문제
KOI나라에서 미술 전시회를 개최하기로 했다.
전시회는 나라 전체에서 모인 다양한 미술품이 전시될 예정이다.
전시되는 미술품의 후보로 N개가 선정되었다.
각각의 미술품에는 크기와 가치가 자연수로 책정되어 있다.
i번째 미술품의 크기는 A_i, 가치는 B_i이다(1 ≦ i ≦ N). 전시회에서는 이러한 미술품들 중에서 1개 이상을 선택해 전시한다.
전시회 회장은 충분히 넓기 때문에 N개의 미술품을 모두 전시 할 수 있다.
그러나 방문객의 미적 감각은 매우 까다롭기 때문에, 크기가 비슷한 미술품들만을 전시하고 싶다.
또한, 가능한 가치 있는 미술품을 많이 전시하고 싶다. 전시회 관리자는 이런 점을 고려해 다음 조건을 충족하도록 전시하는 미술품을 선택하기로 결정했다.
• 전시된 미술품 중 크기가 가장 큰 것의 크기를 A_max, 크기가 가장 작은 것의 크기를 A_min,
전시된 미술품들의 가치의 합을 S라고 할 때, S - (A max - A min)가 최대가 되게 미술품을 선택한다.
전시되는 미술품 후보의 개수와 각 미술품의 크기 및 가치가 주어졌을 때, S - (A_max – A_min) 의 최댓값을 구하여라.
입력
첫 번째 줄에 미술품 후보의 개수를 의미하는 자연수 N이 주어진다.
두 번째 줄부터 N개의 줄에 미술품의 크기와 가치를 나타내는 두 개의 자연수 A_i, B_i가 주어진다.
[제한]
모든 입력 데이터는 다음을 만족한다.
• 2 ≦ N ≦ 500,000
• 1 ≦ A_i ≦ 1,000,000,000,000,000 = 10^15 (1 ≦ i ≦ N)
• 1 ≦ B_i ≦ 1,000,000,000 (1 ≦ i ≦ N) 부분문제 1 [10 점]
• N ≦ 16 부분문제 2 [20 점]
• N ≦ 300 부분문제 3 [20 점]
• N ≦ 5000 부분문제 4 [50 점]
• 추가 제한은 없다.
출력
예제1
3
23
112
45
6
예제2
6
41
15
103
91
42
53
7
예제3
15
1543361732260774320
2089759661257198921
1555665663389548466
4133306295296394520
2596448427301103944
1701413087274491541
2347488426912791996
2133012079444074242
2659886224656957044
1345396764259870638
2671164286233246973
2791812672585862344
299661463591065315
971304780488995617
1523452673988137562
4232545716