Недавно Петя узнал о новой игре «Slay the Dragon». Как видно из названия, игроку предстоит сражаться с драконами, чтобы победить дракона, необходимо его убить и защитить свой замок. Для этого в распоряжении игрока есть отряд из \(n\) героев, сила \(i\)-го героя равна \(a_i\).
По правилам игры убивать дракона должен отправиться ровно один герой, все остальные будут защищать замок. Если защита дракона равна \(x\), то на его убийство можно отправлять героя с силой не менее \(x\). Если сила атаки дракона равна \(y\), то суммарная сила героев, защищающих замок, должна быть хотя бы \(y\).
За одну золотую монету игрок может увеличить силу любого из героев на \(1\). Эту операцию можно выполнять любое количество раз.
Всего в игре существует \(m\) драконов, у \(i\)-го из них защита \(x_i\), а сила атаки \(y_i\). Пете стало интересно, какое минимальное количество монет ему необходимо потратить, чтобы победить \(i\)-го дракона.
Обратите внимание, что задача решается независимо для каждого дракона (улучшения не сохраняются).
Выходные данные
Выведите \(m\) строк, \(i\)-я из которых содержит одно целое число — минимальное количество монет, которое необходимо потратить, чтобы победить \(i\)-го дракона.
Примечание
Для победы над первым драконом можно увеличить силу третьего героя на \(1\), тогда силы героев будут равны \([3, 6, 3, 3]\). Для убийства дракона можно выбрать первого героя.
Для победы над вторым драконом можно увеличить силы второго и третьего героев на \(1\), тогда силы героев будут равны \([3, 7, 3, 3]\). Для убийства дракона можно выбрать второго героя.
Для победы над третьим драконом можно увеличить силы всех героев на \(1\), тогда силы героев будут равны \([4, 7, 3, 4]\). Для убийства дракона можно выбрать четвертого героя.
Для победы над четверым драконом можно не улучшать героев и выбрать третьего героя для убийства дракона.
Для победы над пятым драконом можно увеличить силу второго героя на \(2\), тогда силы героев будут равны \([3, 8, 2, 3]\). Для убийства дракона можно выбрать второго героя.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4
3 6 2 3
5
3 12
7 9
4 14
1 10
8 7
|
1
2
4
0
2
|