Sebuah permainan kartu yang terkenal sebagai ujian kecerdasan bernama “Kang”. Dalam permainan ini, setiap kartu memiliki skor berupa bilangan bulat positif. Pada awalnya, Anda akan menerima $N$ kartu untuk dipegang di tangan, dan terdapat $M$ kartu lainnya yang diletakkan terbuka di atas meja berjajar dari kiri ke kanan. Anda dapat melihat skor dari setiap kartu, baik yang diterima di tangan maupun yang diletakkan di atas meja. Selanjutnya, Anda dapat mengambil kartu tambahan dari meja sebanyak $k$ putaran, dengan mengambil satu per satu secara berurutan dari kiri ke kanan. Setelah setiap putaran pengambilan kartu, Anda dapat membuang kartu di tangan sebanyak 1 kali, yaitu membuang berapa pun jumlah kartu di tangan yang memiliki skor yang sama. Anda harus merencanakan strategi permainan agar setelah mengambil kartu dari meja dan membuang kartu di tangan selama $k$ putaran penuh, kartu yang tersisa di tangan memiliki total skor sekecil mungkin.

Perhatikan contoh berikut ini.

Misalkan pada awalnya Anda memiliki lima kartu dengan skor $6, 3, 9, 6, 3$ dan kartu yang diletakkan di atas meja memiliki skor berurutan dari kiri ke kanan $4, 6, 9, 6$.

Kasus $k = 1$: Jika Anda hanya dapat mengambil 1 kartu dari meja, ketika Anda mengambil kartu pertama, skor kartu yang Anda miliki menjadi $6, 3, 9, 6, 3, 4$. Kemudian Anda dapat memilih untuk membuang kartu dengan skor yang sama sebanyak 1 kali; cara terbaik adalah memilih untuk membuang 2 kartu dengan skor $6$, sehingga total skor kartu yang tersisa menjadi sekecil mungkin yaitu $3 + 9 + 3 + 4 = 19$.

Kasus $k = 2$: Jika Anda dapat mengambil 2 kartu dari meja, cara terbaik adalah: setelah mengambil kartu pertama yang memiliki skor $4$, Anda memilih untuk membuang satu kartu yang memiliki skor $9$. Kartu yang tersisa di tangan memiliki skor $6, 3, 6, 3, 4$. Kemudian, ketika mengambil kartu ke-2 yang memiliki skor $6$, Anda dapat membuang 3 kartu yang memiliki skor $6$, sehingga kartu yang tersisa memiliki total skor terkecil yaitu $3 + 3 + 4 = 10$.

Kasus $k = 3$: Jika Anda dapat mengambil 3 kartu dari meja, cara terbaik adalah: ketika Anda mengambil kartu pertama, skor kartu yang ada di tangan adalah $6, 3, 9, 6, 3, 4$. Kemudian pilih kartu dengan skor yang sama untuk dibuang sebanyak 1 kali; cara terbaik adalah mengambil kedua kartu (2 kartu) dengan skor $3$ untuk dibuang, sehingga tersisa kartu di tangan $6, 9, 6, 4$. Selanjutnya, ketika mengambil kartu ke-2 dengan skor $6$, Anda dapat membuang 3 kartu dengan skor $6$, sehingga kartu di tangan menjadi $9, 4$. Dan ketika Anda mengambil kartu untuk ke-3 kalinya yang memiliki skor $9$, Anda dapat membuang kedua kartu (2 kartu) dengan skor $9$, sehingga kartu yang tersisa memiliki total skor $4$.

Kasus $k = 4$: Jika Anda dapat mengambil 4 kartu dari meja, cara terbaik adalah: setelah mengambil kartu pertama dengan skor $4$, pilih untuk membuang satu kartu dengan skor $4$, menyisakan kartu di tangan dengan skor $6, 3, 9, 6, 3$. Selanjutnya pada pengambilan ke-2, kartu memiliki skor $6$; cara terbaik adalah membuang kedua kartu (2 kartu) dengan skor $3$, menyisakan kartu di tangan $6, 9, 6, 6$. Pada pengambilan ke-3, kartu memiliki skor $9$; pilih untuk membuang kedua kartu (2 kartu) dengan skor $9$. Dan pada pengambilan kartu terakhir yang memiliki skor $6$, Anda dapat membuang 4 kartu dengan skor $6$. Pembuangan kali ini mengakibatkan tidak ada kartu yang tersisa di tangan, yang berarti total skor kartu adalah $0$.

