Du hast $k+1$ Murmeln mit genau gleicher Form und Masse: $k$ gewöhnliche und eine magische. Du möchtest die magische Murmel finden, um das magische Schloss zu betreten.

Mit bloßem Auge ist sie nicht zu unterscheiden, aber du hast $M$ Beutel ($M \ge 2$), die bei der Suche helfen. Sie sind von $0$ bis $M-1$ nummeriert.

Die Beutel werden folgendermaßen verwendet.

1. Verteile alle deine Murmeln auf die $M$ Beutel.

   • Jede Murmel muss in einem Beutel liegen.
   • Beutel dürfen leer bleiben.
   • Beutel dürfen nur Murmeln und keine anderen Beutel enthalten.

2. Sprich einen Zauberspruch.

3. Unmittelbar danach:

   • Alle Murmeln in Beuteln ohne die magische Murmel verschwinden.
   • Die Murmeln im Beutel mit der magischen Murmel werden geschützt und verschwinden nicht. Die Nebenwirkungen des Zaubers zu beheben kostet jedoch Geld. Liegt die magische Murmel im Beutel $i$, der $j$ Murmeln enthält, kostet dies $A[i] \times j+B[i]$ Won ($A[i] \ge 0$, $B[i] \ge 1$).

Die magische Murmel verschwindet nie. Wiederholt man den Vorgang, bis nur eine Murmel übrig ist, findet man sie.

Wähle eine Verteilungsstrategie, die die Gesamtkosten im schlimmsten Fall minimiert. Gesucht ist also das kleinste $w$, sodass die magische Murmel für höchstens $w$ Won gefunden werden kann, unabhängig davon, welche der $k+1$ Murmeln magisch ist.

Schreibe eine Funktion, die dies für alle $k$ von $0$ bis $N-1$ löst.

Implementierungsdetails

Implementiere die folgende Funktion.

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

• $N$: die maximale Anzahl der Murmeln.
• $A,B$: Arrays der Länge $M$. Für alle $i$ ($0 \le i \le M-1$) gilt: Ist die magische Murmel im Beutel $i$ mit $j$ Murmeln, betragen die Kosten $A[i] \times j+B[i]$ Won.
• Gib ein Array $C$ der Länge $N$ zurück. Für alle $k$ ($0 \le k \le N-1$) ist $C[k]$ der kleinste Aufwand im schlimmsten Fall in Won, um die magische Murmel unter $k$ gewöhnlichen und einer magischen Murmel zu finden.

Dein eingereichter Quelltext darf an keiner Stelle Ein-/Ausgabefunktionen ausführen.

Beispiele

Beispiele 1

Betrachte den Fall $N=3$, $M=2$, $A=[1,3]$, $B=[2,1]$.

Der Grader ruft die Funktion wie folgt auf.

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

Für $k=0$ ist die einzige Murmel magisch; sie kann für $0$ Won gefunden werden.

Für $k=1$ lege je eine Murmel in jeden Beutel. Ist die magische in Beutel $0$, kostet dies $A[0] \times 1+B[0]=1 \times 1+2=3$ Won; ist sie in Beutel $1$, kostet es $A[1] \times 2+B[1]=3 \times 1+1=4$ Won. Im schlimmsten Fall kostet es $4$ Won.

Für $k=2$ verwende die folgende Strategie und nenne die drei Murmeln $X,Y,Z$.

• Lege $X,Z$ in Beutel $0$ und $Y$ in Beutel $1$ und sprich den Zauber.

  • Ist die magische Murmel in Beutel $0$, kostet dies $A[0] \times 2+B[0]=1 \times 2+2=4$ Won und nur $X,Z$ bleiben. Lege nun $Z$ in Beutel $0$ und $X$ in Beutel $1$ und sprich den Zauber.

    • Ist die magische Murmel in Beutel $0$, kostet dies $A[0] \times 1+B[0]=1 \times 1+2=3$ Won und nur $Z$ bleibt.

    • Ist die magische Murmel in Beutel $1$, kostet dies $A[1] \times 1+B[1]=3 \times 1+1=4$ Won und nur $X$ bleibt.

  • Ist die magische Murmel in Beutel $1$, kostet dies $A[1] \times 1+B[1]=3 \times 1+1=4$ Won und nur $Y$ bleibt.

Mit dieser Strategie betragen die Gesamtkosten $4+4=8$ Won für eine magische $X$, $4$ Won für $Y$ und $4+3=7$ Won für $Z$. Somit kostet es im schlimmsten Fall $8$ Won.

Die Funktion muss zurückgeben $[0,4,8]$.

Beispiele 2

Betrachte den Fall $N=13$, $M=2$, $A=[1,3]$, $B=[2,1]$.

Der Grader ruft die Funktion wie folgt auf.

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

Die Funktion muss zurückgeben $[0,4,8,11,13,17,18,20,24,25,27,29,30]$.

Beispiele 3

Betrachte den Fall $N=12$, $M=3$, $A=[5,3,0]$, $B=[1,4,6]$.

Der Grader ruft die Funktion wie folgt auf.

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

Die Funktion muss zurückgeben $[0,6,7,12,13,16,17,18,19,20,22,23]$.

Beschränkungen

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

Teilaufgaben

1. ($3$ Punkte) $A[0]=A[1]=\cdots=A[M-1]$, $B[0]=B[1]=\cdots=B[M-1]$.
2. ($4$ Punkte) $N \le 5\,000$, $M=2$.
3. ($7$ Punkte) $M=2$.
4. ($12$ Punkte) $A[i]=0$, $B[i] \le 1\,000$ (für alle $0 \le i \le M-1$).
5. ($25$ Punkte) $N \le 10\,000$, $M \le 10$.
6. ($17$ Punkte) $M \le 100$.
7. ($32$ Punkte) Keine zusätzlichen Beschränkungen.

Beispielgrader

Das Eingabeformat des Beispielgraders lautet wie folgt.

• Zeile $1$: $N$ $M$
• Zeile $2+i$ ($0 \le i \le M-1$): $A[i]$ $B[i]$

Das Ausgabeformat des Beispielgraders lautet wie folgt.

• Zeile $1+k$ ($0 \le k \le N-1$): $C[k]$