Археологи раскопали Древний Храм, ко входу в который ведет лестница, шириной в 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
Археологи раскопали Древний Храм, ко входу в который ведет лестница, шириной в 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
Входные данные
В первой строке через пробел заданы два целых числа 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
Не можешь разобраться в этой теме?
Обратись за помощью к экспертам
Гарантированные бесплатные доработки
Быстрое выполнение от 2 часов
Проверка работы на плагиат
Интересные статьи из справочника
Поможем написать учебную работу
Отвечай на вопросы, зарабатывай баллы и трать их на призы.
Подробнее
Подробнее
Алгоритм решения:
Считываем числа M и N.Создаем массив ступенек, каждая ступень представлена парой чисел (L, H) - длина и высота ступеньки.Сортируем ступеньки по возрастанию длины.Вычисляем разницу между длинами и высотами соседних ступенек и суммируем эти разницы.Выводим результат - минимальное количество ступенек N.Пример на Python:
M, N = map(int, input().split())steps = []
for _ in range(M):
L, H = map(int, input().split())
steps.append((L, H))
steps.sort()
diff = []
for i in range(1, M):
diff.append(steps[i][0] - steps[i-1][0])
diff.append(steps[i][1] - steps[i-1][1])
diff.sort(reverse=True)
print(sum(diff[:N-1]))
При вводе примера из задачи (5 3 и длина/высота ступенек), получим ответ 3.