Археологи раскопали Древний Храм, ко входу в который ведет лестница, шириной в 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

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

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

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

Детальный обзор систем антиплагиата: как с ними работать и как повысить уникальность
14305 +43
8
Сегодня вы студент, а завтра уже нет. Как вернуться к учебе после отчисления?
11626 +43
2
Что дает военная кафедра в вузе? Как поступить на «военку» в 2019 году.
6764 +38
0
Как стать тестировщиком игр, сняться на ТВ и вкусно поесть.
2398 +29
1
Доверьте свою работу экспертам
Разместите заказ
Наша система отправит ваш заказ на оценку 30 888 авторам
Первые отклики появятся уже в течение 10 минут
Напишем уникальную работу
Скидка 10%