E. Кондитерская
ограничение по времени на тест
3 seconds
ограничение по памяти на тест
256 megabytes
ввод
stdin
вывод
stdout

В садик ходят n ребят, пронумерованных от 1 до n. Каждому из них родители дают на карманные расходы некоторое количество денег (в рублях).

Сегодня ребята собираются в самую известную кондитерскую города. Кондитерская продает конфеты коробками: для всех i от 1 до m, включительно, в кондитерской имеется в наличии коробка, в которой ровно i конфет. Конфета стоит один рубль, так что коробка, в которой x конфет, стоит x рублей.

Ребята будут покупать конфеты по очереди, начиная с мальчика номер 1. За один раз мальчик номер i купит одну коробку конфет, количество конфет в которой строго больше, чем количество конфет в коробке, купленной предыдущим мальчиком (исключением является самый первый раз, когда первый мальчик может купить любую коробку). Затем наступает очередь мальчика номер i + 1, или же мальчика номер 1, если до этого была очередь мальчика номер n. Этот процесс можно остановить в любое время, но после закупок у всех ребят должно быть одинаковое количество коробок конфет. Конечно, ни один мальчик не может потратить больше, чем ему выдали карманных денег.

Вы работаете в кондитерской и хотели бы заготовить конфеты для детей. Выведите наибольшее количество конфет, которое можно продать детям в кондитерской. Если дети не могут приобрести ни одной конфеты (когда им не хватает карманных денег), выведите 0.

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

В первой строке через пробел записаны два целых числа n и m (2 ≤ n ≤ 2·105, 2 ≤ m ≤ 5·106, n ≤ m), обозначающие количество детей и максимальное количество конфет в коробке, соответственно.

Затем следуют n строк, в каждой строке записано по одному положительному целому числу, не превосходящему — карманные деньги в рублях, выдаваемые ребенку. Карманные деньги детей заданы по порядку, от ребенка 1 до ребенка n.

Пожалуйста, не используйте спецификатор %lld для чтения или записи 64-х битовых чисел на С++, вместо него рекомендуется использовать потоки cin, cout, а также спецификатор %I64d.

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

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

Примеры
Входные данные
2 5
5
10
Выходные данные
13
Входные данные
3 8
8
16
13
Выходные данные
32
Входные данные
2 5000000
12500002500000
12500002500000
Выходные данные
12500002500000
Примечание

Для первого теста один из раскладов, при котором кондитерская продаст 13 конфет, выглядит так:

  • 1 покупка. 1-й ребенок покупает 1 конфету.
  • 2 покупка. 2-й ребенок покупает 3 конфеты.
  • 3 покупка. 1-й ребенок покупает 4 конфеты.
  • 4 покупка. 2-й ребенок покупает 5 конфет.