공장 생산성

정올 공장에는 n명의 노동자와 p개의 생산 라인이 있고, n명의 노동자는 단 한 명도 빠짐없이 p개의 생산 라인 중 하나에 배정이 되어 일을 한다.

실제로 모든 일은 기계가 다 하기 때문에 노동자가 몇명이 붙어있건 생산율은 동일하지만,
안전 규정상 생산 라인은 해당 생산 라인에 배정된 모든 노동자가 근무 중일 때만 작동할 수 있다.

즉, 생산 라인의 생산성은 해당 라인에 할당된 모든 노동자가 근무를 하고 있는 시간과 동일하다고 할 수 있다.

또한, 각 생산 라인의 생산성은 항상 0 초과여야 한다.

모든 n명의 노동자들을 적절히 각 p개의 생산 라인에 배정하여 만들 수 있는 최대의 생산성은 얼마인가?

입력

첫 번째 줄에 n, p가 주어진다 (1 ≤ p ≤ n ≤ 200). 노동자의 수와 생산 라인의 수를 뜻한다.

이후 n개의 줄에 a, b가 주어진다 (0 ≤ a < b ≤ 100 000). 노동자는 시간 a에 출근하고 시간 b에 퇴근한다.

올바른 배정이 최소 하나 존재함이 보장된다.

출력

공장의 최대 생산성을 출력하라.

부분문제

번호	점수	조건
#1	10점	n=p
#2	20점	p=1
#3	30점	a_i \le a_j \leftrightarrow b_j \le b_i
#4	40점	추가 제약 조건 없음

예제

태그

출처

NWERC 2015 B번

공장 생산성 2s 512MB