전시회 > 문제은행



문제은행

3375 : 전시회

제한시간: 2000 ms    메모리제한: 512 MB
해결횟수: 16 회    시도횟수: 96 회   



승원이는 미술품 N개를 가지고 있다. 

각각의 미술품은 1번부터 N번까지 번호가 매겨져 있다. 

i번 미술품의 크기는 Ai, 가치는 Bi로 나타낸다.

 

오늘은 승원이의 저택 1층에서 미술품을 전시하려고 한다. 

승원이는 아래 조건을 만족하는 미술품을 골라서 전시하려고 한다.

 

 * 전시할 미술품 중에서 가장 큰 크기를 Amax, 가장 작은 크기를 Amin 이라고 하자. 

 * 전시할 미술품의 가치의 합을 S라고 한다.

 * 이 때, S − (Amax − Amin) 가 가장 커야 한다.

 

승원이가 가지고 있는 미술품 N개의 크기와 가치가 주어졌을 때, 

S − (Amax − Amin) 의 최댓값을 구하는 프로그램을 작성하시오.




첫째 줄에 승원이가 가지고 있는 미술품의 개수 N (2 ≤ N ≤ 500,000)이 주어진다.
둘째 줄부터 N개의 줄에 미술품의 크기 Ai와 가치 Bi가 1번 미술품 부터 순서대로 주어진다. 
(1 ≤ Ai ≤ 1,000,000,000,000,000 = 10^15, 1 ≤ Bi ≤ 1,000,000,000)



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


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






HancomEducation E-mail : hancomc@hotmail.com, comkiwer@naver.com Tel : 070-7163-5782 FAX : 031-388-0996 정올소개 이용약관 개인정보처리방침
경기도 안양시 동안구 호계동 1065-10 협성골드프라자 601호, 경기도 안양시 동안구 평촌대로 109 협성골드프라자 601호
Copyright@2010-2015 jungol. All right reserved.