路径复原 II

题目描述

你来到了一家无限供应的魔法糖果店。你的背包容量为 $M$。

糖果店共有 $N$ 种糖果，每种糖果的属性如下：

• 重量 $w_i$。
• 美味程度 $v_i$。
• 每种糖果的供应量是无限的。

你希望在不超过背包容量的前提下，获得最大的美味程度总和。

除了最大美味程度，你还需要告诉店主：每种糖果你具体各拿了多少颗，以便店主补货。

如果存在多种获得最大美味程度的方案，请输出使糖果编号序列（按选取的糖果编号排列，如 1 1 2 3）字典序最小的方案。这等价于：在保证最大美味程度的前提下，尽可能多地拿编号较小的糖果。

输入格式

第一行包含两个整数 $N$ 和 $M$，分别表示糖果种类和背包容量。

接下来的 $N$ 行，每行包含两个整数 $w_i$ 和 $v_i$，表示第 $i$ 种糖果的重量和美味程度。

输出格式

第一行输出一个整数，表示最大美味程度。

接下来的 $N$ 行，每行输出一个整数，第 $i$ 行表示第 $i$ 种糖果被选取的颗数。

输入输出样例 #1

输入 #1

3 10
2 5
3 8
4 10

输出 #1

26
2
2
0

样例 1 说明

最大美味程度 26：

• 方案 1：2 颗糖果 1（重 4，值 10）+ 2 颗糖果 2（重 6，值 16）= 重 10，值 26。每种数量：2, 2, 0。
• 方案 2：1 颗糖果 2（重 3，值 8）+ 1 颗糖果 3（重 4，值 10）+ 1 颗糖果 1（重 2，值 5）... 值不够。
• 其他组合无法达到 26。

数据范围

对于 $100\%$ 的数据，$1 \le N \le 100$，$1 \le M \le 1000$，$1 \le w_i, v_i \le 1000$。

建议

三刷