Homework

Time limit2sMemory limit512 MB

Summary

Given n assignments split into two courses with release days and deadlines, simulate fixed tie-break rules over adaptive coin choices and find the maximum and minimum number he can finish.

Level: Hard8 of 10
Topics: Dynamic programming, Greedy, Simulation, Implementation
Solved: No attempts yet

Problem

Taro is a student at Ibaraki College of Prominent Computing. This semester he takes two courses, mathematics and informatics. After a class the teacher may assign homework. A single class can produce several assignments, and each assignment may have its own deadline. Every assignment carries a distinct ID number.

Every day after school Taro finishes at most one assignment, in the following way. He first flips a coin to decide which course to work on. Let $S$ be the set of all assignments of the chosen course that have already been given, are still unfinished, and whose deadline has not passed. If $S$ is empty, he plays a video game and does no homework that day, even when the other course still has unfinished assignments. Otherwise, let $T \subseteq S$ be the assignments of $S$ with the nearest deadline; he finishes the one with the smallest ID in $T$ .

The number of assignments Taro finishes by the end of the semester depends on the coin flips. Given the schedule of the assignments, compute the maximum and the minimum number of assignments Taro finishes. The semester runs from day 1 to day 400, and Taro flips the coin on every one of those days.

Input

The input consists of a single test case in the following format.

n m
s1 t1
.
.
.
sn tn

The first line contains two integers $n$ and $m$ with $1 \le m < n \le 400$ . Here $n$ is the total number of assignments in this semester and $m$ is the number of assignments of the mathematics course, so the informatics course has $n - m$ assignments. Assignment IDs run from 1 to $n$ : IDs 1 through $m$ belong to mathematics, and the rest belong to informatics. The next $n$ lines give the schedule of the assignments. The $i$ -th of them contains two integers $s_i$ and $t_i$ with $1 \le s_i \le t_i \le 400$ . Assignment $i$ is given to Taro on day $s_i$ of the semester, and its deadline is the end of day $t_i$ .

Output

In the first line, print the maximum number of assignments Taro finishes. In the second line, print the minimum number.

Examples8

Example 1
Input
```
6 3
1 2
1 5
2 3
2 6
4 5
4 6
```
Expected output
```
6
2
```
Example 2
Input
```
6 3
1 1
2 3
4 4
1 1
2 4
3 3
```
Expected output
```
4
3
```
Example 3
Input
```
2 1
1 1
1 1
```
Expected output
```
1
1
```
Example 4
Input
```
2 1
1 1
2 2
```
Expected output
```
2
0
```
Example 5
Input
```
4 1
1 1
2 2
3 3
4 4
```
Expected output
```
4
0
```
Example 6
Input
```
5 2
1 400
1 400
1 400
1 400
1 400
```
Expected output
```
5
2
```

Example 7

Input

Expected output

4
4

Example 8
Input
```
7 3
2 2
5 5
1 6
2 2
5 5
3 4
1 6
```
Expected output
```
5
3
```