e-olymp
Məsələlər

Абзац

Абзац

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

Входные данные

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

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

Выходные данные

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

Zaman məhdudiyyəti 1 saniyə
Yaddaşı istafadə məhdudiyyəti 256 MiB
Giriş verilənləri
7 6
3 1
2 1
3 3
1 1
3 3
3 1
Çıxış verilənləri
5
3
2
3
1