Поликарп участвует в математическом телешоу. Ему предложены n задач, каждая из которых состоит из k подзадач, которые пронумерованы от 1 до k. За время tj минут он может решить подзадачу j любой из задач. Таким образом, время, которое необходимо на решение подзадачи зависит только от её номера, но не зависит от самой задачи. Поликарп может решать подзадачи в любом порядке.
За решение подзадачи произвольной задачи ему дается один балл. Таким образом, балл за задачу равен количеству её решенных подзадач. Кроме того, если Поликарп полностью решает задачу (то есть все её k подзадач), то он получает дополнительный балл. Таким образом, суммарный балл за полное решение задачи равен k + 1.
Всего у Поликарпа есть M минут. Какой наибольший балл он сможет набрать?
Выходные данные
Выведите максимальное количество баллов, сколько сможет набрать Поликарп за M минут.
Примечание
В первом примере Поликарп может полностью справиться с первой задачей, потратив время 1 + 2 + 3 + 4 = 10 минут и еще успеть решить одну подзадачу второй задачи за одну минуту.
Во втором примере Поликарп может решить у всех пяти задач первую подзадачу, потратив на это 5·1 = 5 минут. У него еще останется 5 минут. За это время у двух задач он решит вторые подзадачи, потратив на это 2·2 = 4 минуты. Таким образом, суммарно он наберет 5 + 2 = 7 баллов.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3 4 11
1 2 3 4
|
6
|
|
2
|
5 5 10
1 2 4 8 16
|
7
|