AT_joisp2025_e.スタンプラリー 4 (Collecting Stamps 4)

JOI 君居住的 IOI 国因拥有一个巨大的湖泊而闻名。今天，湖周围将举办一次集章拉力赛大会。

湖的周围等间隔排列着 $2N$ 个地点，按照顺时针方向编号为 $1$ 到 $2N$。每两个相邻的地点之间，各有一条单向道路。第 $i$ 条道路（$1 \leq i \leq 2N-1$）是从第 $i$ 个地点指向第 $i+1$ 个地点的道路，第 $2N$ 条道路则是从第 $2N$ 个地点指向第 $1$ 个地点的道路。每条道路的中间都设置有一个集章台。

章的颜色共有 $N$ 种，编号为 $1$ 到 $N$。道路 $i$（$1 \leq i \leq 2N$）上的集章台可以盖的章的颜色为 $A_i$。对于每个 $j$（$1 \leq j \leq N$），颜色 $j$ 的章各恰好出现 $2$ 次。

JOI 君带着许多集章卡参加此次拉力赛。每张集章卡上印有左右两个章框，每个框最多只能盖一个章。初始时，所有集章卡均未盖章。JOI 君在集章拉力赛中的行动流程如下：

1. 首先，选择 $2N$ 个地点中的某一个作为起点，并移动到该地点。若起点为第 $i$ 个地点，则需支付参赛费用 $C_i$。
2. 接着，JOI 君可以指示主办方交换相邻两条道路上的集章台。例如，可以指定交换道路 $2N$ 和 $1$ 上的集章台，或指定 $i$（$2 \leq i \leq 2N$），即交换道路 $i-1$ 与 $i$ 上的集章台。每次交换需支付代价 $X$，且可以不限次数地进行交换，也可以完全不交换。每次发出交换指示后，立即完成交换。但为防止作弊，不能进行跨越起点的交换：若选择第 $1$ 个地点为起点，则禁止道路 $2N$ 和 $1$ 之间的集章台交换；若选择第 $i$ 个地点为起点（$2 \leq i \leq 2N$），则禁止道路 $i-1$ 与 $i$ 之间的集章台交换。
3. 随后，JOI 君从起点出发，顺时针依次经过 $2N$ 个集章台，最后回到起点，结束拉力赛。每到达一个集章台时，可以用章在集章卡上任意多次盖章。在同一集章台上，也可以在一张卡的左右两个框分别盖章。但必须遵循先左后右的顺序，即右边空框不能在左边空框之前盖章。

JOI 君希望尽可能多地收集到不同种类、左右两格都盖有章的集章卡。令左侧盖有颜色 $a$、右侧盖有颜色 $b$ 的集章卡记为 $(a, b)$。仅当 $a_1 = a_2$ 且 $b_1 = b_2$ 时，$(a_1, b_1)$ 和 $(a_2, b_2)$ 被视为相同种类。

注意因为有 $N$ 种颜色，所以两格均盖满章的集章卡共有 $N^2$ 种可能。

你要帮助 JOI 君回答 $Q$ 个问题。第 $q$ 个问题如下（$1 \leq q \leq Q$）：

• 使拉力赛结束时，拥有不同种类且左右两格均盖章的集章卡不少于 $K_q$ 种，所需支付的总费用最小值是多少？本题保证了，在本题限制下，付出足够多的费用总是可以获得任意数量的盖满章的集章卡。

给定章的颜色信息、参赛费用、交换操作费用，以及 $Q$ 个问题的信息，请编写程序计算 JOI 君每个问题的答案。

输入从标准输入读入，格式如下：

$N\ X\ A_1\ A_2\ \cdots\ A_{2N}\ C_1\ C_2\ \cdots\ C_{2N}\ Q\ K_1\ K_2\ \vdots\ K_Q$

请按顺序输出 $Q$ 行。第 $q$ 行（$1 \leq q \leq Q$）输出使拉力赛结束时拥有不少于 $K_q$ 种左右两格均盖章的集章卡所需的最小总费用。

小题点

1.（$5$ 分）$N \leq 4$。
2.（$20$ 分）$N \leq 5000$，$Q = 1$，$K_1 = N^2$。
3.（$20$ 分）$N \leq 5000$，$Q = 1$。
4.（$19$ 分）$N \leq 5000$。
5.（$21$ 分）$Q = 1$。
6.（$15$ 分）无附加限制。

---

样例说明 1

假设 JOI 君选择第 $2$ 个地点为起点，并进行一次将道路 $3$ 与道路 $4$ 上的集章台交换的操作。那么：

• JOI 君需支付的总费用为 $C_2 + X \times 1 = 3$。
• 按顺时针经过的道路和集章台顺序为 $2,3,4,5,6,1$，分别可盖的章颜色顺序为 $2,3,2,1,3,1$。
• 最终可得到的，左右都盖满章的集章卡有 $8$ 种。
  • 例如，要得到左为 $3$、右为 $1$ 的集章卡，可以在道路 $3$ 上盖左，$1$ 上盖右。
  • 只有左为 $1$、右为 $2$ 的集章卡无法获得。

费用不超过 $2$ 时无法获得 $8$ 种或更多集章卡故第 $1$ 行输出 $3$。

若 JOI 君选择第 $3$ 个地点为起点，不进行任何交换，则可获得 $9$ 种集章卡。此时需要支付的总费用为 $C_3 + X \times 0 = 4$。

费用不超过 $3$ 时无法获得 $9$ 种或更多集章卡，所以第 $2$ 行输出 $4$。

此输入数据符合小题 $1,4,6$ 的限制。

---

样例说明 2

假如选择第 $10$ 个地点为起点，并依次进行以下交换操作：

• 交换道路 $15$ 与 $16$ 上的集章台
• 交换道路 $2$ 与 $3$ 上的集章台
• 交换道路 $16$ 与 $1$ 上的集章台
• 交换道路 $1$ 与 $2$ 上的集章台

此时可以获得 $64$ 种不同类型的集章卡，总费用为 $C_{10} + X \times 4 = 7$。

此输入数据符合小题 $2,3,4,5,6$ 的限制。

---

样例说明 3

此输入数据符合小题 $4,6$ 的限制。

数据范围

• $2 \leq N \leq 500\,000$。
• $1 \leq X \leq 500\,000$。
• $(A_1, A_2, \dots, A_{2N})$ 为 $(1, 1, 2, 2, \dots, N, N)$ 的一个排列。
• $1 \leq C_i \leq 10^{18}$（$1 \leq i \leq 2N$）。
• $1 \leq Q \leq 500\,000$。
• $1 \leq K_q \leq N^2$（$1 \leq q \leq Q$）。
• 所有输入均为整数。

由 ChatGPT 5 翻译