← 返回题目列表

Codeforces · 1607/G

G. 宴会准备1

中文机器翻译题面 查看原题

一位知名厨师准备了 $$$n$$$ 菜肴:第 $$$i$$$ 菜肴由 $$$a_i$$$ 克鱼和 $$$b_i$$$ 克肉组成。

宴会组织者估算 $$$n$$$ 菜品的余额如下。平衡等于鱼的总质量与肉的总质量之差的绝对值。

从技术上讲,余额等于 $$$\left|\sum\limits_{i=1}^n a_i - \sum\limits_{i=1}^n b_i\right|$$$。余额越小越好。

为了提高平衡性,请了品尝师。他会吃掉每道菜中的 $$$m$$$ 克食物。对于每道菜,品尝者分别决定他要吃多少鱼和多少肉。唯一的条件是他必须吃掉每道菜总共 $$$m$$$ 克。

确定品尝者应该从每道菜中吃多少类型的食物,以使平衡值尽可能最小。如果有多个正确答案,您可以选择其中一个。

输入

输入数据的第一行包含一个整数 $$$t$$$ ($$$1 \leq t \leq 10^4$$$) — 测试用例的数量。

每个测试用例的描述前面都有一个空行。接下来是包含整数 $$$n$$$ 和 $$$m$$$ 的行($$$1 \leq n \leq 2 \cdot 10^5$$$; $$$0 \leq m \leq 10^6$$$)。接下来的 $$$n$$$ 行描述菜肴,其中第 $$$i$$$ 包含一对整数 $$$a_i$$$ 和 $$$b_i$$$ ($$$0 \leq a_i, b_i \le 10^6$$$) — 第 $$$i$$$ 菜肴中的鱼和肉的质量。

保证每道菜可以吃$$$m$$$克食物。换句话说,$$$m \leq a_i+b_i$$$ 对于从 $$$1$$$ 到 $$$n$$$ 的所有 $$$i$$$ 包括在内。

测试中所有测试用例的所有 $$$n$$$ 值的总和不超过 $$$2 \cdot 10^5$$$。

输出

对于每个测试用例,在第一行打印通过吃每道菜中 $$$m$$$ 克食物可以达到的最小平衡值。

然后打印 $$$n$$$ 行来描述执行此操作的方法:第 $$$i$$$ 行应包含两个整数 $$$x_i$$$ 和 $$$y_i$$$ ($$$0 \leq x_i \leq a_i$$$; $$$0 \leq y_i \leq b_i$$$; $$$x_i+y_i=m$$$),其中 $$$x_i$$$ 是品尝者应从第 $$$i$$$ 餐中吃多少克鱼,$$$y_i$$$ 是多少克肉。

如果有多种方法可以实现最小平衡,请找到其中任何一种。

示例

输入 #1

8

1 5
3 4

1 6
3 4

2 2
1 3
4 2

2 4
1 3
1 7

3 6
1 7
1 8
1 9

3 6
1 8
1 9
30 10

3 4
3 1
3 2
4 1

5 4
0 7
6 4
0 8
4 1
5 3

输出 #1

0
2 3
1
3 3
0
1 1
1 1
2
1 3
0 4
3
0 6
0 6
0 6
7
1 5
1 5
6 0
0
3 1
3 1
3 1
0
0 4
2 2
0 4
3 1
1 3