题目描述
有 n 根木棍,第 i 根木棍的长度为 ai。
你可以使用一种切割机器。每次操作时,选择若干根木棍,并指定一个正整数 x。对于每根被选中的、长度为 l 的木棍:
- 若 l≤x,则木棍保持不变;
- 若 l>x,则将其切成两根长度分别为 x 和 l−x 的木棍。
切割后得到的木棍仍然可以继续被切割。
对于每个 k=1,2,…,m,独立考虑恰好进行 k 次操作的情况,求最终最多能得到多少根长度完全相同的木棍。
注意,你只需要让某一种长度相同的木棍尽量多,对于该种数量最多的木棍的长度并没有要求。
即,设最后切割成了 h 根木棍,长度分别是 p1,p2,…,ph,你要最大化
smaxi=1∑h[pi=s].
例如,切割后的长度为 [1,1,2,2,2,3,3,4],答案为 3,因为有 3 根长度为 2 的木棍。
输入格式
第一行包含两个整数 n,m。
第二行包含 n 个整数 a1,a2,…,an。
输出格式
输出一行 m 个整数,表示 k=1,2,…,m 时的答案。
样例 1 输入
5 4
1 2 3 4 4
样例 1 输出
6 14 14 14
样例 1 解释
当 k=1,选择 x=2 切割 [2,3,4,4],变成 [1,2,2,1,2,2,2,2]。
当 k=2,第一次选择 x=2 切割 [2,3,4,4],变成 [1,2,2,1,2,2,2,2];第二次选择 x=1 切割所有长度为 2 的木棍。
样例 2 输入
7 9
1 7 5 1 7 5 3
样例 2 输出
7 17 29 29 29 29 29 29 29
数据范围
对于所有测试数据,保证:1≤n,m≤2×105,1≤ai≤m。
| 测试点 |
n≤ |
m≤ |
特殊性质 |
| 1∼5 |
7 |
无 |
| 6∼8 |
100 |
| 9∼12 |
1000 |
| 13∼15 |
2×105 |
∀i,存在 k 使得 ai=2k |
| 16∼20 |
无 |