포스터 붙이기

바이트버그 동쪽 지구의 건물들은 모두 옛 방식으로 지어져서, 서로 사이에 빈틈 없이 바짝 붙어 있다. 이 건물들은 동쪽에서 서쪽으로 길게 이어지며, 높이가 제각각인 하나의 긴 건물 사슬을 이룬다.

바이트버그의 시장 바이트아사르는 이 사슬의 북쪽 면을 포스터로 덮으려고 한다. 그는 북쪽 면 전체를 덮는 데 필요한 포스터의 최소 개수가 궁금하다. 포스터는 각 변이 수직이거나 수평인 직사각형이다. 포스터끼리 겹칠 수는 없지만, 변끼리 닿는 것(경계에서 점을 공유하는 것)은 허용된다. 모든 포스터는 어떤 건물들의 벽에 빈틈없이 맞닿아야 하며, 북쪽 면 전체가 남김없이 덮여야 한다.

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

• 표준 입력에서 건물들의 정보를 읽는다,
• 북쪽 면을 완전히 덮는 데 필요한 포스터의 최소 개수를 구한다,
• 그 결과를 표준 출력에 쓴다.

첫째 줄에 건물의 개수를 나타내는 정수 $n$ ($1 \le n \le 250\,000$)이 주어진다. 이어지는 $n$개의 줄에는 각각 두 정수 $d_i$와 $w_i$ ($1 \le d_i, w_i \le 10^9$)가 공백 하나로 구분되어 주어지며, 이는 각각 줄에서 $i$번째 건물의 너비와 높이를 뜻한다.

건물들의 북쪽 면을 덮기에 충분한 직사각형 포스터의 최소 개수를 정수 하나로 출력한다.

아래 그림은 하나의 예시이다. 첫 번째 그림은 어떤 건물 사슬의 북쪽 면을 보여 주고, 두 번째 그림은 그 면을 포스터 4장으로 덮는 한 가지 방법을 보여 준다.