Informatica Online Judge

  전시회 #1 [2196 / 0894]

Time Limit(Test case) : 2000 (ms)
Number of users who solved : 21   Total Tried : 24


The Champion of this Problem (C++) : gs17003 - 0ms / 445byte
My Best Submission (C++) : N/A

[JOI 2018 honsen]

Background

GSHS국에서 미술전시회가 열린다.

전시회는 전국에서 모은 각종 미술품이 전시될 예정이다.

전시되는 미술품의 후보로 N개가 정해졌다. 이 미술품에는 1, 2, ... , N 으로 번호가 붙여져 있다.

각각의 미술품은 크기(A)와 가치(B)를 가진다.

각 미술품의 크기는 $A_i$로 표현하고 가치는 $B_i$로 표현된다.

미술전시회에는 이들 미술품들 중 1개 이상을 전시해야 한다.

전시장은 모든 전시품을 전시할 수 있을만큼 충분히 넓다.

GSHS사람들은 전시되는 전시품들의 크기차이가 너무 큰 것을 싫어한다.

따라서 성공적인 전시회를 위해서는 다음 조건을 만족해야 한다.

---------------------------------------------------------------------------------

-선택된 미술품들 중에서 크기가 가장 큰 것을 $A_{max}$, 가장 작은 것을 $A_{min}$, 모든 가치의 합을 $S$라고 한다.

- 전시회의 성공지수는 $W$는 다음과 같다. $ W = S-( A_{max}-A_{min} ) $

----------------------------------------------------------------------------------

적당한 미술품들을 전시하여 $W$의 값의 최댓값을 구하시오.

Input

첫 번째 줄에는 N이 입력된다.

다음 줄부터 N줄에 걸쳐서 $A_i$, $B_i$가 공백으로 구분되어 입력된다.

[입력값의 정의역]
#1 : $ 2 <= N <= 5,000$
$ 1 <= a_i <= 1,000,000,000,000,000$
$ 1 <= b_i <= 1,000,000,000$

Output

최대 성공지수를 출력한다.

IO Example

입력
3
2 3
11 2
4 5

출력
6

* 미술품 1, 3을 고르면 성공지수가 6이되면 이 값이 최대이다.

Submit : [C/C++] | [C++11] | [Obj-C] | [Java] | [Python]
Prob Analysis : [Problem Statistics] | [Solution]