問題一覧 > 通常問題

No.3302 Sense Battle

レベル : / AI推定難易度 : 1200 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 86
作問者 : dyktr_06 / テスター : sepa38 くらげ hanba-gu1 Nafmo2
お気に入りにしたユーザー ProblemId : 12390 / 自分の提出
問題文最終更新日: 2025-10-04 18:13:16
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もしくは右上の雲マークをクリックしてアカウントを作成してください。