هناك لعبة ورق يُقال إنها اختبار للذكاء، وتُسمّى «كانغ». في هذه اللعبة، لكل بطاقة نقاط تساوي عددًا صحيحًا موجبًا. في البداية، تحصل على $N$ بطاقة لتحتفظ بها في يدك، وتوجد $M$ بطاقة أخرى موضوعة مكشوفةً على الطاولة ومرتبةً من اليسار إلى اليمين، حيث يمكنك رؤية نقاط جميع البطاقات سواء التي حصلت عليها في يدك أو الموضوعة على الطاولة. بعد ذلك، يمكنك سحب بطاقات إضافية من الطاولة لمدة $k$ جولات، بحيث تسحب بطاقةً واحدةً في كل مرة بالترتيب من اليسار إلى اليمين. بعد سحب بطاقة في كل جولة، يمكنك التخلص من بطاقات في يدك مرةً واحدةً (1)، وذلك بالتخلص من أي عدد تشاء من البطاقات في يدك التي لها نفس النقاط. عليك التخطيط للعب بحيث يكون مجموع نقاط البطاقات المتبقية في يدك بعد سحب البطاقات من الطاولة والتخلص من البطاقات في يدك لإتمام $k$ جولات أصغر ما يمكن.

تأمل المثال التالي:

إذا كان لديك في البداية خمس بطاقات نقاطها هي $6, 3, 9, 6, 3$، وكانت البطاقات الموضوعة على الطاولة مرتبةً من اليسار إلى اليمين بنقاط $4, 6, 9, 6$:

الحالة $k = 1$: إذا كان بإمكانك سحب بطاقة واحدة (1) فقط من الطاولة، فعندما تسحب البطاقة الأولى ستصبح نقاط البطاقات التي لديك كما يلي: $6, 3, 9, 6, 3, 4$. بعد ذلك يمكنك اختيار التخلص من بطاقات لها نفس النقاط مرةً واحدةً (1)، والطريقة الأفضل هي أن تختار التخلص من بطاقتين (2) نقاط كل منهما تساوي $6$، لكي يكون مجموع نقاط البطاقات المتبقية أصغر ما يمكن ويساوي $3 + 9 + 3 + 4 = 19$.

الحالة $k = 2$: إذا كان بإمكانك سحب بطاقتين (2) من الطاولة، فالطريقة الأفضل هي: بعد سحب البطاقة الأولى التي تساوي نقاطها $4$، تختار التخلص من بطاقة واحدة نقاطها تساوي $9$، فتكون البطاقات المتبقية في اليد بنقاط $6, 3, 6, 3, 4$. ثم عند سحب البطاقة الثانية (2) التي تساوي نقاطها $6$، ستتمكن من التخلص من 3 بطاقات نقاطها تساوي $6$، مما يجعل مجموع نقاط البطاقات المتبقية أصغر ما يمكن ويساوي $3 + 3 + 4 = 10$.

الحالة $k = 3$: إذا كان بإمكانك سحب 3 بطاقات من الطاولة، فالطريقة الأفضل هي: عندما تسحب البطاقة الأولى ستكون نقاط البطاقات في يدك هي $6, 3, 9, 6, 3, 4$. بعد ذلك تختار التخلص من بطاقات لها نفس النقاط مرةً واحدةً (1)، والطريقة الأفضل هي التخلص من البطاقتين (2) اللتين نقاطهما تساوي $3$، فيتبقى في اليد البطاقات $6, 9, 6, 4$. ثم عند سحب البطاقة الثانية (2) التي تساوي نقاطها $6$، ستتمكن من التخلص من 3 بطاقات نقاطها تساوي $6$، فيتبقى في اليد البطاقتان $9, 4$. وعندما تسحب في المرة الثالثة (3) بطاقةً نقاطها تساوي $9$، ستتمكن من التخلص من كلتا البطاقتين (2) اللتين نقاطهما تساوي $9$، مما يجعل مجموع نقاط البطاقات المتبقية يساوي $4$.

