Master Zhu and Chessboard

면접 대비

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

요약

각 행의 검은 구간 [Li, Ri]가 오른쪽으로 밀리거나 포함되도록 주어질 때, 모든 검은 칸이 같은 행이나 열에 놓인 말과 겹치도록 하는 최소 말의 수를 구한다.

난이도: 보통10점 중 6점
유형: 그리디, 구간
정답자: 아직 제출이 없습니다

문제

Master Zhu has a rectangular board consisting of $N$ rows and $M$ columns. In the $i$ -th row, the squares from the column $L\_i$ to the column $R\_i$ inclusive are colored black, and all other squares are colored white. Additionally, it is known that $L\_i \le L\_{i + 1}$ and $R\_i \le R\_{i + 1}$ . Now Master Zhu is going to place some chess pieces on several black squares so that for each black square, there is at least one chess piece in its row or in its column.

Find the minimum number of chess pieces he should place.

입력

The first line of the input contains two integers $N$ and $M$ : the number of rows and columns $(1 \le N, M \le 100)$ . Each of the next $N$ lines contains two integers $L\_i$ and $R\_i$ ( $1 \le L\_i \le R\_i \le M$ ). It is guaranteed that $L\_i \le L\_{i + 1}$ and $R\_i \le R\_{i + 1}$ .

출력

Output the minimum number of chess pieces Master Zhu should place.

예제3

예제 1
입력
```
3 3
1 1
2 2
3 3
```
예상 출력
```
3
```
예제 2
입력
```
2 4
1 3
2 4
```
예상 출력
```
2
```
예제 3
입력
```
3 2
1 2
1 2
1 2
```
예상 출력
```
2
```