Известный шеф-повар приготовил \(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\) грамм.
Определите, сколько какого типа еды должен съесть дегустатор в каждом из блюд, чтобы величина баланса оказалась минимально возможной. Если ответов несколько, выведите любой из них.
Выходные данные
Для каждого набора входных данных выведите в первой строке минимальное значение баланса, которое можно достичь, съев из каждого блюда ровно \(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
|
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
|