No.3302 Sense Battle
問題文最終更新日: 2025-10-04 18:13:16
English (AI translation)
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence.
Back to the original
yukicoder contest MMA Contest 020
(順位表)
の他の問題:
Problem Statement
There is $1$ monster with $10^{100}$ HP.
You will fight this monster in a battle of $N$ turns. On turn $i$ $(1 \leq i \leq N)$, you perform the following action in order.
- Choose $1$ card from $2$ types of cards.
If you choose the $1$st type of card, your attack power increases by $+ A_i$.
If you choose the $2$nd type of card, you deal damage equal to your current attack power $+ B_i$.
At the start of the battle, your attack power is $0$. Find the maximum possible total damage you can deal to the monster.
Constraints
- $1 \leq N \leq 5000$
- $1 \leq A_i, B_i \leq 10^{9}$
- All input values are integers.
Input
The input is given from Standard Input in the following format.
$N$ $A_1$ $B_1$ $A_2$ $B_2$ $\vdots$ $A_N$ $B_N$
Output
Output the answer to the problem on a single line.
Sample
Sample 1
Input
4 200 100 300 500 500 200 700 100
Output
1500
For example, choosing cards as follows achieves a total damage of $1500$.
- Turn $1$: Choose the $1$st type of card. Your attack power becomes $200$.
- Turn $2$: Choose the $2$nd type of card. You deal $200 + 500 = 700$ damage.
- Turn $3$: Choose the $1$st type of card. Your attack power becomes $700$.
- Turn $4$: Choose the $2$nd type of card. You deal $700 + 100 = 800$ damage.
It is impossible to deal more than $1500$ damage, so output $1500$.
Sample 2
Input
1 1000000000 1
Output
1
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。
sepa38
くらげ