В некоторой стране имеется n городов, пронумерованных последовательными целыми числами от 1 до n. Торговец артефактами хочет последовательно посетить все эти города от меньшего номера к большему. Изначально он находится в городе с номером 1.

У торговца имеется m артефактов. Он может продать любой из них в любом из городов, в котором он окажется. За любой артефакт в городе с номером i готовы заплатить a_{i} золотых монет. Торговец может продать более одного артефакта в одном городе, а может и вовсе не продавать ни одного в некоторых городах. В первом и последнем городах так же можно продавать артефакты.

Для того, чтобы перебраться между двумя соседними городами, имея k ранее не проданных предметов, требуется k дней. Временем пребывания в городе и на продажу артефактов можно пренебречь.

Торговец артефактами хочет добраться из города с номером 1 в город с номером n не более чем за d дней. Какое максимальное количество золотых монет он может при этом заработать?

Ваша задача — написать программу, которая определит наибольшее количество монет, которое сможет заработать торговец артефактами, добравшись до города с номером n не более чем за d дней.

Первая строка входных данных содержит три целых числа n, m и d — количество городов, начальное количество артефактов у торговца и количество дней соответственно (1 \leqslant n, m \leqslant 2 \cdot 10^{2}, 1 \leqslant d \leqslant 10^{9}).

Вторая строка входных данных содержит n целых чисел a_{i} — количество золотых монет, которое может быть выручено за продажу артефакта в деревне с номером i (1 \leqslant a_{i} \leqslant 10^{9}).

Единственная строка выходных данных должна содержать единственное целое число — искомое наибольшее количество золотых монет.