페이지가 로드되지 않나요? 여기를 눌러보면 고쳐질 수도 있어요.
Placeholder

#3161

전시회 1s 256MB

문제

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(2 ≦ N ≦ 500,000 )이 주어진다.

두 번째 줄부터 N개의 줄에 미술품의 크기와 가치를 나타내는 두 개의 자연수 A_i, B_i(1 ≦ A_i ≦ 1,000,000,000,000,000 = 10^{15}, 1 ≦ B_i ≦ 1,000,000,000 )가 주어진다. 


출력

S - (A_{max} - A_{min})의 최댓값을 나타내는 한 개의 자연수를 출력한다.


부분문제

번호 점수 조건
#110점

N ≦ 16

#220점

N ≦ 300

#320점

N ≦ 5,000

#450점

추가 제한은 없다.


예제 #1

3

2 3

11 2

4 5
6

전시되는 미술품의 후보가 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})를 7 이상으로 만들 수 없기 때문에 6을 출력한다.


예제 #2

6

4 1

1 5

10 3

9 1

4 2

5 3
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
4232545716


출처

JOI 2018 본선
로그인해야 코드를 작성할 수 있어요.