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

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

Потрібно знайти таке розбиття абзацу на рядки, щоб висота абзацу була мінімальною. Ширина і висота кожного блоку ~(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~.

Результати

У першому рядку виведіть мінімальну висоту абзацу. У другому – кількість рядків ~M~, на які потрібно розбити абзац, а в кожному з наступних ~M~ рядків виведіть кількість блоків у відповідному рядку абзаца.

Приклади

Вхід

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

Результат

5
3
2
3
1

Примітки

1. Зрозуміло, в цій задачі для деяких вхідних даних можливі різні детальні правильні відповіді (розподіл блоків по рядкам), які дають однакову мінімальну сумарну висоту. Ваша програма повинна виводити (єдино можливу) правильну мінімальну сумарну висоту та будь-який один із правильних розподілів блоків по рядкам.
2. Зверніть увагу, що у прикладі з умови мінімальна сумарна висота досягається при немінімальній кількості рядків: у першому рядку абзаца можна розмістити не два (як у наведеній відповіді), а три блоки, і тоді всі шість блоків поміщаються у два рядки; але це невигідно, бо сумарна висота тоді вийшла б ~\max(1,1,3)+\max(1,3,1)=3+3=6~, а при наведеному розбитті на три рядки сумарна висота виходить ~\max(1,1)+\max(3,1,3)+\max(1)=1+3+1=5~.