K. Пиратские сундуки
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
64 мегабайта
ввод
стандартный ввод
вывод
стандартный вывод

В настольной игре «Пираты» в течение игры идет накопление жетонов. В конце игры происходит подсчет очков. Из колоды вытягиваются m карточек-сундуков.

Сундуки открываются слева направо, начиная с первого, по следующим правилам:

  • потратив 1 жетон, можно открыть очередной сундук;
  • потратив 1 + 2 = 3 жетона, можно пропустить один сундук и открыть следующий за ним;
  • потратив 1 + 2 + 3 = 6 жетонов, можно пропустить два сундука и открыть следующий за ними;
  • ...
  • потратив (1 + 2 + ... + N) жетонов, можно пропустить следующие (N - 1) сундуков, перейти сразу к N-му и открыть его.

Открытие сундуков может прекратиться в любой момент по решению игрока, тратить все жетоны не обязательно.

При открытии i-ого сундука к количеству очков прибавляется ai.

Посчитайте, какую максимальную ценность может получить игрок, который имеет n жетонов и данную раскладку сундуков.

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

Первая строка содержит целые числа n и m (1 ≤ n ≤ 1000, 1 ≤ m ≤ 100) — число жетонов и сундуков соответственно.

Вторая строка содержит m целых чисел ai ( - 106 ≤ ai ≤ 106) — число очков, которое даёт i-й сундук.

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

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

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

В последнем примере максимально возможную сумму можно собрать следующим образом:

  • Потратим 1 жетон и откроем 1 сундук, суммарное число очков 1;
  • Потратим 1 жетон и откроем 2 сундук, суммарное число очков 2;
  • Потратим 1 жетон и откроем 3 сундук, суммарное число очков 0;
  • Потратим 1 + 2 = 3 жетона, пропустим 4 сундук и откроем 5 сундук, суммарное число очков 5;
  • Потратим 1 жетон и откроем 6 сундук, суммарное число очков 11.
Потрачено 7 жетонов из 8, суммарная ценность составила 11.