场景：传奇的萨格勒布酒馆 Kod Žnidaršića。

时间：1936 年。

Franjo 和他的朋友们正在吧台旁享受着美酒，同时讨论着阿比西尼亚（Abyssinia）的时事。他的儿子，小 Perica，正坐在酒吧角落的一张小桌子旁。Perica 面前有 $N$ 个杯子，编号为 $1$ 到 $N$。每个杯子的容量（单位：纳升）以及当前杯中的液体量都是已知的。

小 Perica 想知道，通过在杯子之间倾倒液体，最多可以使多少个杯子变空。他可以随意将任意整数纳升的液体从一个杯子倒入另一个杯子，次数不限，只要液体不溢出即可。

你的任务是输出空杯子的最大数量，以及所有杯子中液体的一种可能最终配置。如果有多种配置可以得到相同数量的空杯子，输出其中任意一种即可。注意，不需要最小化杯子之间倒液体的次数。

输入格式

第一行包含一个整数 $N$ ($1 \le N \le 1\,000$)，表示杯子的数量。

接下来的 $N$ 行，每行包含两个整数 $T_i$ ($0 \le T_i \le 10^9$) 和 $Z_i$ ($1 \le Z_i \le 10^9$)，分别表示第 $i$ 个杯子中当前的液体量和它的容量。两个数值的单位均为纳升，且当前液体量不会超过杯子的容量，即 $T_i \le Z_i$ 成立。

输出格式

第一行输出通过在杯子之间倒液体所能得到的最大空杯子数量。

第二行输出在 Perica 完成必要的倾倒操作后，每个杯子中的液体量。杯子应按编号 $1$ 到 $N$ 的顺序输出。

子任务

对于每个测试用例，正确输出第一行得 4 分，正确输出第二行得 1 分。

在价值 20 分的测试用例中，所有杯子的容量都相同。

样例

输入样例 1

5
2 6
1 6
0 6
6 6
5 6

输出样例 1

2
6 6 2 0 0

输入样例 2

5
4 5
2 7
5 5
0 10
7 9

输出样例 2

3
0 0 0 10 8

输入样例 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

说明

第二个样例的一种可能倾倒方案如下：

1. 将杯子 1 中的所有液体倒入杯子 2。
2. 将杯子 2 中的所有液体倒入杯子 4。
3. 将杯子 3 中的 4 纳升液体倒入杯子 4。
4. 将杯子 3 中的 1 纳升液体倒入杯子 5。

此时，编号为 1、2 和 3 的杯子都变空了。