الحالة $k = 4$: إذا كان بإمكانك سحب 4 بطاقات من الطاولة، فالطريقة الأفضل هي: بعد سحب البطاقة الأولى التي تساوي نقاطها $4$، تختار التخلص من بطاقة واحدة نقاطها تساوي $4$، فيتبقى في اليد بطاقات نقاطها $6, 3, 9, 6, 3$. ثم في السحبة الثانية (2) تكون البطاقة بنقاط تساوي $6$، والطريقة الأفضل هي التخلص من البطاقتين (2) اللتين نقاطهما تساوي $3$، فيتبقى في اليد $6, 9, 6, 6$. وفي السحبة الثالثة (3) تكون البطاقة بنقاط تساوي $9$، فتختار التخلص من البطاقتين (2) اللتين نقاطهما تساوي $9$. وعند سحب البطاقة الأخيرة التي تساوي نقاطها $6$، ستتمكن من التخلص من 4 بطاقات نقاطها تساوي $6$. ويؤدي هذا التخلص إلى عدم بقاء أي بطاقة في اليد، مما يعني أن مجموع نقاط البطاقات هو $0$.

مهمتك (Your Task)

أوجد «أصغر مجموع لنقاط البطاقات المتبقية في اليد» بعد انتهاء $k$ جولات عندما $k = 1, 2, 3, \ldots, M$.

تتميز هذه المسألة بنمط كتابة برنامج يختلف عن النمط المعتاد، وهو النمط المستخدم في المسابقة الفعلية. يُرجى مراجعة نهاية هذه المسألة لمعرفة طريقة الاستخدام.

تفاصيل التنفيذ

يجب عليك كتابة الدالة التالية:

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

حيث المعاملات هي:

• $A$ هي مصفوفة طولها $N$ تحدد أرقام البطاقات في اليد في البداية.
• $B$ هي مصفوفة طولها $M$ تحدد أرقام البطاقات الموضوعة على الطاولة مرتبةً من اليسار إلى اليمين.
• يجب أن تُرجع هذه الدالة مصفوفةً $C$ طولها $M$ تمثل أصغر مجموع ممكن لنقاط البطاقات في اليد بعد $k$ جولات عندما $k = 1, 2, 3, \ldots, M$.

على سبيل المثال، إذا كانت $A = [6, 3, 9, 6, 3]$ و $B = [4, 6, 9, 6]$، فيجب أن تُرجع الدالة المصفوفة $[19, 10, 4, 0]$.

القيود

• $1 \le N, M \le 10^6$
• $1 \le A[i] \le 10^9$ لكل $i$ حيث $1 \le i \le N$
• $1 \le B[i] \le 10^9$ لكل $i$ حيث $1 \le i \le M$

المهام الفرعية

ملاحظة

إرشادات كتابة البرنامج

في هذه المسألة، تختلف طريقة كتابة البرنامج وإرساله إلى نظام التقييم (Grader) عن النمط العام لكتابة البرامج الذي يتطلب من المتسابق كتابة جزء قراءة المدخلات وجزء طباعة المخرجات. ففي هذه المسألة، يتعين على المتسابق كتابة جزء الحسابات اللازمة فقط داخل الدالة المحددة، حيث تكون بيانات الإدخال المختلفة متاحةً عبر معاملات الدالة، ويجب إرجاع نتائج الحساب عبر الدالة أيضًا، دون أن يضطر المتسابق إلى كتابة جزء قراءة المدخلات أو جزء طباعة المخرجات.

سيحصل المتسابق على عدة ملفات كما يلي، وعليه تعديل ملف واحد فقط حسبما تحدده المسألة وإرسال ذلك الملف إلى النظام:

• grader.cpp هو الملف الرئيسي المسؤول عن استقبال المدخلات وإخراج النتائج.
• kang.cpp هو الملف الذي يجب على المتسابق كتابة العمليات الحسابية المختلفة فيه وهو الملف الذي يرسله المتسابق إلى النظام (يُمنع وجود الدالة main() في الملف kang.cpp، ولكن يُسمح بوجود دوال أخرى).
• run_cpp.sh هو الملف الذي يمكن للمتسابق استدعاؤه لتشغيل البرنامج بالكامل.
• compile_cpp.sh هو الملف الذي يمكن للمتسابق استدعاؤه لترجمة (تجميع) البرنامج.

سيحصل المتسابق على ملف .zip يمكن تنزيله من النظام، وعند فك ضغطه (extract) سيحتوي على الملفات الأربعة (4) جميعها. ينبغي للمتسابق استخدام محرر نصوص (text editor) أو بيئة تطوير متكاملة (IDE) لتعديل الملف kang.cpp، وترجمة البرنامج أو تشغيله عبر استدعاء compile_cpp.sh أو run_cpp.sh.

عندما يستدعي المتسابق الملف run_cpp.sh لتشغيل البرنامج، سيعمل البرنامج وفقًا لما هو محدد في الملف grader.cpp، حيث يشرح قسم «وصف ملف المُقيِّم» آلية عمل ذلك الملف.