153. Мягкие подстилки

Программист Вова купил полоску земли шириной $h$ и бесконечной длиной. Так как он любит пёсиков, Вова решил выделить место на полоске для вольера, в котором будут жить его питомцы. Вова хочет покрыть участок этой полосы длиной $w$ мягкими подстилками. Но у программиста мало денег, поэтому пришлось использовать марку «PLANKS».

Подстилки имеют форму вытянутого прямоугольника $1 * x$, причем их надо укладывать так:

• Подстилки кладутся вдоль купленной Вовой полоски, то есть горизонтально.

• Начинать укладку ряда нужно с левого края полоски.

• Начинать новый ряд нельзя, пока длина старого строго меньше $w$.

• Так как все подстилки упакованы, доставать их можно только в том порядке, в котором их привезли.

Участок длины $w$ считается покрытым, тогда и только тогда, когда длина каждого из $h$ рядов $\ge$ w. Вова уже сделал заказ подстилок и хочет понять, какую максимальную длину участка $w$ он сможет ими покрыть.

В первой строке даны два целых числа — ширина полоски ($1 \le h \le 100000$) и количество подстилок в заказе ($h \le n \le 1000000$). В следующей строке даны $n$ целых чисел — длины подстилок ($1 \le x_i \le 1000$)

В единственной строке вывести одно целое число — длину участка $w$.