승원이는 미술품 N개를 가지고 있다. 각각의 미술품은 1번부터 N번까지 번호가 매겨져 있다. i번 미술품의 크기는 A_i, 가치는 B_i로 나타낸다.

오늘은 승원이의 저택 1층에서 미술품을 전시하려고 한다. 승원이는 아래 조건을 만족하는 미술품을 골라서 전시하려고 한다.

• 전시할 미술품 중에서 가장 큰 크기를 A_max, 가장 작은 크기를 A_min 이라고 한다. 전시할 미술품의 가치의 합을 S라고 한다.
• 이때, S − (A_max − A_min) 가 가장 커야 한다.

승원이가 가지고 있는 미술품 N개의 크기와 가치가 주어졌을 때, S − (A_max − A_min) 의 최댓값을 구하는 프로그램을 작성하시오.

입력 형식

첫째 줄에 승원이가 가지고 있는 미술품의 개수 N (2 ≤ N ≤ 500,000)이 주어진다.

둘째 줄부터 N개의 줄에 미술품의 크기 A_i와 가치 B_i가 1번 미술품 부터 순서대로 주어진다. (1 ≤ A_i ≤ 1,000,000,000,000,000 = 10¹⁵, 1 ≤ B_i ≤ 1,000,000,000)

출력 형식

첫째 줄에  S − (A_max − A_min) 의 최댓값을 출력한다.

예제 입력 1

3
2 3
11 2
4 5

예제 출력 1

6

예제 입력 2

6
4 1
1 5
10 3
9 1
4 2
5 3

예제 출력 2

7

예제 입력 3

15
1543361732 260774320
2089759661 257198921
1555665663 389548466
4133306295 296394520
2596448427 301103944
1701413087 274491541
2347488426 912791996
2133012079 444074242
2659886224 656957044
1345396764 259870638
2671164286 233246973
2791812672 585862344
2996614635 91065315
971304780 488995617
1523452673 988137562

예제 출력 3

4232545716

힌트

예제 1의 경우에 승원이는 3개의 미술품을 가지고 있고, 크기와 가치는 다음과 같다.

• 1번 미술품의 크기는 2, 가치는 3.
• 2번 미술품의 크기는 11, 가치는 2.
• 3번 미술품의 크기는 4, 가치는 5

이때는, 1번과 3번을 전시하면 S − (A_max − A_min) = 6가 되고, 가장 큰 값이다.

• 크기가 가장 큰 미술품은 3번이다. 따라서, A_max = 4.
• 크기가 가장 작은 미술품은 1번이다. 따라서, A_min = 2.
• 전시할 미술품 가치의 합은 3 + 5 = 8 이다.

따라서, S = 8 이고,  S − (A_max − A_min) 는 6이다.