어부들

어느 작은 나라의 마을들은 모두 곧은 해안선을 따라 난 하나의 직선 도로 위에 있다. 첫 번째와 마지막 마을을 제외한 각 마을은 도로에서 바로 이웃한 두 마을과 직접 연결되어 있다.

각 마을의 어부들은 해마다 물고기를 잡는다. 잡은 물고기는 그 마을에서 먹을 수도 있고, 도로를 따라 다른 마을로 운반할 수도 있다. 물고기를 운반하면 세금 때문에 이동 거리 1킬로미터마다 물고기 1톤이 사라진다.

각 마을이 같은 수의 아이들을 돌보려고 한다. 아이 한 명은 1년에 물고기 1톤을 먹는다. 물고기를 적절히 운반했을 때 모든 아이들을 먹일 수 있도록, 각 마을이 돌볼 수 있는 아이 수의 최댓값을 구하라.

첫째 줄에 마을의 수 N이 주어진다. 1 <= N <= 100000이다.

다음 N개 줄에는 두 정수 A와 B가 주어진다. A는 마을의 위치, B는 그 마을의 연간 물고기 생산량을 뜻한다. 1 <= A <= 1000000000, 0 <= B <= 1000000000이다.

마을들은 도로 위 위치가 증가하는 순서로 주어진다.

주어지는 데이터에서는 항상 양의 답이 존재한다.

각 마을이 돌볼 수 있는 아이 수의 최댓값을 한 줄에 출력한다.