VIP 쿠폰

희지는 생일 선물로 카트라이더 VIP 쿠폰 $N$개를 받았다. 지금은 VIP가 아니지만, 쿠폰을 사용함으로써 VIP가 되어 게임의 여러 혜택을 받을 수 있다.

희지가 받은 VIP 쿠폰은 쿠폰마다 유효기간과 효과기간이 다르다. 선물 받은 $i$번째 쿠폰의 유효기간은 $E_i$일이며, 효과기간은 $D_i$일이다. VIP 혜택을 받는 기간에는 VIP 쿠폰을 사용할 수 없고, VIP 기간이 끝난 직후에만 사용할 수 있다. 그리고 쿠폰은 유효기간이 0일이 되는 순간 자동으로 폐기되어 더는 사용할 수 없게 되어버린다.

편의상 현재 시점을 $1$일차라고 하자. $i$번째 쿠폰은 $E_i$일차까지 사용할 수 있고, 사용 즉시 쿠폰은 소멸하며 VIP 기간이 $D_i$일 연장된다. 예를 들어 $1$일차에 효과기간이 $3$일인 쿠폰을 사용하면 VIP 기간은 $3$일차까지 연장되고, $4$일차에는 새로운 쿠폰을 사용하여 VIP 기간을 연장해야 한다. 이때 $E_i$가 $4$이상인 쿠폰만 사용할 수 있다.

희지는 VIP 기간을 연속하여 최대한 오래 유지하고 싶어 한다. 그러기 위해서는 쿠폰을 전략적으로 사용해야 하는데, 희지를 도와 VIP 기간을 현재 시점부터 시작하여 최대 며칠 동안 유지할 수 있는지 계산하는 프로그램을 작성하시오.

입력 형식

첫 줄에 선물 받은 쿠폰의 개수 $N$이 주어진다. ($N \ge 1$)

그다음 $N$개의 줄에 걸쳐 $i+1$번째 줄에는 선물 받은 $i$번째 쿠폰의 유효기간 $E_i$와 효과기간 $D_i$가 공백으로 구분되어 주어진다. ($E_i, D_i \ge 1$)

각각의 상한은 아래의 채점방식을 참고하라.

출력 형식

첫 줄에 VIP 기간을 연속하여 최대한 오래 유지했을 때, 유지 가능한 일수를 출력한다.

예제 1

3
11 11
1 10
10 19

21

예제 2

3
12 11
1 10
10 11

22

채점 방식

입력 케이스들은 다음과 같은 종류로 구별되며, 한 종류의 케이스를 다 맞추어야 그 종류에 배정된 점수를 받을 수 있다.

해설