테트리스

테트리스를 해 본 적이 있을 것이다. 이 게임에서는 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$까지의 구간을 차지한다.

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