Tienes $k+1$ canicas de forma y masa idénticas: $k$ normales y una mágica. Quieres encontrar la canica mágica para entrar al castillo mágico.

No se puede distinguir a simple vista, pero tienes $M$ bolsas ($M \ge 2$) que ayudan a encontrarla, numeradas de $0$ a $M-1$.

Las bolsas se utilizan de la siguiente manera.

1. Reparte todas tus canicas entre las $M$ bolsas.

   • Cada canica debe quedar dentro de alguna bolsa.
   • Puede haber bolsas vacías.
   • Las bolsas solo pueden contener canicas, no otras bolsas.

2. Pronuncia un hechizo.

3. Inmediatamente después del hechizo:

   • Todas las canicas de las bolsas sin la canica mágica desaparecen.
   • Las canicas de la bolsa que contiene la canica mágica quedan protegidas y no desaparecen. Sin embargo, reparar los efectos secundarios del hechizo cuesta dinero. Si la canica mágica estaba en la bolsa $i$, que contenía $j$ canicas, el coste es $A[i] \times j+B[i]$ wones ($A[i] \ge 0$, $B[i] \ge 1$).

La canica mágica nunca desaparece, por lo que repetir el proceso hasta que quede una sola permite encontrarla.

Elige una estrategia de distribución que minimice el coste total en el peor caso. Es decir, encuentra el menor $w$ que permita encontrar la canica mágica gastando como máximo $w$ wones, sin importar cuál de las $k+1$ canicas sea mágica.

Escribe una función que resuelva el problema para todo $k$ de $0$ a $N-1$.

Detalles de implementación

Implementa la siguiente función.

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

• $N$: cantidad máxima de canicas.
• $A,B$: arreglos de longitud $M$. Para todo $i$ ($0 \le i \le M-1$), si la canica mágica está en la bolsa $i$ con $j$ canicas, el coste es $A[i] \times j+B[i]$ wones.
• Devuelve un arreglo $C$ de longitud $N$. Para todo $k$ ($0 \le k \le N-1$), $C[k]$ es el mínimo coste en el peor caso, en wones, de encontrar la canica mágica entre $k$ normales y una mágica.

Ninguna parte del código enviado debe ejecutar funciones de entrada/salida.

Ejemplos

Ejemplos 1

Considera el caso $N=3$, $M=2$, $A=[1,3]$, $B=[2,1]$.

El evaluador llama a la función así.

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

Para $k=0$, la única canica es mágica y puede encontrarse con un coste de $0$ wones.

Para $k=1$, coloca una canica en cada bolsa. Si la mágica está en la bolsa $0$, el coste es $A[0] \times 1+B[0]=1 \times 1+2=3$ wones; si está en la $1$, es $A[1] \times 2+B[1]=3 \times 1+1=4$ wones. El peor coste es $4$ wones.

Para $k=2$, usa la siguiente estrategia, llamando $X,Y,Z$ a las tres canicas.

• Coloca $X,Z$ en la bolsa $0$ y $Y$ en la $1$, y pronuncia el hechizo.

  • Si la mágica está en la bolsa $0$, el coste es $A[0] \times 2+B[0]=1 \times 2+2=4$ wones y solo quedan $X,Z$. Coloca entonces $Z$ en la bolsa $0$ y $X$ en la $1$, y pronuncia el hechizo.

    • Si la mágica está en la bolsa $0$, el coste es $A[0] \times 1+B[0]=1 \times 1+2=3$ wones y solo queda $Z$.

    • Si la mágica está en la bolsa $1$, el coste es $A[1] \times 1+B[1]=3 \times 1+1=4$ wones y solo queda $X$.

  • Si la mágica está en la bolsa $1$, el coste es $A[1] \times 1+B[1]=3 \times 1+1=4$ wones y solo queda $Y$.

Con esta estrategia, el coste total es $4+4=8$ wones si $X$ es mágica, $4$ si lo es $Y$, y $4+3=7$ si lo es $Z$. Por tanto, el peor coste es $8$ wones.

La función debe devolver $[0,4,8]$.

Ejemplos 2

Considera el caso $N=13$, $M=2$, $A=[1,3]$, $B=[2,1]$.

El evaluador llama a la función así.

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

La función debe devolver $[0,4,8,11,13,17,18,20,24,25,27,29,30]$.

Ejemplos 3

Considera el caso $N=12$, $M=3$, $A=[5,3,0]$, $B=[1,4,6]$.

El evaluador llama a la función así.

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

La función debe devolver $[0,6,7,12,13,16,17,18,19,20,22,23]$.

Restricciones

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

Subtareas

1. ($3$ puntos) $A[0]=A[1]=\cdots=A[M-1]$, $B[0]=B[1]=\cdots=B[M-1]$.
2. ($4$ puntos) $N \le 5\,000$, $M=2$.
3. ($7$ puntos) $M=2$.
4. ($12$ puntos) $A[i]=0$, $B[i] \le 1\,000$ (para todo $0 \le i \le M-1$).
5. ($25$ puntos) $N \le 10\,000$, $M \le 10$.
6. ($17$ puntos) $M \le 100$.
7. ($32$ puntos) Sin restricciones adicionales.

Evaluador de ejemplo

El formato de entrada del evaluador de ejemplo es el siguiente.

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

El formato de salida del evaluador de ejemplo es el siguiente.

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