لديك $k+1$ كرة متطابقة تمامًا في الشكل والكتلة: $k$ كرات عادية وواحدة سحرية. تريد إيجاد الكرة السحرية للدخول إلى القلعة السحرية.

لا يمكن تمييز الكرة السحرية بالنظر، لكن لديك $M$ أكياس ($M \ge 2$) تساعد في إيجادها، مرقمة من $0$ إلى $M-1$.

تستخدم الأكياس لإيجاد الكرة السحرية كما يأتي.

1. وزع جميع كراتك على الأكياس $M$.

   • يجب وضع كل كرة في أحد الأكياس.
   • يمكن أن تبقى أكياس فارغة.
   • لا يجوز وضع شيء سوى الكرات في الأكياس، ولا يجوز وضع أكياس داخلها.

2. ردد تعويذة.

3. فور ترديد التعويذة:

   • تختفي جميع الكرات الموجودة في الأكياس التي لا تحتوي على الكرة السحرية.
   • تحمي الكرة السحرية الكرات الموجودة معها في الكيس فلا تختفي. لكن معالجة الآثار الجانبية للتعويذة تكلف مالًا. إذا كانت الكرة السحرية في الكيس $i$ الذي يحتوي على $j$ كرات، فالتكلفة هي $A[i] \times j+B[i]$ وون ($A[i] \ge 0$، $B[i] \ge 1$).

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

اختر استراتيجية لتوزيع الكرات تقلل التكلفة الإجمالية في أسوأ حالة. أي أوجد أصغر $w$ يتيح إيجاد الكرة السحرية بتكلفة لا تتجاوز $w$ وون، أيًا كانت الكرة السحرية بين الكرات $k+1$.

اكتب دالة تحل هذه المسألة لكل $k$ من $0$ إلى $N-1$.

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

نفذ الدالة التالية.

vector<long long> find_minimum_costs(int N, vector<int> A, vector<int> B)

• $N$: العدد الأقصى للكرات.
• $A,B$: مصفوفتان بطول $M$. لكل $i$ ($0 \le i \le M-1$)، إذا كانت الكرة السحرية في الكيس $i$ المحتوي على $j$ كرات، فالتكلفة هي $A[i] \times j+B[i]$ وون.
• أعد مصفوفة $C$ بطول $N$. لكل $k$ ($0 \le k \le N-1$)، تكون $C[k]$ أقل تكلفة في أسوأ حالة، بالوون، لإيجاد الكرة السحرية بين $k$ كرات عادية وواحدة سحرية.

يجب ألا ينفذ أي جزء من الشيفرة المقدمة دوال إدخال أو إخراج.

أمثلة

أمثلة 1

لننظر في الحالة $N=3$, $M=2$, $A=[1,3]$, $B=[2,1]$.

يستدعي برنامج التقييم الدالة كما يأتي.

find_minimum_costs(3, {1, 3}, {2, 1})

عندما $k=0$، تكون الكرة الوحيدة سحرية، ويمكن إيجادها بتكلفة $0$ وون.

عندما $k=1$، نضع كرة في كل كيس. إذا كانت السحرية في الكيس $0$ فالتكلفة $A[0] \times 1+B[0]=1 \times 1+2=3$ وون، وإذا كانت في الكيس $1$ فالتكلفة $A[1] \times 2+B[1]=3 \times 1+1=4$ وون. إذن أسوأ تكلفة هي $4$ وون.

عندما $k=2$، يمكن استخدام الاستراتيجية التالية، وللتسهيل نسمي الكرات $X,Y,Z$.

• نضع $X,Z$ في الكيس $0$ و$Y$ في الكيس $1$، ثم نردد التعويذة.

  • إذا كانت السحرية في الكيس $0$ فالتكلفة $A[0] \times 2+B[0]=1 \times 2+2=4$ وون ولا تبقى إلا $X,Z$. ثم نضع $Z$ في الكيس $0$ و$X$ في الكيس $1$ ونردد التعويذة.

    • إذا كانت السحرية في الكيس $0$ فالتكلفة $A[0] \times 1+B[0]=1 \times 1+2=3$ وون ولا تبقى إلا $Z$.

    • إذا كانت السحرية في الكيس $1$ فالتكلفة $A[1] \times 1+B[1]=3 \times 1+1=4$ وون ولا تبقى إلا $X$.

  • إذا كانت السحرية في الكيس $1$ فالتكلفة $A[1] \times 1+B[1]=3 \times 1+1=4$ وون ولا تبقى إلا $Y$.

في هذه الاستراتيجية، التكلفة الإجمالية $4+4=8$ وون إذا كانت $X$ سحرية، و$4$ إذا كانت $Y$، و$4+3=7$ إذا كانت $Z$. لذا فإن أسوأ تكلفة هي $8$ وون.

يجب أن تعيد الدالة $[0,4,8]$.

أمثلة 2

لننظر في الحالة $N=13$, $M=2$, $A=[1,3]$, $B=[2,1]$.

يستدعي برنامج التقييم الدالة كما يأتي.

find_minimum_costs(13, {1, 3}, {2, 1})

يجب أن تعيد الدالة $[0,4,8,11,13,17,18,20,24,25,27,29,30]$.

أمثلة 3

لننظر في الحالة $N=12$, $M=3$, $A=[5,3,0]$, $B=[1,4,6]$.

يستدعي برنامج التقييم الدالة كما يأتي.

find_minimum_costs(12, {5, 3, 0}, {1, 4, 6})

يجب أن تعيد الدالة $[0,6,7,12,13,16,17,18,19,20,22,23]$.

القيود

• $2 \le N \le 1\,000\,000$
• $2 \le M \le 100\,000$
• $0 \le A[i] \le 10^9$ (لكل $0 \le i \le M-1$).
• $1 \le B[i] \le 10^9$ (لكل $0 \le i \le M-1$).

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

1. ($3$ نقطة) $A[0]=A[1]=\cdots=A[M-1]$, $B[0]=B[1]=\cdots=B[M-1]$.
2. ($4$ نقطة) $N \le 5\,000$, $M=2$.
3. ($7$ نقطة) $M=2$.
4. ($12$ نقطة) $A[i]=0$, $B[i] \le 1\,000$ (لكل $0 \le i \le M-1$).
5. ($25$ نقطة) $N \le 10\,000$, $M \le 10$.
6. ($17$ نقطة) $M \le 100$.
7. ($32$ نقطة) لا توجد قيود إضافية.

برنامج التقييم النموذجي

صيغة إدخال برنامج التقييم النموذجي كما يأتي.

• السطر $1$: $N$ $M$
• السطر $2+i$ ($0 \le i \le M-1$): $A[i]$ $B[i]$

صيغة إخراج برنامج التقييم النموذجي كما يأتي.

• السطر $1+k$ ($0 \le k \le N-1$): $C[k]$