Banquet Preparations 1

题意翻译

### 题目描述 厨师为一次宴会准备了 $n$ 道菜品，出于某种原因，所有菜品都是由鱼肉和猪肉组成的。第 $i$ 道菜品中包含了 $a_i$ 单位的鱼肉和 $b_i$ 单位的猪肉。 晚宴的主办方定义晚会美食的平衡度为 $|\sum_{i=1}^n\ a_i\ - \ \sum_{i=1}^n\ b_i|$，并且希望这个值越小越好。为了达成这一点，主办方请来了一个吃客。此人会在每道菜中刚好吃下 $m$ 单位的食物，现在请你规划他在每道菜中该吃多少鱼肉，多少猪肉，使得最后的平衡值最小。 ### 输入格式 第一行一个正整数 $T$, 表示测试数据的数量。 对于每组测试数据，第一行两个正整数 $n,\ m$，含义见题意。 之后的 $n$ 行，每行两个数，其中第 $i$ 行的数分别为 $a_i,\ b_i$，含义见题意。 ### 输出格式 对于每组测试数据，输出 $n$ 行，每行两个整数，其中第 $i$ 行的数分别为 $ansa_i,\ ansb_i$，表示吃客应该在第 $i$ 道菜吃下的鱼肉和猪肉的数量。 ### 数据范围 $1\le n \le 2\times 10^5,\ 0\le m\le 10^6$ 保证对于 $\forall i$，满足 $m\le a_i+b_i$

题目描述

A known chef has prepared $ n $ dishes: the $ i $ -th dish consists of $ a_i $ grams of fish and $ b_i $ grams of meat. The banquet organizers estimate the balance of $ n $ dishes as follows. The balance is equal to the absolute value of the difference between the total mass of fish and the total mass of meat. Technically, the balance equals to $ \left|\sum\limits_{i=1}^n a_i - \sum\limits_{i=1}^n b_i\right| $ . The smaller the balance, the better. In order to improve the balance, a taster was invited. He will eat exactly $ m $ grams of food from each dish. For each dish, the taster determines separately how much fish and how much meat he will eat. The only condition is that he should eat exactly $ m $ grams of each dish in total. Determine how much of what type of food the taster should eat from each dish so that the value of the balance is as minimal as possible. If there are several correct answers, you may choose any of them.

输入输出格式

输入格式

The first line of input data contains an integer $ t $ ( $ 1 \leq t \leq 10^4 $ ) — the number of the test cases. Each test case's description is preceded by a blank line. Next comes a line that contains integers $ n $ and $ m $ ( $ 1 \leq n \leq 2 \cdot 10^5 $ ; $ 0 \leq m \leq 10^6 $ ). The next $ n $ lines describe dishes, the $ i $ -th of them contains a pair of integers $ a_i $ and $ b_i $ ( $ 0 \leq a_i, b_i \le 10^6 $ ) — the masses of fish and meat in the $ i $ -th dish. It is guaranteed that it is possible to eat $ m $ grams of food from each dish. In other words, $ m \leq a_i+b_i $ for all $ i $ from $ 1 $ to $ n $ inclusive. The sum of all $ n $ values over all test cases in the test does not exceed $ 2 \cdot 10^5 $ .

输出格式

For each test case, print on the first line the minimal balance value that can be achieved by eating exactly $ m $ grams of food from each dish. Then print $ n $ lines that describe a way to do this: the $ i $ -th line should contain two integers $ x_i $ and $ y_i $ ( $ 0 \leq x_i \leq a_i $ ; $ 0 \leq y_i \leq b_i $ ; $ x_i+y_i=m $ ), where $ x_i $ is how many grams of fish taster should eat from the $ i $ -th meal and $ y_i $ is how many grams of meat. If there are several ways to achieve a minimal balance, find any of them.

输入输出样例

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