Informatica Online Judge

  파인애플을 사랑하는 동준이 #1 [2245 / 08C5]

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


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

[34th 윤산울]
Writer ID : [gs16068]

Background

평화로운 나라 PPAP의 파인애플 농장에 도둑이 들었다. 파인애플을 모두 도둑맞은 PPAP의 왕 피코타로는 대신 사과를 수확하여 전쟁을 준비하였다.

며칠 후, 파인애플을 사랑하는 동준이가 훔친 파인애플을 들고 PPAP를 침략하였고, 피코타로는 즉시 $n$명의 병사를 파견하였다. $i(1<=i<=n)$번째 병사는 초당 $a_i$개의 사과를 던질 수 있고, 파인애플 $p_i$개를 맞으면 죽는다.

그런데 동준이는 사방팔방으로 매초 파인애플을 하나씩 던지기 때문에, 병사들은 동준이를 향해 일렬로 서서 한 명씩 고기방패가 될 것이다.

따라서 맨 앞에 있는 병사부터 파인애플을 매초 하나씩 맞고, 앞의 병사가 죽으면 그 다음 병사가 파인애플을 맞기 시작할 것이다.



병사들은 사과를 포물선으로 잘 던지기 때문에 던진 사과는 동준이에게 항상 적중한다. 이때 병사들을 적절히 배치하여, 동준이에게 최대한 많이 사과를 던져보자.

Input

첫번째 줄에는 병사의 숫자 $n(n<=200,000)$이 주어진다.

두번째 줄부터 $(n+1)$번째 줄까지 각 병사의 $a_i, p_i(1<=i<=n, 1<=a_i, p_i<=10,000)$가 공백으로 구분되어 주어진다.

Sub-Task Info

$#1: n<=10$

Output

병사들이 던질 수 있는 사과의 최대 개수를 출력한다.

IO Example

입력
3
2 3
3 2
4 5

출력
68

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