B. Математическое телешоу
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Поликарп участвует в математическом телешоу. Ему предложены n задач, каждая из которых состоит из k подзадач, которые пронумерованы от 1 до k. За время tj минут он может решить подзадачу j любой из задач. Таким образом, время, которое необходимо на решение подзадачи зависит только от её номера, но не зависит от самой задачи. Поликарп может решать подзадачи в любом порядке.

За решение подзадачи произвольной задачи ему дается один балл. Таким образом, балл за задачу равен количеству её решенных подзадач. Кроме того, если Поликарп полностью решает задачу (то есть все её k подзадач), то он получает дополнительный балл. Таким образом, суммарный балл за полное решение задачи равен k + 1.

Всего у Поликарпа есть M минут. Какой наибольший балл он сможет набрать?

Входные данные

В первой строке записаны три целых числа n, k и M (1 ≤ n ≤ 45, 1 ≤ k ≤ 45, 0 ≤ M ≤ 2·109).

Следующая строка содержит k целых чисел — значения tj (1 ≤ tj ≤ 1000000), где tj — время решения j-й подзадачи в минутах для любой из задач.

Выходные данные

Выведите максимальное количество баллов, сколько сможет набрать Поликарп за M минут.

Примеры
Входные данные
3 4 11
1 2 3 4
Выходные данные
6
Входные данные
5 5 10
1 2 4 8 16
Выходные данные
7
Примечание

В первом примере Поликарп может полностью справиться с первой задачей, потратив время 1 + 2 + 3 + 4 = 10 минут и еще успеть решить одну подзадачу второй задачи за одну минуту.

Во втором примере Поликарп может решить у всех пяти задач первую подзадачу, потратив на это 5·1 = 5 минут. У него еще останется 5 минут. За это время у двух задач он решит вторые подзадачи, потратив на это 2·2 = 4 минуты. Таким образом, суммарно он наберет 5 + 2 = 7 баллов.