知力の試練として語り継がれるあるカードゲームがあり、その名を「แคง (Kang)」といいます。このゲームでは、各カードに正の整数の得点が書かれています。ゲーム開始時、あなたは $N$ 枚のカードを手札として受け取り、さらにテーブルの上には $M$ 枚のカードが左から右へ表向きに並んでいます。あなたは、手札として受け取ったカードとテーブルの上に置かれたカードの両方について、すべてのカードの得点を見ることができます。その後、あなたはテーブルの上のカードを左から右へ 1 枚ずつ順番に引く操作を $k$ ラウンド行うことができます。各ラウンドでカードを引いた後、あなたは手札から「得点が同じである手札のカードを何枚でもまとめて捨てる」操作を 1 回行うことができます。テーブルからカードを引き手札からカードを捨てる操作を $k$ ラウンド終えた後、手札に残ったカードの得点の合計が最小になるようにプレイ計画を立てなければなりません。

次の例を考えてみましょう。

最初にあなたが 5 枚のカードを持っており、その得点が $6, 3, 9, 6, 3$ であり、テーブルの上に左から右へ置かれているカードの得点が $4, 6, 9, 6$ であるとします。

$k = 1$ の場合：テーブルの上のカードを 1 枚だけ引けるとき、最初の 1 枚を引くと、あなたが持っているカードの得点は $6, 3, 9, 6, 3, 4$ となります。その後、得点が同じカードを選んで 1 回捨てることができます。最善の方法は、得点が $6$ のカードを 2 枚選んで捨てることであり、これにより残ったカードの得点の合計は最小値 $3 + 9 + 3 + 4 = 19$ となります。

$k = 2$ の場合：テーブルの上のカードを 2 枚引けるとき、最善の方法は次の通りです。得点が $4$ である最初のカードを引いた後、得点が $9$ のカードを 1 枚捨てることを選びます。手札に残ったカードの得点は $6, 3, 6, 3, 4$ となります。次に、得点が $6$ である 2 枚目のカードを引いたとき、得点が $6$ のカードを 3 枚捨てることができ、残ったカードの得点の合計は最小値 $3 + 3 + 4 = 10$ となります。

$k = 3$ の場合：テーブルの上のカードを 3 枚引けるとき、最善の方法は次の通りです。最初のカードを引いたとき、手札にあるカードの得点は $6, 3, 9, 6, 3, 4$ となります。その後、得点が同じカードを選んで 1 回捨てることができますが、最善の方法は得点が $3$ のカードを 2 枚とも捨てることであり、手札には $6, 9, 6, 4$ が残ります。次に、得点が $6$ である 2 枚目のカードを引いたとき、得点が $6$ のカードを 3 枚捨てることができ、手札は $9, 4$ となります。そして、得点が $9$ である 3 回目のカードを引いたとき、得点が $9$ のカードを 2 枚とも捨てることができ、残ったカードの得点の合計は $4$ となります。

$k = 4$ の場合：テーブルの上のカードを 4 枚引けるとき、最善の方法は次の通りです。得点が $4$ である最初のカードを引いた後、得点が $4$ のカードを 1 枚捨てることを選ぶと、手札に残るカードの得点は $6, 3, 9, 6, 3$ となります。次に 2 回目に引くカードの得点は $6$ であり、最善の方法は得点が $3$ のカードを 2 枚とも捨てることで、手札には $6, 9, 6, 6$ が残ります。3 回目に引くカードの得点は $9$ であり、得点が $9$ のカードを 2 枚とも捨てます。そして、得点が $6$ である最後のカードを引くとき、得点が $6$ のカードを 4 枚捨てることができます。この捨て札によって手札にカードが 1 枚も残らなくなるため、カードの得点の合計は $0$ となります。

あなたの課題 (Your Task)

$k = 1, 2, 3, \ldots, M$ のそれぞれについて、$k$ ラウンド終了後に「手札に残ったカードの得点の合計の最小値」を求めてください。

この問題は、実際の競技で使用される通常とは異なるプログラミング形式を採用しています。使用方法については、本問題文の末尾を参照してください。

実装の詳細

以下の関数を記述しなければなりません：

std::vector<long long> capsize(std::vector<int> A, std::vector<int> B)

パラメータは以下の通りです：

• $A$ は長さ $N$ の配列であり、開始時の手札にあるカードの番号を表します。
• $B$ は長さ $M$ の配列であり、テーブルの上に置かれているカードの番号を左から右の順で表します。
• この関数は、長さ $M$ の配列 $C$ を返さなければなりません。これは $k = 1, 2, 3, \ldots, M$ に対して、$k$ ラウンド後に達成可能な手札のカードの得点の合計の最小値を表します。

例えば、$A = [6, 3, 9, 6, 3]$ かつ $B = [4, 6, 9, 6]$ の場合、関数は配列 $[19, 10, 4, 0]$ を返さなければなりません。

制約

• $1 \le N, M \le 10^6$
• $1 \le i \le N$ を満たす各 $i$ について、$1 \le A[i] \le 10^9$
• $1 \le i \le M$ を満たす各 $i$ について、$1 \le B[i] \le 10^9$

小課題

注記

プログラミングの指示

この問題では、プログラムを作成してグレーダー（Grader）システムに提出する方法が、競技者が入力の受け取り部分と出力の表示部分を記述する通常の形式とは異なります。この問題では、競技者は指定された関数の中に必要な計算部分のみを記述しなければなりません。各種入力データは関数のパラメータを通じて利用でき、計算結果もまた関数を通じて返さなければなりません。競技者は入力を受け取る部分のプログラムを書く必要はなく、出力部分を書く必要もありません。

競技者には以下のように複数のファイルが与えられます。競技者は問題で指定された 1 つのファイルのみを編集し、そのファイルをシステムに提出しなければなりません：

• grader.cpp は入出力を受け持つメインファイルです。
• kang.cpp は競技者が各種計算プログラムを記述するファイルであり、システムに提出するファイルです（kang.cpp ファイル内に main() 関数を含めてはいけませんが、他の関数を含めることは可能です）。
• run_cpp.sh は競技者がプログラム全体を実行するために呼び出すことができるファイルです。
• compile_cpp.sh は競技者がプログラムをコンパイルするために呼び出すことができるファイルです。

競技者にはシステムからダウンロード可能な .zip ファイルが提供され、展開（extract）するとこれら 4 つのファイルすべてが含まれています。競技者はテキストエディタまたは IDE を使用して kang.cpp ファイルを編集し、compile_cpp.sh または run_cpp.sh を呼び出すことでプログラムのコンパイルや実行を行ってください。

競技者が run_cpp.sh ファイルを呼び出してプログラムを実行すると、プログラムは grader.cpp ファイルに記述された通りに動作します。このファイルの動作については「グレーダーファイルの説明」の項目で説明されています。