Migrated from Lutece 2401 我来变身

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

不幸的吉田咲欠了很多钱，为了守护她，假面骑士fatdog决定变身成为冒险家，去世界各地寻宝。

他寻得大海的深处有一个洞穴中藏有丰富的秘宝，洞穴内有 $n$ 件宝物，对于宝物 $i$ ，它的所占背包的容量为 $s_i$ 并且价值为 $v_i$。难题来了，他一次只能带一个容量不大于 $k$ 的背包下海，他必须从洞穴中带回尽可能多价值的宝物，求问对于他若一次携带容量为 $1,2,3,..,k$ 的背包，能装回的最大价值为多少。

事态紧急！Emergence!!

Input

第一行包含两个整数 $n$ 和 $k$ ($1\leq n \leq 10^6,~1\leq k \leq 10^5$)

接下来 $n$ 行，每行包含两个整数 $s_i$ 和 $v_i$ ($1\leq s_i \leq300, ~1\leq v_i\leq10^9$)

Output

输出一行 $k$ 个整数，用空格分隔开，第 $i$ 个整数代表容量为 $i$ 时能带回的最大价值为多少。

Samples

4 9
2 8
1 1
3 4
5 100

1 8 9 9 100 101 108 109 109

Resources

2020 UESTC ICPC Training for Dynamic Programming