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