숙제

타로는 이바라키 첨단 컴퓨팅 대학의 학생이다. 이번 학기에는 수학과 정보 두 과목을 듣는다. 수업이 끝나면 교사가 숙제를 낼 때가 있다. 한 수업에서 숙제를 여러 개 받을 수도 있고, 숙제마다 마감일이 다를 수 있다. 숙제에는 저마다 다른 번호가 붙어 있다.

타로는 매일 방과 후에 다음 방식으로 숙제를 최대 한 개 끝낸다. 먼저 동전을 던져 어느 과목의 숙제를 할지 정한다. 고른 과목의 숙제 중에서 이미 받았고, 아직 끝내지 않았으며, 마감일이 지나지 않은 것을 모두 모은 집합을 $S$라고 하자. $S$가 비어 있으면 다른 과목에 끝내지 않은 숙제가 남아 있어도 그날은 숙제를 하지 않고 비디오 게임을 한다. 비어 있지 않으면 $S$에서 마감일이 가장 이른 숙제를 모은 집합을 $T$라고 하고, $T$ 중 번호가 가장 작은 숙제를 끝낸다.

학기가 끝날 때까지 타로가 끝내는 숙제 개수는 동전 결과에 따라 달라진다. 숙제 일정이 주어지면 타로가 끝내는 숙제 개수의 최댓값과 최솟값을 구하라. 학기는 1일차부터 400일차까지이고, 타로는 이 기간의 매일 동전을 던진다.

입력은 테스트 케이스 하나로 이루어지고, 형식은 다음과 같다.

n m
s1 t1
.
.
.
sn tn

첫째 줄에 정수 $n$과 $m$이 주어진다($1 \le m < n \le 400$). $n$은 이번 학기 숙제의 총개수이고 $m$은 수학 숙제의 개수이므로, 정보 숙제는 $n - m$개다. 숙제 번호는 1번부터 $n$번까지이며, 1번부터 $m$번까지가 수학 숙제이고 나머지가 정보 숙제다. 다음 $n$개 줄에 숙제 일정이 주어진다. 그중 $i$번째 줄에 정수 $s_i$와 $t_i$가 주어진다($1 \le s_i \le t_i \le 400$). $i$번 숙제는 학기의 $s_i$일차에 주어지고, 마감은 $t_i$일차가 끝날 때다.

첫째 줄에 타로가 끝내는 숙제 개수의 최댓값을, 둘째 줄에 최솟값을 출력한다.