Tugas Anda (Your Task)

Carilah “total skor minimum dari kartu yang tersisa di tangan” setelah menyelesaikan $k$ putaran untuk $k = 1, 2, 3, \ldots, M$.

Soal ini memiliki format pemrograman yang berbeda dari format biasa, yang akan digunakan dalam kompetisi sesungguhnya. Silakan lihat bagian akhir soal ini mengenai cara penggunaannya.

Detail Implementasi

Anda harus menulis fungsi berikut:

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

Dengan parameter sebagai berikut:

• $A$ adalah array dengan panjang $N$ yang menyatakan nomor kartu di tangan pada saat awal.
• $B$ adalah array dengan panjang $M$ yang menyatakan nomor kartu yang diletakkan di atas meja, diurutkan dari kiri ke kanan.
• Fungsi tersebut harus mengembalikan array $C$ dengan panjang $M$ yang menyatakan total skor kartu di tangan terkecil yang mungkin setelah $k$ putaran, untuk $k = 1, 2, 3, \ldots, M$.

Sebagai contoh, jika $A = [6, 3, 9, 6, 3]$ dan $B = [4, 6, 9, 6]$, fungsi harus mengembalikan array $[19, 10, 4, 0]$.

Batasan

• $1 \le N, M \le 10^6$
• $1 \le A[i] \le 10^9$ untuk setiap $i$ dengan $1 \le i \le N$
• $1 \le B[i] \le 10^9$ untuk setiap $i$ dengan $1 \le i \le M$

Subsoal

Catatan

Petunjuk Pemrograman

Untuk soal ini, cara menulis dan mengirimkan program ke sistem penilai (Grader) memiliki format yang berbeda dari format pemrograman pada umumnya di mana peserta harus menulis bagian pembacaan masukan dan bagian pencetakan keluaran. Pada soal ini, peserta hanya perlu menulis bagian perhitungan yang diperlukan di dalam fungsi yang telah ditentukan. Berbagai data masukan dapat diakses melalui parameter fungsi, dan hasil perhitungan juga harus dikembalikan melalui fungsi tersebut, tanpa perlu menulis bagian pembacaan masukan maupun bagian pencetakan keluaran.

Peserta akan menerima beberapa berkas sebagai berikut. Peserta hanya perlu memodifikasi satu berkas sesuai ketentuan soal dan mengirimkan berkas tersebut ke dalam sistem:

• grader.cpp adalah berkas utama yang bertugas menerima masukan dan mencetak keluaran.
• kang.cpp adalah berkas tempat peserta harus menulis program perhitungan dan merupakan berkas yang harus dikirimkan peserta ke sistem (di dalam berkas kang.cpp dilarang terdapat fungsi main(), tetapi diperbolehkan terdapat fungsi-fungsi lainnya).
• run_cpp.sh adalah berkas yang dapat dipanggil peserta untuk menjalankan keseluruhan program.
• compile_cpp.sh adalah berkas yang dapat dipanggil peserta untuk mengompilasi program.

Peserta akan menerima berkas .zip yang dapat diunduh dari sistem; ketika berkas tersebut diekstrak (extract), keempat berkas di atas akan tersedia di dalamnya. Peserta disarankan menggunakan text editor atau IDE untuk mengedit berkas kang.cpp, serta melakukan kompilasi atau menjalankan program dengan memanggil compile_cpp.sh atau run_cpp.sh.

Ketika peserta memanggil berkas run_cpp.sh untuk menjalankan program, program akan bekerja sebagaimana ditentukan di dalam berkas grader.cpp, di mana bagian “Deskripsi Berkas Grader” menjelaskan cara kerja dari berkas tersebut.