Задача G. Путь к спасению

Автор:Антон Карабанов   Ограничение времени:1 сек
Входной файл:Стандартный вход   Ограничение памяти:64 Мб
Выходной файл:Стандартный выход  
Максимальный балл:100  

Условие

"Остап запрыгал по лестнице, ведущей на пристань. Ему предстояло пробежать четыреста ступенек. На шестой площадке его уже поджидали два любителя, пробравшиеся сюда окольной тропинкой прямо по склону. Остап оглянулся. Сверху катилась собачьей стаей тесная группа разъяренных поклонников защиты Филидора. Отступления не было. Поэтому Остап побежал вперед.

— Вот я вас сейчас, сволочей! — гаркнул он храбрецам-разведчикам, бросаясь с пятой площадки. Испуганные пластуны ухнули, переваливаясь за перила, и покатились куда-то в темноту бугров и склонов. Путь был свободен.

— Держите гроссмейстера! — катилось сверху. " (И.Ильф, Е.Петров. "Двенадцать стульев").

Остап бежит вниз по лестнице, на некоторых площадках которой его поджидают рассерженные шахматисты. У сына турецкоподданого есть показатель агрессивности, начальный уровень которой равен a. Если этот показатель не меньше количества k васюкинцев на площадке, то он может потратить k единиц агрессивности и преодолеть площадку без повреждений. В противном случае (или если Остапу не хочется уменьшать агрессивность), он получает от шахматистов k тумаков, а его агрессивность увеличивается на ⌊ k2 (k пополам, округленное вниз до целой части).

Определите наименьшее число тумаков, которое может получить на лестнице великий комбинатор.

Формат входных данных

Первая строка входного файла содержит два неотрицательных целых числа a - начальное состояние агрессивности и n - количество площадок, на которых Остапа поджидают противники. Во второй строке даны n натуральных чисел ki - количество шахматистов на каждой такой площадке.

Формат выходных данных

Выведите одно натуральное число - ответ на задачу.

Ограничения

0 ≤ a ≤ 100

1 ≤ n ≤ 100

1 ≤ ki ≤ 10

Система оценки и описание подзадач

Баллы за каждый тест начисляются независимо.

Пояснение к примеру

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

На первой площадке Остап не тратит агрессивность и получает первый тумак. Его агрессивность при этом не меняется (⌊ 12⌋ = 0) и по-прежнему равна 5.

На второй площадке Остап снова не тратит агрессивность и получает еще три тумака (всего 4). Его агрессивность при этом увеличивается на 1 (⌊ 32⌋ = 1) и становится равна 6.

На третьей площадке Остап пугает противников и не получает новых тумаков (всего 4). Его агрессивность уменьшается на 2 и становится равна 4.

На четвертой площадке Остап не тратит агрессивность и получает еще четыре тумака (всего 8). Его агрессивность при этом увеличивается на 2 (⌊ 42⌋ = 2) и опять становится равна 6.

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

Примеры тестов

Стандартный вход Стандартный выход
1
5 6
1 3 2 4 1 5
8

0.042s 0.009s 15