题目描述

大博物馆刚刚宣布将举办一场关于世界各地珠宝的大型展览。世界闻名的窃贼、犯罪大师 Edward Terrenando 希望借此机会，完成他职业生涯中的盗窃巅峰之作，以期未来繁荣昌盛。

Edward 计划从大博物馆的展览中盗取大量珠宝。但唉！他必须谨慎选择要盗取的珠宝，以最大化被盗珠宝的总价值。

Edward 有 $k$ 个背包，容量分别为 $1, 2, 3, \dots, k$，他想知道每个容量下能盗取珠宝的最大总价值。这样他可以在决定盗取多少珠宝时，恰当地权衡风险与回报。容量为 $s$ 的背包可以装载物品，当且仅当这些物品的尺寸之和小于或等于 $s$。如果你能计算出每个背包容量下的最佳珠宝总价值，你就能帮助 Edward 完成世纪大劫案！

输入格式

每个输入包含单个测试用例。请注意，你的程序可能会在不同输入上多次运行。输入的第一行包含两个空格分隔的整数 $n$ 和 $k$，其中 $n$（$1 \leq n \leq 1{,}000{,}000$）是展览中珠宝的数量，$k$（$1 \leq k \leq 100{,}000$）是 Edward 可用的最大背包容量。接下来的 $n$ 行，每行描述一件珠宝。每行包含两个空格分隔的整数 $s$ 和 $v$，其中 $s$（$1 \leq s \leq 300$）是珠宝的尺寸，$v$（$1 \leq v \leq 10^9$）是其价值。每件珠宝在每个背包中只能被取一次，但每个背包的问题是独立的。

输出格式

输出 $k$ 个整数，用空格分隔。第一个整数应为容量为 $1$ 的背包能装入的最大珠宝价值，第二个整数应为容量为 $2$ 的背包能装入的最大珠宝价值，依此类推。

4 9
2 8
1 1
3 4
5 100

1 8 9 9 100 101 108 109 109

5 7
2 2
3 8
2 7
2 4
3 8

0 7 8 11 15 16 19

2 6
300 1
300 2

0 0 0 0 0 0

提示

翻译由 DeepSeek V3.2 完成