사탕 기계

어느 사탕 공장에 신비한 기계가 하나 있다. 이 기계는 저마다 조금씩 다른 맛있는 사탕을 만들어 낸다. 기계에는 1번부터 n번까지 번호가 매겨진 출력 슬롯이 한 줄로 늘어서 있고, 각 사탕은 준비되는 순간 자신의 슬롯에서 아래로 떨어진다. 생산이 시작되기 전에 기계는 각 사탕이 몇 번 슬롯에서 언제 떨어질지를 적은 목록을 미리 출력해 준다.

떨어지는 사탕이 바닥에 닿아 상하지 않도록, 공장 주인은 슬롯 아래를 오가며 사탕을 받아 내는 자동 수레를 설치한다. 수레는 1초에 슬롯 한 칸만큼 이동할 수 있고, 생산이 시작되기 전에는 각 수레를 원하는 슬롯 아래에 자유롭게 놓아둘 수 있다. 한 수레가 시각 t에 슬롯 s에서 사탕을 받은 뒤 시각 t′(t ≤ t′)에 슬롯 s′에서 또 다른 사탕을 받으려면 |s′ − s| ≤ t′ − t 를 만족해야 한다.

수레를 운영하는 비용이 크기 때문에 주인은 되도록 적은 수의 수레만 쓰고 싶어 한다. 모든 사탕을 받아 내는 데 필요한 수레의 최소 개수를 구하는 프로그램을 작성하여라.

입력은 표준 입력으로 주어지며, 기계의 한 번의 생산 과정을 나타낸다. 첫째 줄에는 그 과정에서 생산되는 사탕의 개수 n이 주어진다. 이어지는 n개의 줄에는 각각 두 정수 sᵢ와 tᵢ가 주어지며, 이는 i번째 사탕이 떨어지는 슬롯과 시각을 뜻한다. 모든 (sᵢ, tᵢ) 쌍은 서로 다르다.

모든 사탕을 받아 내기 위해 필요한 수레의 최소 개수를 정수 하나로 출력한다.

• 1 ≤ n ≤ 100000
• 0 ≤ sᵢ, tᵢ ≤ 1000000000