题目描述
Per前面有N个玻璃杯,编号从 1 到 N。已知每个玻璃杯的体积(以纳升为单位)和当前杯中酒的体积。 问题:Per 想知道通过杯子若干次互倒后,最多可以清空多少个玻璃杯。互倒时保证液体不溢出,同时倒酒的数量是一个整数,倒酒次数不限。 输出最多清空的杯子数,和一种可能的最后状态。
输入格式
第一行包含来自任务描述的整数 N (1 ≤ N ≤ 1 000)。
接下来的 N 行中的每一行都包含两个整数 Ti (0 ≤ Ti ≤ $10^9$) 和 Zi (1 ≤ Zi ≤ $10^9$),依次表示当前第 i 个玻璃杯中的液体量及其杯子体积。 单位为纳升,当前液体量不能大于玻璃的体积,即 Ti ≤ Zi。
输出格式
在第一行中,您应该输出通过倾倒液体可以清空的最大玻璃杯数量。
在第二行中,您应该在 Perica 执行后输出每个玻璃杯中的液体量注意: 玻璃杯应从编号 1 的玻璃杯到编号为 N 的玻璃。
样例 #1
样例输入 #1
5
2 6
1 6
0 6
6 6
5 6
样例输出 #1
2
6 6 2 0 0
样例 #2
样例输入 #2
5
4 5
2 7
5 5
0 10
7 9
样例输出 #2
3
0 0 0 10 8
样例 #3
样例输入 #3
8
2 6
3 4
1 1
9 10
0 10
4 5
6 8
3 9
样例输出 #3
5
0 0 0 9 10 0 0 9
提示
第一行写得正确得 4 分,第二行写得正确每行得 1 分 测试用例。
20% 的测试用例中,所有杯子的体积相同。
第二个示例的说明:一种可能的倒酒方法如下:
将玻璃 1 中的所有东西倒入玻璃 2。
将玻璃 2 中的所有东西倒入玻璃 4。
将 4 纳升从玻璃 3 倒入玻璃 4。
将 1 纳升从玻璃 3 倒入玻璃 5。
编号为 1、2 和 3 的杯子现在是空的。