Ақыл-ой сынағы деп аталатын бір карта ойыны «Канг» деп аталады. Бұл ойында әрбір картаның оң бүтін санға тең ұпайы болады. Ойын басталғанда қолыңызға ұстау үшін сізге $N$ карта беріледі, ал үстел үстінде солдан оңға қарай қатарлап ашық күйде тағы $M$ карта жатады; сіз қолыңызға алған карталардың да, үстел үстінде жатқан карталардың да барлығының ұпайларын көріп тұрасыз. Одан кейін үстел үстіндегі карталардан тағы $k$ раунд бойы қосымша карта ала аласыз, бірақ оларды солдан оңға қарай ретімен бір-бірден алуыңыз керек. Әр раундта карта алғаннан кейін қолыңыздағы карталарды 1 рет тастай аласыз — қолыңыздағы ұпайлары бірдей карталардың қаншасын болса да тастауға болады. Үстелден карта алып және қолдағы карталарды тастап толық $k$ раунд өткеннен кейін, қолыңызда қалған карталардың жалпы ұпай қосындысы ең аз болатындай етіп ойын жоспарын құруыңыз қажет.

Келесі мысалды қарастырайық:

Егер бастапқыда қолыңызда ұпайлары $6, 3, 9, 6, 3$ болатын бес карта болса, ал үстел үстінде жатқан карталардың солдан оңға қарай ұпайлары $4, 6, 9, 6$ болса:

$k = 1$ жағдайы: егер үстелден тек 1 карта ала алсаңыз, бірінші картаны алған кезде сіздегі карталардың ұпайлары мынадай болады: $6, 3, 9, 6, 3, 4$. Содан кейін ұпайлары бірдей карталарды 1 рет таңдап тастай аласыз. Ең тиімді жолы — қалған карталардың жалпы ұпайы ең аз, яғни $3 + 9 + 3 + 4 = 19$ болуы үшін, ұпайы $6$-ға тең 2 картаны таңдап тастауыңыз керек.

$k = 2$ жағдайы: егер үстелден 2 карта ала алсаңыз, ең тиімді жолы мынадай: ұпайы $4$-ке тең бірінші картаны алғаннан кейін, ұпайы $9$-ға тең бір картаны тастауды таңдайсыз. Қолыңызда қалған карталардың ұпайлары $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$ карталары қалады. Ал 3-ші ретте ұпайы $9$-ға тең картаны алғанда, ұпайы $9$-ға тең екі (2) картаны да тастай аласыз, бұл қалған карталардың жалпы ұпайын $4$ етеді.

$k = 4$ жағдайы: егер үстелден 4 карта ала алсаңыз, ең тиімді жолы мынадай: ұпайы $4$-ке тең бірінші картаны алғаннан кейін, ұпайы $4$-ке тең бір картаны тастауды таңдаңыз, сонда қолыңызда ұпайлары $6, 3, 9, 6, 3$ болатын карталар қалады. Содан кейін 2-ші рет алғанда картаның ұпайы $6$-ға тең болады; ең тиімді жолы — ұпайы $3$-ке тең екі (2) картаны да тастау, сонда қолыңызда $6, 9, 6, 6$ карталары қалады. 3-ші рет алғанда картаның ұпайы $9$-ға тең болады; ұпайы $9$-ға тең екі (2) картаны да тастауды таңдаңыз. Ал ұпайы $6$-ға тең соңғы картаны алған кезде, ұпайы $6$-ға тең 4 картаны тастай аласыз. Бұл тастаудың нәтижесінде қолыңызда ешқандай карта қалмайды, демек карталардың жалпы ұпайы $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$ массив.
• Аталған функция $k = 1, 2, 3, \ldots, M$ болғанда $k$ раундтан кейінгі қолдағы карталардың мүмкін болатын ең аз ұпай қосындысын білдіретін ұзындығы $M$ болатын $C$ массивін қайтаруы тиіс.

Мысалы, егер $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) жіберу әдісі қатысушыдан енгізу деректерін оқу бөлігін және шығару бөлігін жазуды талап ететін жалпы бағдарламалау форматынан өзгеше болады. Бұл есепте қатысушы тек берілген функцияның ішінде қажетті есептеу бөлігін ғана жазуы керек. Әртүрлі енгізу деректері функция параметрлері арқылы қолжетімді болады және есептеу нәтижелері де функция арқылы қайтарылуы тиіс; қатысушыға енгізу деректерін оқу бөлігін және нәтижені шығару бөлігін жазудың қажеті жоқ.

Қатысушыға төмендегідей бірнеше файл беріледі; қатысушы есепте көрсетілгендей тек бір файлды ғана өзгертіп, сол файлды жүйеге жіберуі керек:

• grader.cpp — енгізу деректерін қабылдау және шығару қызметін атқаратын негізгі файл.
• kang.cpp — қатысушы әртүрлі есептеу бағдарламаларын жазуы тиіс және жүйеге жіберетін файл (kang.cpp файлында main() функциясы болмауы керек, бірақ басқа функциялар болуы мүмкін).
• run_cpp.sh — қатысушы бүкіл бағдарламаны іске қосу үшін шақыра алатын файл.
• compile_cpp.sh — қатысушы бағдарламаны компиляциялау үшін шақыра алатын файл.

Қатысушы жүйеден жүктеп алуға болатын .zip файлын алады; оны тарқатқанда (extract) ішінде барлық 4 файл болады. Қатысушы kang.cpp файлын өңдеу үшін мәтіндік редакторды (text editor) немесе IDE қолданғаны жөн, ал бағдарламаны компиляциялауды немесе іске қосуды compile_cpp.sh не run_cpp.sh шақыру арқылы орындайды.

Қатысушы бағдарламаны іске қосу үшін run_cpp.sh файлын шақырған кезде, бағдарлама grader.cpp файлында көрсетілгендей жұмыс істейді, ал «Грейдер файлының сипаттамасы» бөлімінде аталған файлдың жұмыс істеу тәртібі түсіндіріледі.