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 점]
• 추가 제한은 없다.
출력형식
입력 예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을 출력한다.