테트리스

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

요약

각 블록은 높이 1의 가로 막대이고 길이와 왼쪽 시작 위치가 주어진다. 떨어뜨리는 순서를 정해 최종 그림의 높이를 가장 낮게 만들고, 그 최소 높이를 출력한다.

난이도: 어려움10점 중 8점
유형: 그리디, 정렬, 구간, 배열
정답자: 아직 제출이 없습니다

문제

테트리스를 해 본 적이 있을 것이다. 이 게임에서는 2차원 블록들이 판 위로 수직으로 떨어진다. 블록은 장애물, 즉 다른 블록이나 판에 닿을 때까지 아래로 떨어지며, 한 번 멈춘 블록은 다시 움직이지 않는다.

원래 테트리스에서는 한 줄이 가득 차면 그 줄이 사라지지만, 이 문제에서는 단순하게 하기 위해 줄이 사라지는 것은 고려하지 않는다. 또한 모든 블록은 높이가 $1$ 인 가로 막대라고 가정한다. 블록을 회전하거나 좌우로 옮길 수는 없고, 바꿀 수 있는 것은 오직 블록들이 떨어지는 순서뿐이다.

각 블록의 길이와 왼쪽 끝의 가로 위치가 주어진다. 블록들을 어떤 순서로 떨어뜨렸을 때 완성되는 도형의 높이를 가장 낮게 만들 수 있는지, 그 최소 높이를 구하여라.

다음을 수행하는 프로그램을 작성하시오.

블록들의 정보를 읽는다,
블록들을 적절한 순서로 떨어뜨렸을 때 얻을 수 있는 도형의 최소 높이를 구한다,
그 높이를 표준 출력에 쓴다.

입력

첫째 줄에 판 위로 떨어질 블록의 개수 $n$ ( $1 \le n \le 100\,000$ )이 주어진다. 이어지는 $n$ 개의 줄에는 각각 두 정수 $l_i$ 와 $p_i$ ( $1 \le l_i, p_i \le 1\,000\,000\,000$ )가 공백 하나로 구분되어 주어지며, 각각 $i$ 번째 블록의 길이와 그 왼쪽 끝의 가로 위치를 뜻한다. $i$ 번째 블록은 가로 방향으로 $p_i$ 부터 $p_i + l_i$ 까지의 구간을 차지한다.

출력

완성되는 도형의 가능한 최소 높이를 정수 하나로 출력한다.

예제4

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