Logo Universal Online Judge

UOJ

时间限制:1 s 空间限制:512 MB
Statistics

题目描述

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. 将玻璃 1 中的所有东西倒入玻璃 2。

  2. 将玻璃 2 中的所有东西倒入玻璃 4。

  3. 将 4 纳升从玻璃 3 倒入玻璃 4。

  4. 将 1 纳升从玻璃 3 倒入玻璃 5。

编号为 1、2 和 3 的杯子现在是空的。