Informatica Online Judge

  소 짝지어 주기 [1995 / 07CB]

Time Limit(Test case) : 1000 (ms)
Number of users who solved : 18   Total Tried : 20


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

[USACO]

Background

농부 존은 젖소들을 짝지어 주면 우유를 더 쉽게 짤 수 있다는 것을 알아냈다. 존은 m마리의 소들을 2개의 그룹으로 나누어 m/2 개의 짝으로 만들고 싶어 한다.

짝지어진 젖소들은 동시에, 한 쌍씩 우유를 짜는 공간으로 동시에 보내져 착유가 시작된다. 착유량이 A인 젖소와 B인 젖소를 쌍으로 우유를 짜내는 데에는 A+B 만큼의 시간이 걸린다.

소를 최적으로 짝지어, 모든 소들의 우유를 모두 짜내기 위해 필요한 시간을 최소 시간은 얼마일까?

Input

첫 번째 줄에는 n이 입력된다.(1 <= n <= 100000)
그 다음 n개의 각 줄에는 소의 마릿수(x)와 그 소들의 착유량(y)이 공백을 두고 입력된다.
(sum(1 to n) x_i = m, 2 <= m(짝수) <= 1,000,000,000, 1 <= y <= 1,000,000,000)

Output

최적으로 소들을 짝짓고, 동시에 착유를 시작하고 끝낼 때, 가능한 최소 시간을 출력한다.

IO Example

입력
3
1 8
2 5
1 2

출력
10

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