Есть \(n\) сундуков; \(i\)-й сундук изначально содержит \(a_i\) монет. Для каждого сундука вы можете выбрать любое неотрицательное (\(0\) или больше) количество монет, чтобы добавить в этот сундук, с одним ограничением: суммарное количество монет во всех сундуках должно стать не менее \(k\).
После того как вы закончите добавлять монеты в сундуки, придет жадный Монокарп, которому нужны монеты. Он будет брать сундуки по одному, и поскольку он жадный, он всегда будет выбирать сундук с максимальным количеством монет. Монокарп остановится, как только общее количество монет в сундуках, которые он забрал, станет не менее \(k\).
Вы хотите, чтобы Монокарп забрал как можно меньше монет, поэтому вам нужно добавлять монеты в сундуки таким образом, чтобы, когда Монокарп закончит забирать сундуки, у него было ровно \(k\) монет. Вычислите минимальное количество монет, которое вам нужно добавить.
Выходные данные
Для каждого набора входных данных выведите одно целое число — минимальное количество монет, которое нужно добавить, чтобы, когда Монокарп закончит забирать сундуки, у него было ровно \(k\) монет. Можно показать, что при данных ограничениях задачи это всегда возможно.
Примечание
В первом примере не нужно добавлять монеты. Когда Монокарп придет, он возьмет сундук с \(4\) монетами, так что у него будет ровно \(4\) монеты.
Во втором примере вы можете добавить \(1\) монету в \(4\)-й сундук, так что, когда Монокарп придет, он возьмет сундук с \(4\) монетами, затем еще один сундук с \(4\) монетами и сундук с \(2\) монетами.
В третьем примере вы можете добавить \(3\) монеты в \(1\)-й сундук и \(5\) монет во \(2\)-й сундук.
В четвертом примере вы можете добавить \(1\) монету в \(1\)-й сундук и \(1\) монету в \(3\)-й сундук.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4
5 4
4 1 2 3 2
5 10
4 1 2 3 2
2 10
1 1
3 8
3 3 3
|
0
1
8
2
|