Vous avez $k+1$ billes de forme et de masse exactement identiques : $k$ ordinaires et une magique. Vous voulez trouver la bille magique pour entrer dans le château magique.

On ne peut pas les distinguer à l’œil nu, mais vous disposez de $M$ sacs ($M \ge 2$) qui peuvent aider à la trouver, numérotés de $0$ à $M-1$.

Les sacs s’utilisent comme suit.

1. Répartissez toutes vos billes entre les $M$ sacs.

   • Chaque bille doit être placée dans un sac.
   • Des sacs peuvent rester vides.
   • Les sacs ne peuvent contenir que des billes, pas d’autres sacs.

2. Prononcez une formule magique.

3. Immédiatement après :

   • Toutes les billes des sacs sans la bille magique disparaissent.
   • Les billes du sac contenant la bille magique sont protégées et ne disparaissent pas. Mais réparer les effets secondaires du sort coûte de l’argent. Si la bille magique était dans le sac $i$ contenant $j$ billes, le coût est de $A[i] \times j+B[i]$ wons ($A[i] \ge 0$, $B[i] \ge 1$).

La bille magique ne disparaît jamais. Répéter ce processus jusqu’à ce qu’il ne reste qu’une bille permet donc de la trouver.

Choisissez une stratégie de répartition minimisant le coût total dans le pire cas. Autrement dit, trouvez le plus petit $w$ permettant de trouver la bille magique pour au plus $w$ wons, quelle que soit la bille magique parmi les $k+1$ billes.

Écrivez une fonction résolvant ce problème pour tout $k$ de $0$ à $N-1$.

Détails d'implémentation

Implémentez la fonction suivante.

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

• $N$ : nombre maximal de billes.
• $A,B$ : tableaux de longueur $M$. Pour tout $i$ ($0 \le i \le M-1$), si la bille magique se trouve dans le sac $i$ contenant $j$ billes, le coût est de $A[i] \times j+B[i]$ wons.
• Renvoyez un tableau $C$ de longueur $N$. Pour tout $k$ ($0 \le k \le N-1$), $C[k]$ est le coût minimal dans le pire cas, en wons, pour trouver la bille magique parmi $k$ billes ordinaires et une magique.

Aucune partie du code soumis ne doit exécuter de fonction d’entrée/sortie.

Exemples

Exemples 1

Considérons le cas $N=3$, $M=2$, $A=[1,3]$, $B=[2,1]$.

Le programme d’évaluation appelle la fonction ainsi.

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

Pour $k=0$, la seule bille est magique et peut être trouvée pour $0$ won.

Pour $k=1$, placez une bille dans chaque sac. Si la bille magique est dans le sac $0$, le coût est de $A[0] \times 1+B[0]=1 \times 1+2=3$ wons ; dans le sac $1$, il est de $A[1] \times 2+B[1]=3 \times 1+1=4$ wons. Le pire coût est donc de $4$ wons.

Pour $k=2$, utilisez la stratégie suivante, en appelant les billes $X,Y,Z$.

• Placez $X,Z$ dans le sac $0$ et $Y$ dans le sac $1$, puis prononcez la formule.

  • Si la bille magique est dans le sac $0$, le coût est de $A[0] \times 2+B[0]=1 \times 2+2=4$ wons et seules $X,Z$ restent. Placez alors $Z$ dans le sac $0$ et $X$ dans le sac $1$, puis prononcez la formule.

    • Si la bille magique est dans le sac $0$, le coût est de $A[0] \times 1+B[0]=1 \times 1+2=3$ wons et seule $Z$ reste.

    • Si la bille magique est dans le sac $1$, le coût est de $A[1] \times 1+B[1]=3 \times 1+1=4$ wons et seule $X$ reste.

  • Si la bille magique est dans le sac $1$, le coût est de $A[1] \times 1+B[1]=3 \times 1+1=4$ wons et seule $Y$ reste.

Cette stratégie coûte au total $4+4=8$ wons si $X$ est magique, $4$ si c’est $Y$, et $4+3=7$ si c’est $Z$. Le pire coût est donc de $8$ wons.

La fonction doit renvoyer $[0,4,8]$.

Exemples 2

Considérons le cas $N=13$, $M=2$, $A=[1,3]$, $B=[2,1]$.

Le programme d’évaluation appelle la fonction ainsi.

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

La fonction doit renvoyer $[0,4,8,11,13,17,18,20,24,25,27,29,30]$.

Exemples 3

Considérons le cas $N=12$, $M=3$, $A=[5,3,0]$, $B=[1,4,6]$.

Le programme d’évaluation appelle la fonction ainsi.

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

La fonction doit renvoyer $[0,6,7,12,13,16,17,18,19,20,22,23]$.

Contraintes

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

Sous-tâches

1. ($3$ points) $A[0]=A[1]=\cdots=A[M-1]$, $B[0]=B[1]=\cdots=B[M-1]$.
2. ($4$ points) $N \le 5\,000$, $M=2$.
3. ($7$ points) $M=2$.
4. ($12$ points) $A[i]=0$, $B[i] \le 1\,000$ (pour tout $0 \le i \le M-1$).
5. ($25$ points) $N \le 10\,000$, $M \le 10$.
6. ($17$ points) $M \le 100$.
7. ($32$ points) Aucune contrainte supplémentaire.

Programme d’évaluation d’exemple

Le format d’entrée du programme d’évaluation d’exemple est le suivant.

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

Le format de sortie du programme d’évaluation d’exemple est le suivant.

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