Тренировка для продолжающих (по задачам муниципальных олимпиад школьников 2014-15)
A. Торговец артефактами
В некоторой стране имеется 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}).
Единственная строка выходных данных должна содержать единственное целое число — искомое наибольшее количество золотых монет.
Стандартный ввод | Стандартный вывод |
---|---|
6 3 6 2 4 3 6 7 10 | 16 |
6 3 7 2 4 3 6 7 10 | 18 |