숙제

시간 제한2초메모리 제한512 MB

요약

두 과목으로 나뉜 n개의 과제가 각각 공개일과 마감일을 가질 때, 정해진 선택 규칙 아래 동전 던지기에 따라 달라지는 완료 과제 수의 최댓값과 최솟값을 구한다.

난이도: 어려움10점 중 8점
유형: 동적 계획법, 그리디, 시뮬레이션, 구현
정답자: 아직 제출이 없습니다

문제

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

타로는 매일 방과 후에 다음 방식으로 숙제를 최대 한 개 끝낸다. 먼저 동전을 던져 어느 과목의 숙제를 할지 정한다. 고른 과목의 숙제 중에서 이미 받았고, 아직 끝내지 않았으며, 마감일이 지나지 않은 것을 모두 모은 집합을 $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$ 일차가 끝날 때다.

출력

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

예제8

예제 1
입력
```
6 3
1 2
1 5
2 3
2 6
4 5
4 6
```
예상 출력
```
6
2
```
예제 2
입력
```
6 3
1 1
2 3
4 4
1 1
2 4
3 3
```
예상 출력
```
4
3
```
예제 3
입력
```
2 1
1 1
1 1
```
예상 출력
```
1
1
```
예제 4
입력
```
2 1
1 1
2 2
```
예상 출력
```
2
0
```
예제 5
입력
```
4 1
1 1
2 2
3 3
4 4
```
예상 출력
```
4
0
```
예제 6
입력
```
5 2
1 400
1 400
1 400
1 400
1 400
```
예상 출력
```
5
2
```

예제 7

입력

예상 출력

4
4

예제 8
입력
```
7 3
2 2
5 5
1 6
2 2
5 5
3 4
1 6
```
예상 출력
```
5
3
```