形と質量が完全に同じ $k+1$ 個のビー玉を持っている。$k$ 個は普通で、1個は魔法のビー玉である。魔法の城に入るため、そのビー玉を見つけたい。

見た目では区別できないが、探すのに使える $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$）である。

魔法のビー玉は決して消滅しないため、1個だけ残るまでこの操作を繰り返せば見つけられる。

袋への分け方の戦略を立て、最悪の場合の総費用を最小にしたい。つまり、$k+1$ 個のうちどれが魔法のビー玉でも、合計 $w$ ウォン以下で見つけられる最小の $w$ を求めたい。

$0$ 以上 $N-1$ 以下のすべての $k$ に対してこの問題を解く関数を作成せよ。

実装の詳細

以下の関数を実装せよ。

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$）について、魔法のビー玉が $j$ 個のビー玉を含む $i$ 番の袋にあると、費用は $A[i] \times j+B[i]$ ウォンである。
• 長さ $N$ の配列 $C$ を返すこと。すべての $k$（$0 \le k \le N-1$）について、$C[k]$ は普通のビー玉 $k$ 個と魔法のビー玉1個があるときの、最悪の場合に見つけるための最小費用（ウォン）である。

提出するソースコードのどの部分でも入出力関数を実行してはならない。

入出力例

入出力例 1

次の場合を考える。 $N=3$, $M=2$, $A=[1,3]$, $B=[2,1]$.

グレーダは次のように関数を呼び出す。

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

$k=0$ では唯一のビー玉が魔法なので、費用 $0$ ウォンで見つけられる。

$k=1$ では各袋に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$ では次の戦略を使える。便宜上3個を $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$ だけが残る。

この戦略では、魔法のビー玉が $X$ なら合計 $4+4=8$ ウォン、$Y$ なら $4$ ウォン、$Z$ なら $4+3=7$ ウォンかかるため、最悪の費用は $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]$