Лучшая производительность
ACME Inc. реорганизует свою фабрику, чтобы максимизировать производительность бесполезных безделушек. Новый дизайн фабрики состоит из p независимых и идентичных производственных линий. Каждой производственной линии может быть назначено определенное количество работников.
Конечно, все работы выполняются машинами, поэтому производительность производственной линии не зависит от фактического числа назначенных ей рабочих. Однако работники работают посменно, и из-за местных правил безопасности производственная линия может быть активной только в том случае, если все ее работники присутствуют (любой работник, который прибывает до последнего прибывшего человека, или уходит после ухода первого человека, будет тратить неактивное время на кофе-брейк). Другими словами, производительность производственной линии равна длительности промежутка времени, в течение которого присутствуют все работники, назначенные на эту производственную линию. Крайне важно, чтобы производительность каждой линии была положительной (т. е. последний прибывший на линию рабочий должен прибыть строго перед тем, как первый рабочий покинет эту линию), поскольку в противном случае рабочие знают что их работа не имеет смысла.
К сожалению, из-за некоторых надоедливых законов о труде ACME не имеют права увольнять кого-либо из своих работников, а это значит, что каждый из n рабочих должен быть назначен на какую-либо производственную линию, хотя это может фактически снизить общую производительность труда на фабрике.
Все эти правила и положения создают головную боль для управления ACME. Можете ли вы помочь им определить максимально возможную общую производительность (суммарную производительность производственных линий p) на их новом заводе?
Входные данные
Состоит из:
строка содержит два числа n и p (1 ≤ p ≤ n ≤ 200) - количество рабочих и число производственных линий;
n строк, каждая содержит два числа a и b (0 ≤ a < b ≤
10^5), означающих что рабочий прибывает в момент времени a и уходит в момент времени b.
Известно, что существует хотя бы одно подходящее назначение работников на производственные линии.
Выходные данные
Выведите максимальный уровень производительности фабрики.