3375 : 전시회
- 제한시간
- 2000 ms
- 메모리제한
- 512 MB
- 해결횟수
- 18 회
- 시도횟수
- 98 회
문제
승원이는 미술품 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 |