JOI 2018, 2018camp contest4 problemC- 전시회 > 문제은행 : 정보올림피아드&알고리즘




3161 : 전시회

제한시간
1000 ms   
메모리제한
256 MB   
해결횟수
23 회   
시도횟수
119 회   

문제

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 점] 

• 추가 제한은 없다.


출력형식

S - (A_max - A_min)의 최댓값을 나타내는 한 개의 자연수를 출력한다.

입력 예

3
2 3
11 2
4 5

출력 예

6

입력 예

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

출력 예

7

입력 예

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

Hint!

첫 번째 예제는 전시되는 미술품의 후보가 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을 출력한다.




경기도 안양시 동안구 평촌대로 109 협성골드프라자 601호

TEL : 031-360-4144 FAX : 031-388-0996 E-mail : hancomc@hotmail.com, comkiwer@naver.com

Copyrightⓒ 2010 jungol. All right reserved.

TOP