Задача №112718. Лестница
Археологи раскопали Древний Храм, ко входу в который ведет лестница, шириной в 1 (один) метр, из \(М\) ступенек различной длины и высоты. Лестница построена из каменных блоков \(1 \times 1 \times 1\) метр. Археологи хотят для удобства туристов, чтобы лестница состояла из меньшего количества ступенек \(N\). Для этого они могут также устанавливать каменные блоки \(1 \times 1 \times 1\). Какое минимальное количество блоков необходимо, чтобы сделать лестницу в \(N\) ступенек, если известны начальная длина и высота каждой ступеньки. Высоты и длины ступенек новой лестницы могут различаться.
В первой строке через пробел заданы два целых числа \(M\) и \(N\) (\(1 \le N < M \le 100\)). Далее идут \(M\) строк, содержащих пару целых чисел \(L\) и \(H\) – длина и высота \(i\)-ой ступеньки соответственно (\(1 \le L, H \le 101\)). Ступеньки нумеруются снизу вверх.
В выходной файл выведите единственное число - ответ на задачу.
Тесты разделены на четыре группы, баллы за группу выставляются только при корректной работе программы на всех тестах группы.
* Тест из условия (0 баллов)
* В этой группе тестов все \(L = H = 1, N < M \le 100\)(30 баллов)
* В этой группе тестов \(1 \le L, H \le 101, N < M \le 10\)(30 баллов)
* Дополнительных ограничений нет (40 баллов)
5 3 4 2 1 2 5 2 1 2 2 1
3