---

注意事项

在 LibreOJ 上，由于语言限制，目前只支持以下语言的提交：

• C++（标准为 C++ 17 及以上）

请在提交源代码前添加 #include "marbles.h"。

---

题目描述

题目译自 2022년도 국제정보올림피아드 대표학생 선발고사 - 2차 선발고사 T3 「마법 구슬 찾기」

你有 $k+1$ 颗外观和质量完全相同的珠子，其中 $k$ 颗是普通珠子，$1$ 颗是魔法珠子。你需要找到这颗魔法珠子，才能进入魔法城堡。

虽然无法通过肉眼区分魔法珠子和普通珠子，但你可以使用 $M$ $(M \geq 2)$ 个袋子来找到魔法珠子。袋子编号从 $0$ 到 $M-1$。

找到魔法珠子的步骤如下：

1. 将所有珠子分装到 $M$ 个袋子中。
   • 每个袋子里必须有珠子，不能有空袋子。
   • 袋子里只能装珠子，不能装其他袋子。
2. 念咒语。
3. 念咒语后：
   • 不含魔法珠子的袋子里的珠子会全部消失。
   • 含有魔法珠子的袋子里的珠子会因为魔法珠子的保护而不消失，但需要支付费用。若魔法珠子在第 $i$ 个袋子中，且该袋子里有 $j$ 颗珠子，则费用为 $A[i] \times j + B[i]$ $(A[i] \geq 0, B[i] \geq 1)$ 元。
4. 魔法珠子永远不会消失，因此你可以重复上述步骤，直到只剩下魔法珠子。

你需要制定一个策略，将珠子分装到袋子中，以最小化在最坏情况下找到魔法珠子的费用。也就是说，无论哪颗珠子是魔法珠子，总费用不超过 $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 \leq i \leq M-1)$，若魔法珠子在第 $i$ 个袋子中，且该袋子里有 $j$ 颗珠子，则费用为 $A[i] \times j + B[i]$ 元。
• 该函数返回一个长度为 $N$ 的数组 $C$。对于每个 $k$ $(0 \leq k \leq 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$ 时，可以将两颗珠子分别放入两个袋子。若魔法珠子在第 $0$ 个袋子中，费用为 $A[0] \times 1 + B[0] = 1 \times 1 + 2 = 3$ 元；若魔法珠子在第 $1$ 个袋子中，费用为 $A[1] \times 1 + B[1] = 3 \times 1 + 1 = 4$ 元。因此，最坏情况下费用为 $4$ 元。

• 当 $k=2$ 时，可以采用以下策略。假设三颗珠子分别为 $X$, $Y$, $Z$。

  1. 将 $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 \leq N \leq 10^6$
• $2 \leq M \leq 10^5$
• 对于所有 $i$ $(0 \leq i \leq M-1)$，$0 \leq A[i] \leq 10^{9}$
• 对于所有 $i$ $(0 \leq i \leq M-1)$，$1 \leq B[i] \leq 10^{9}$

详细子任务附加限制及分值如下表所示。

子任务	分值	附加限制
1	3	$A[0]=A[1]=\cdots=A[M-1]$, $B[0]=B[1]=\cdots=B[M-1]$
2	4	$N \leq 5000$, $M=2$
3	7	$M=2$
4	12	对于所有 $i$ $(0 \leq i \leq M-1)$，$A[i]=0$, $B[i] \leq 1000$
5	25	$N \leq 10000$, $M \leq 10$
6	17	$M \leq 100$
7	32	无附加限制

---

示例评测程序

示例评测程序按以下格式读取输入：

第 1 行：N M
第 2+i (0 ≤ i ≤ M-1) 行：A[i] B[i]

示例评测程序的输出格式如下：

第 1+k (0 ≤ k ≤ N-1) 行：C[k]