Ця задача відрізняється від наступної задачі «Абзац (детальна відповідь)» тільки тим, що тут потрібно знаходити й виводити лише мінімальну сумарну висоту, а в наступній ще й розподіл блоків по рядкам.

Абзац містить блоки різної висоти (наприклад, звичайні слова й математичні системи). Цей абзац навряд чи поміщається весь в один рядок, тому його, найімовірніше, потрібно розбити на рядки. Висота кожного рядка визначається за найвищим з блоків цього рядка. Висота абзацу дорівнює сумі висот всіх рядків (ніби друкуємо не на окремих сторінках, а на довгому свитку). Довжина кожного рядка визначається як сумарна ширина блоків, включених до цього рядка (враховувати пробіли між блоками не потрібно). Можливість розбиття блоку для перенесення з рядка на рядок не розглядається. Змінювати порядок блоків не можна (і це природньо: ну куди це годиться, щоб у друкарні взяли й попереставляли слова в тексті, який вони мали лише надрукувати, а не відредагувати).

Потрібно знайти таке розбиття абзацу на рядки, щоб висота абзацу була мінімальною. Ширина і висота кожного блоку ~(w_i, h_i)~ та максимально допустима довжина рядка ~TW~ (скорочення від TextWidth) задаються у вхідних даних.

Вхідні дані

У першому рядку записано два числа: ~TW~ (максимально допустима довжина рядка) і ~N~ (кількість блоків в абзаці, де ~5\leqslant N\leqslant 5000~). У наступних ~N~ рядках записано по два числа ~w_i~ та ~h_i~ – ширина і висота чергового блоку.

Всі розміри (окремих блоків та ~TW~) – натуральні числа, не більші ~10^6~. Гарантовано, що для кожного окремо взятого блоку ~w_i\leqslant TW~.

Результати

Виведіть єдине число – мінімальну висоту абзацу.

Приклади

Вхід

7 6
3 1
2 1
2 3
1 1
3 3
3 1

Результат

5

Примітки

Як отримати відповідь 5 при цих вхідних даних, див. у прикладі наступної задачі.