Наступают неспокойные времена, и поэтому вы решили закупиться сахаром про запас. В округе расположены \(n\) магазинов, в которых продают сахар: в \(i\)-м магазине одна пачка сахара стоит \(a_i\), но везде продают только по одной пачке на руки в день. А потому, чтобы купить несколько пачек, придется посетить несколько магазинов.
Есть и другая проблема: цены на сахар растут каждый день: в первый день он стоит \(a_i\), во второй день он стоит \(a_i + 1\), в третий — \(a_i + 2\) и так далее в любом магазине \(i\).
Вы можете тратить на сахар только \(x\) монет каждый день. Другими словами, каждый день вы ходите и покупаете как можно больше пачек сахара суммарной стоимостью не более \(x\). Обратите внимание, что если в какой-то день вы тратите не все монеты, вы не можете оставшиеся монеты использовать в следующие дни.
Рано или поздно, стоимость пачки из любого магазина превысит \(x\), и вы больше не сможете купить ни одной пачки. Вопрос в том, сколько всего пачек вы сможете купить до этого момента?
Выходные данные
Для каждого набора входных данных выведите одно число — суммарное количество пачек сахара, которые вы сможете приобрести, пока цены не превысят ваши возможности.
Примечание
В первом наборе входных данных:
- День 1: цены равны \([2, 1, 2]\). Вы сможете купить все \(3\) пачки, так как \(2 + 1 + 2 \le 7\).
- День 2: цены равны \([3, 2, 3]\). Вы не сможете купить все \(3\) пачки, так как \(3 + 2 + 3 > 7\), а потому вы купите только \(2\) пачки.
- День 3: цены равны \([4, 3, 4]\). Вы сможете купить \(2\) пачки с ценами \(4\) и \(3\).
- День 4: цены равны \([5, 4, 5]\). Вы больше не сможете купить \(2\) пачки, а потому вы купите только \(1\) пачку.
- День 5: цены равны \([6, 5, 6]\). Вы сможете купить \(1\) пачку.
- День 6: цены равны \([7, 6, 7]\). Вы сможете купить \(1\) пачку.
- День 7: цены равны \([8, 7, 8]\). Вы все еще можете купить \(1\) пачку за цену \(7\).
- День 8: цены равны \([9, 8, 9]\). Цены слишком высокие, и вы не можете ничего купить.
В результате вы купите
\(3 + 2 + 2 + 1 + 1 + 1 + 1 = 11\) пачек.
Во втором наборе, цены слишком высокие с первого дня, и вы не сможете ничего купить.
В третьем наборе, вы можете купить одну пачку только в первый день.
В четвертом наборе, вы можете покупать \(2\) пачки первые \(500\) дней. В день \(501\) цены станут \([501, 501]\), а потому вы сможете покупать только \(1\) пачку следующие \(500\) дней. В день \(1001\) цены станут \([1001, 1001]\) и вы больше ничего не сможете купить. В результате вы купите \(500 \cdot 2 + 500 \cdot 1 = 1500\) пачек.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4
3 7
2 1 2
5 9
10 20 30 40 50
1 1
1
2 1000
1 1
|
11
0
1
1500
|