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

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 君の行動は以下の通りである． 1. まず，スタート地点として $ 2N $ 個の地点のいずれかを選び，その地点に移動する．地点 $ i $ ( $ 1\leqq i \leqq 2N $ ) をスタート地点に選んだとき，JOI 君はスタンプラリー大会の参加費としてコスト $ C_i $ を支払う． 2. 次に，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 $ に設置されているスタンプ台どうしの交換が，禁止される． 3. その後，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 $ 種類以上持っているために，支払う必要のあるコストの合計の最小値を出力せよ．

### 小課題 1. ( $ 5 $ 点) $ N\leqq 4 $ ． 2. ( $ 20 $ 点) $ N\leqq 5000 $ ， $ Q = 1 $ ， $ K_1=N^2 $ ． 3. ( $ 20 $ 点) $ N\leqq 5000 $ ， $ Q = 1 $ ． 4. ( $ 19 $ 点) $ N\leqq 5000 $ ． 5. ( $ 21 $ 点) $ Q = 1 $ ． 6. ( $ 15 $ 点) 追加の制約はない． --- ### Sample Explanation 1 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 $ の制約を満たす． --- ### Sample Explanation 2 スタート地点として地点 $ 10 $ を選び，次の順にスタンプ台の交換を指示した場合を考える． - 道 $ 15 $ に設置されているスタンプ台と道 $ 16 $ に設置されているスタンプ台との交換 - 道 $ 2 $ に設置されているスタンプ台と道 $ 3 $ に設置されているスタンプ台との交換 - 道 $ 16 $ に設置されているスタンプ台と道 $ 1 $ に設置されているスタンプ台との交換 - 道 $ 1 $ に設置されているスタンプ台と道 $ 2 $ に設置されているスタンプ台との交換 このとき $ 64 $ 種類のスタンプカードを得ることができ，支払うコストの合計は $ C_{10}+X\times 4=7 $ である． この入力例は小課題 $ 2,3,4,5,6 $ の制約を満たす． --- ### Sample Explanation 3 この入力例は小課題 $ 4,6 $ の制約を満たす． ### Constraints - $ 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 $ )． - 入力される値はすべて整数である．