eolymp
bolt
Try our new interface for solving problems
Problems

Абзац

Абзац

Time limit 1 second
Memory limit 256 MiB

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

Input data

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

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

Output data

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

Examples

Input example #1
7 6
3 1
2 1
3 3
1 1
3 3
3 1
Output example #1
5
3
2
3
1