Археологи раскопали Древний Храм, ко входу в который ведет лестница, шириной в 1 (один) метр, из М ступенек различной длины и высоты. Лестница построена из каменных блоков 1x1x1 метр. Археологи хотят для удобства туристов, чтобы лестница состояла из меньшего количества ступенек N. Для этого они могут также устанавливать каменные блоки 1x1x1. Какое минимальное количество блоков необходимо, чтобы сделать лестницу в N ступенек, если известны начальная длина и высота каждой ступеньки. Высоты и длины ступенек новой лестницы могут различаться.
Входные данные
В первой строке через пробел заданы два целых числа M и N (1 ≤ N < M ≤ 100). Далее идут M строк, содержащих пару целых чисел L и H - длина и высота i-ой ступеньки соответственно (1 ≤ L, H ≤ 101). Ступеньки нумеруются снизу вверх.
Выходные данные
В выходной файл выведите единственное число - ответ на задачу.
Примеры
входные данные
5 3
4 2
1 2
5 2
1 2
2 1
выходные данные
3

131
0
Не можешь разобраться в этой теме?
Обратись за помощью к экспертам
Гарантированные бесплатные доработки
Быстрое выполнение от 2 часов
Проверка работы на плагиат

Похожие вопросы

Интересные статьи из справочника

Где лучше всего студентам живется?
4698 +34
1
Форму набора каждый выбирает сам – по возможностям или по желанию. Спешим обрадовать: у коммерции тоже есть плюсы.
4977 +28
0
Несколько способов, которые помогут обратить критику себе на пользу. Проверено — работают.
473 +25
0
Сегодня вы студент, а завтра уже нет. Как вернуться к учебе после отчисления?
5771 +19
0
Устаревший подход к обучению, субъективные оценки учителей и другие проблемы.
436 +17
0
Доверьте свою работу экспертам
Разместите заказ
Наша система отправит ваш заказ на оценку 31 626 авторам
Первые отклики появятся уже в течение 10 минут