Абзац
В абзаці є блоки різної висоти (наприклад, звичайні слова і математичні символи). Оскільки абзац довгий, його потрібно розбити на рядки. Висота рядка визначається найвищим блоком у ньому. Висота абзацу дорівнює сумі висот усіх рядків. Довжина кожного рядка визначається сумарною шириною блоків, включених у цей рядок (пробіли не враховуються). Можливість розбиття блоку для переносу з рядка на рядок не розглядається. Змінювати порядок слідування блоків не можна. Потрібно знайти таке розбиття абзацу на рядки, щоб висота абзацу була мінімальною. Ширина і висота кожного блоку (w(i), h(i)) і максимально допустима довжина рядка TW задані у вхідних даних.
Вхідні дані
У першому рядку записано два числа - TW (максимально допустима довжина рядка) і N (кількість блоків в абзаці), де 5 ≤ N ≤ 5000. У наступних N рядках - по два числа (ширина і висота блоку).
Усі розміри - натуральні числа не більші 10^6. Гарантовано, що для всіх блоків w(i) ≤ TW.
Вихідні дані
У першому рядку виведіть мінімальну висоту абзацу. У другому - кількість рядків M, на які потрібно розбити абзац, а в наступних M рядках виведіть кількість блоків у відповідних рядках абзацу.