eolymp
bolt
Спробуйте наш новий інтерфейс для відправки розв'язків
Задачі

Абзац

Абзац

Ліміт часу 1 секунда
Ліміт використання пам'яті 256 MiB

В абзаце есть блоки разной высоты (напрмер, обычные слова и математические символы). Абзац длинный, поэтому его нужно разбить на строки. Высота строки определется по наивысшему из блоков в ней. Высота абзаца равна сумме высот всех строк. Длина каждой строки определяется как суммарная ширина блоков, включенных в эту строку (учитывать пробелы не нужно). Возможность разбиения блока для переноса со строки на строку не рассматривается. Изменять порядок следования блоков нельзя. Нужно найти такое разбиение абзаца на строки, чтобы высота абзаца была минимальной. Ширина и высота каждого блока (w(i), h(i)) и максимально допустимая длина строки TW задаются во входных данных.

Вхідні дані

В первой строке записано два числа - TW (максимально допустимая длина строки) и N (количество блоков в абзаце), где 5N5000. В следующих N строках - по два числа (ширина и высота блока).

Все размеры - натуральные числа не большие 10^6. Гарантировано, что для всех блоков w(i) ≤ TW.

Вихідні дані

В первой строке выведите минимальную высоту абзаца. Во второй - количество строк M, на которые нужно разбить абзац, а в следующих M строках выведите количество блоков в соотвествующих строках абзаца.

Приклад

Вхідні дані #1
7 6
3 1
2 1
3 3
1 1
3 3
3 1
Вихідні дані #1
5
3
2
3
1