O. Лестница

Ко входу в древний храм ведёт лестница шириной один метр, сложенная из каменных блоков $1 \times 1 \times 1$. Ступенька номер $i$ имеет длину $L_i$ и высоту $H_i$; ступеньки нумеруются снизу вверх.

Археологи хотят, чтобы ступенек стало ровно $N$ вместо $M$. Лишние ступеньки они убирают, засыпая их блоками до уровня следующей: несколько соседних ступенек превращаются в одну, длина которой равна их суммарной длине.

Найдите наименьшее число блоков, которое для этого понадобится.

Первая строка содержит числа $M$ и $N$ ($1 \le N < M \le 100$).

Далее идут $M$ строк, в каждой длина $L$ и высота $H$ очередной ступеньки снизу вверх ($1 \le L, H \le 101$).

Одно число — наименьшее число блоков.