시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 256 MB 23 7 7 33.333%

문제

ACME Inc. 는 최근 생산성을 높이기 위해서 공장을 개편했다. 공장은 p개의 독립적이고 동일한 생산 라인으로 구성되어 있으며, 각각의 생산 라인에는 몇 명의 노동자가 배정된다.

실제로 모든 일은 기계가 다 하기 때문에 노동자가 몇명이 붙어있건 생산율은 동일하다. 한편, 안전 규정상 생산 라인은 모든 노동자가 근무 중일 때만 작동할 수 있다. 이 말을 요약하자면, 어떠한 생산 라인의 생산성은 라인에 할당된 모든 노동자가 근무하는 시간과 동일하다고 할 수 있다. 또한, 노동자들을 뿌듯하게 하기 위해서 각 생산 라인의 생산성은 항상 0 초과여야 한다.

한편, 노동법상 ACME는 한명의 노동자도 해고할 수 없다 - 즉, 모든 n명의 노동자들을 생산 라인에 배정해야 한다. 이 때 그들의 새 공장에서 가능한 최대의 생산성은 얼마인가?

입력

입력은 다음과 같이 구성된다.

  • 첫번째 줄에 n, p가 주어진다 (1 ≤ p ≤ n ≤ 200). 노동자의 수와 생산 라인의 수를 뜻한다.
  • 이후 n개의 줄에 a, b가 주어진다 (0 ≤ a < b ≤ 100 000). 노동자는 시간 a에 출근하고 시간 b에 퇴근한다.

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

출력

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

예제 입력

4 2
1 3
1 5
4 6
2 7

예제 출력

4

힌트