/
Time Limit: 3 sec / Memory Limit: 1024 MiB
Score: 100 points
Problem Statement
JOI-kun lives in the country of IOI, which is famous for its large lake. Today, a stamp rally competition will be held around the lake.
Around the lake, there are 2N evenly spaced locations, numbered from 1 to 2N in a clockwise manner. Additionally, there are 2N one-way roads connecting adjacent locations. Road i (1 \le i \le 2N - 1) goes from location i to location i+ 1, and road 2N goes from location 2N to location 1. At the midpoint of each road, there is a stamp station.
There are N colors of stamps numbered from 1 to N. The color of the stamp that can be obtained at the stamp station on road i (1 \le i \le 2N) is given by A_{i}. For each color j (1 \le j \le N), there are exactly 2 stamp stations where the stamp of that color can be obtained.
JOI-kun, equipped with many stamp cards, participates in the stamp rally competition. Each stamp card has two spaces, left and right, where stamps can be pressed. At most one stamp can be placed in each space. Initially, all stamp cards are blank.
The process of the stamp rally competition for JOI-kun is as follows:
- First, he selects one of the 2N locations as the starting point and moves there. If he selects location i (1 \le i \le 2N), he must pay a participation cost of C_{i}.
-
Next, he can instruct the event organizers to swap adjacent stamp stations. Specifically, he can swap the stamp stations on roads 2N and 1, or swap the stations on roads i - 1 and i for any i (2 \le i \le 2N).
Each swap costs X, and JOI-kun can issue as many swap commands as he wants, possibly none. Swaps are executed immediately upon command. However, to prevent cheating, it is not allowed to exchange stamp stations that cross the starting location that JOI-kun has chosen. That is, if he starts at location 1, swapping the stations on roads 2N and 1 is forbidden. If he starts at location i (2 \le i \le 2N), swapping the stations on roads i - 1 and i is forbidden.
-
After that, JOI-kun starts from his chosen location and moves clockwise, visiting each of the 2N stamp stations in sequence. When visiting a stamp station, he can press the stamp onto his stamp cards as many times as he likes. He can also stamp both the left and right spaces of a single card at the same station. However, for each stamp card, he must always stamp the left space before the right space; that is, he cannot stamp the right space if the left space of that stamp card is still empty.
JOI-kun wants to collect many distinct types of stamp cards that are stamped on both spaces. Let stamped card (a, b) be a stamp card with color a stamped on the left and color b stamped on the right. Two stamped cards (a_{1}, b_{1}) and (a_{2}, b_{2}) are considered the same type if and only if a_{1} = a_{2} and b_{1} = b_{2}. Since there are N colors of stamps, there are a total of N^{2} possible types of stamped cards.
You need to answer Q queries to help JOI-kun. The q-th query (1 \le q \le Q) asks the following:
- What is the minimum total cost required for JOI-kun to collect at least K_{q} types of stamped cards by the end of the rally? It is provable that under the given constraints, JOI-kun can always collect at least K_{q} types of stamped cards by spending a sufficiently large cost.
Given the information about stamp colors, participation costs, swap costs, and queries, write a program to answer JOI-kun’s Q queries.
Input
Read the following data from the standard input.
N X
A_1 A_2 \cdots A_{2N}
C_1 C_2 \cdots C_{2N}
Q
K_1
K_2
\vdots
K_Q
Output
Write Q lines to the standard output, where the q-th line (1 \le q \le Q) contains the minimum total cost required to collect at least K_{q} types of stamped cards.
Constraints
- 2 \le N \le 500\,000.
- 1 \le X \le 500\,000.
- (A_{1}, A_{2}, \ldots, A_{2N}) is a permutation of (1, 1, 2, 2, \ldots, N, N).
- 1 \le C_{i} \le 10^{18} (1 \le i \le 2N).
- 1 \le Q \le 500\,000.
- 1 \le K_{q} \le N^{2} (1 \le q \le Q).
- Given values are all integers.
Subtasks
- (5 points) N \le 4.
- (20 points) N \le 5000, Q = 1, K_{1} = N^{2}.
- (20 points) N \le 5000, Q = 1.
- (19 points) N \le 5000.
- (21 points) Q = 1.
- (15 points) No additional constraints.
Sample Input 1
3 2 1 2 2 3 1 3 6 1 4 5 4 7 2 8 9
Sample Output 1
3 4
Consider the case where JOI-kun selects location 2 as the starting point and instructs the exchange of the stamp stations installed on road 3 and road 4.
In this case,
- The total cost paid by JOI-kun is C_{2} + X \times 1 = 3.
- JOI-kun visits the stamp stations in the order of roads 2, 3, 4, 5, 6, 1, and the stamp colors available at each station in sequence are 2, 3, 2, 1, 3, 1.
-
The number of types of stamp cards stamped on both spaces that JOI-kun can collect is 8.
- For example, to obtain a stamped card with a stamp of color 3 on the left and a stamp of color 1 on the right, JOI-kun can stamp the left side at road 3 and the right side at road 1.
- However, note that it is impossible to obtain a stamped card with a stamp of color 1 on the left and color 2 on the right.
Since it is impossible to obtain 8 or more types of stamped cards with a cost of 2 or less, the first line of the output should be 3.
Additionally, if JOI-kun selects location 3 as the starting point and does not instruct any stamp station exchange, he can obtain 9 types of stamped cards.
In this case, the total cost paid by JOI-kun is C_{3} + X \times 0 = 4. Since it is impossible to obtain 9 or more types of stamped cards with a cost of 3 or less, the second line of the output should be 4.
This input example satisfies the constraints of subtasks 1, 4, 6.
Sample Input 2
8 1 1 2 6 1 6 3 8 4 5 5 3 4 7 2 7 8 4 5 3 6 2 9 1 4 6 3 8 5 2 9 4 7 1 64
Sample Output 2
7
Consider the case where JOI-kun chooses location 10 as the starting point and instructs the stamp station exchanges in the following order:
- Exchange the stamp station installed on road 15 with the one on road 16.
- Exchange the stamp station installed on road 2 with the one on road 3.
- Exchange the stamp station installed on road 16 with the one on road 1.
- Exchange the stamp station installed on road 1 with the one on road 2.
In this case, JOI-kun can obtain 64 types of stamped cards, and the total cost paid is C_{10} + X \times 4 = 7.
This input example satisfies the constraints of subtasks 2, 3, 4, 5, 6.
Sample Input 3
9 4 4 3 5 3 8 1 5 8 1 7 6 2 4 9 6 9 2 7 12 9 4 8 7 1 20 5 8 7 4 13 5 9 10 3 7 8 6 39 81 73 79 64 52
Sample Output 3
1 18 3 10 1 1
This input example satisfies the constraints of subtasks 4, 6.
配点 : 100 点
問題文
JOI 君が住む IOI 国は,大きな湖があることで有名である.今日,湖の周りでスタンプラリー大会が行われることになった.
湖の周りには等間隔に 2N 個の地点が並んでおり,時計回りに 1 から 2N までの番号が付けられている. また,隣り合う地点どうしを結ぶ 2N 本の 一方通行 の道がある. 道 i (1\leqq i \leqq 2N - 1) は地点 i から地点 i+1 へ向かう道であり,道 2N は地点 2N から地点 1 へ向かう道である. それぞれの道の真ん中には 1 つのスタンプ台が設置されている.
スタンプには 1 から N までの N 色があり,道 i (1\leqq i \leqq 2N) の真ん中に設置されているスタンプ台で押すことのできるスタンプの色は A_i である. 各 j (1\leqq j \leqq N) について,色 j のスタンプを押すことのできるスタンプ台はちょうど 2 つある.
JOI 君はたくさんのスタンプカードを持ってスタンプラリー大会に参加することにした. それぞれのスタンプカードには左右 2 箇所にスタンプを押すことのできる枠が印刷されている. 1 つの枠にはスタンプを高々 1 つ押すことができる. はじめ,どのスタンプカードにもスタンプは押されていない. スタンプラリー大会での JOI 君の行動は以下の通りである.
- まず,スタート地点として 2N 個の地点のいずれかを選び,その地点に移動する.地点 i (1\leqq i \leqq 2N) をスタート地点に選んだとき,JOI 君はスタンプラリー大会の参加費としてコスト C_i を支払う.
- 次に,JOI 君は隣り合う道どうしに設置されているスタンプ台を交換するよう,運営会社に指示を出すことができる.すなわち,道 2N,1 に設置されているスタンプ台の交換,もしくは,i (2\leqq i \leqq 2N) を指定して道 i - 1,i に設置されているスタンプ台の交換を指示することができる. JOI 君が指示を出す際に支払うコストは 1 回あたり X で, 何度でも 指示を出すことができる.一度も指示を出さないことも可能である.スタンプ台の交換は指示を出すたびにただちに実行される. ただし,不正防止のため,JOI 君が選んだスタート地点をまたぐようなスタンプ台の交換はできない.すなわち,JOI 君がスタート地点として地点 1 を選んだ場合は道 2N,1 に設置されているスタンプ台どうしの交換が,地点 i (2\leqq i \leqq 2N) を選んだ場合は道 i - 1,i に設置されているスタンプ台どうしの交換が,禁止される.
- その後,JOI 君はスタート地点を出発して時計回りに移動し,2N 個のスタンプ台を順に訪れ,スタート地点に戻ってきた段階でスタンプラリーを終了する.スタンプ台を訪れた際,JOI 君はスタンプカードにスタンプを何回でも押すことができる.同じスタンプ台で 1 枚のスタンプカードの左右にスタンプを押すことも可能である.ただし,それぞれのスタンプカードには必ず左,右の順番で押す必要がある.つまり,左側が空欄であるスタンプカードの右側にスタンプを押すことはできない.
JOI 君はできる限り多くの種類の,左右両方の枠にスタンプが押されたスタンプカードを集めたい. 左側に色 a,右側に色 b のスタンプが押されたスタンプカードをスタンプカード (a,b) と表すこととする. このとき,スタンプカード (a_1, b_1) と (a_2, b_2) は,a_1=a_2 かつ b_1=b_2 のとき,またそのときに限り,種類が同じであるとみなす.
N 色のスタンプがあるため,左右両方の枠にスタンプが押されたスタンプカードは全部で N^2 種類あることに注意せよ.
あなたは JOI 君の戦略作りを手伝うために,Q 個の質問に答える必要がある. q 個目 (1\leqq q \leqq Q) の質問は以下である.
- スタンプラリーの終了時点で,左右両方の枠にスタンプが押されたスタンプカードを K_q 種類以上持っているために支払う必要のあるコストの合計の最小値はいくらか?なお,本問の制約下では,十分多くのコストを支払うことで左右両方の枠にスタンプが押されたスタンプカードを K_q 種類以上集められることが証明できる.
スタンプの色,スタンプラリー大会の参加費,運営会社に指示を出す際に支払うコスト,および JOI 君の質問についての情報が与えられたとき,JOI 君の Q 個の質問の答えを計算するプログラムを作成せよ.
入力
入力は以下の形式で標準入力から与えられる.
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\leqq q \leqq Q) には,スタンプラリーの終了時点で,左右両方の枠にスタンプが押されたスタンプカードを K_q 種類以上持っているために,支払う必要のあるコストの合計の最小値を出力せよ.
制約
- 2 \leqq N \leqq 500\,000.
- 1 \leqq X \leqq 500\,000.
- (A_1, A_2, \dots, A_{2N}) は (1, 1, 2, 2, \dots, N, N) の並べ替えである.
- 1 \leqq C_i \leqq 10^{18} (1 \leqq i \leqq 2N).
- 1 \leqq Q \leqq 500\,000.
- 1 \leqq K_q \leqq N^2 (1\leqq q \leqq Q).
- 入力される値はすべて整数である.
小課題
- (5 点) N\leqq 4.
- (20 点) N\leqq 5000,Q = 1,K_1=N^2.
- (20 点) N\leqq 5000,Q = 1.
- (19 点) N\leqq 5000.
- (21 点) Q = 1.
- (15 点) 追加の制約はない.
入力例 1
3 2 1 2 2 3 1 3 6 1 4 5 4 7 2 8 9
出力例 1
3 4
JOI 君がスタート地点として地点 2 を選び,道 3 に設置されているスタンプ台と道 4 に設置されているスタンプ台との交換を指示した場合を考える. このとき,
- JOI 君が支払うコストの合計は C_2+X\times 1 = 3 である.
- JOI 君は道 2,3,4,5,6,1 の順にスタンプ台を訪れ,それぞれのスタンプ台で押すことのできるスタンプの色は,順に色 2, 3, 2, 1, 3, 1 となる.
- JOI 君が最終的に持っている可能性のある,左右両方の枠にスタンプが押されたスタンプカードは 8 種類となる.
- 例えば,左側に色 3 のスタンプ,右側に色 1 のスタンプが押されたスタンプカードを得るためには,道 3 でスタンプカードの左側に,道 1 でスタンプカードの右側に,それぞれスタンプを押せばよい.
- 左側に色 1 のスタンプ,右側に色 2 のスタンプが押されたスタンプカードだけは得られないことに注意せよ.
2 以下のコストで 8 種類以上のスタンプカードを得ることはできないため,1 行目には 3 を出力する.
また,JOI 君がスタート地点として地点 3 を選び,スタンプ台の交換を指示しなかった場合には,9 種類のスタンプカードを得ることができる. このときに JOI 君が支払うコストの合計は C_3 + X\times 0 = 4 である.
3 以下のコストで 9 種類以上のスタンプカードを得ることはできないため,2 行目には 4 を出力する.
この入力例は小課題 1,4,6 の制約を満たす.
入力例 2
8 1 1 2 6 1 6 3 8 4 5 5 3 4 7 2 7 8 4 5 3 6 2 9 1 4 6 3 8 5 2 9 4 7 1 64
出力例 2
7
スタート地点として地点 10 を選び,次の順にスタンプ台の交換を指示した場合を考える.
- 道 15 に設置されているスタンプ台と道 16 に設置されているスタンプ台との交換
- 道 2 に設置されているスタンプ台と道 3 に設置されているスタンプ台との交換
- 道 16 に設置されているスタンプ台と道 1 に設置されているスタンプ台との交換
- 道 1 に設置されているスタンプ台と道 2 に設置されているスタンプ台との交換
このとき 64 種類のスタンプカードを得ることができ,支払うコストの合計は C_{10}+X\times 4=7 である.
この入力例は小課題 2,3,4,5,6 の制約を満たす.
入力例 3
9 4 4 3 5 3 8 1 5 8 1 7 6 2 4 9 6 9 2 7 12 9 4 8 7 1 20 5 8 7 4 13 5 9 10 3 7 8 6 39 81 73 79 64 52
出力例 3
1 18 3 10 1 1
この入力例は小課題 4,6 の制約を満たす.