問題一覧 > 通常問題

No.3077 Goodstuff Deck Builder(Hard)

レベル : / 実行時間制限 : 1ケース 3.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : （解説公開後に AC するまで非表示） / 解いたユーザー数 47
作問者 : 👑 binap / テスター : 👑 p-adic 👑 hamamu 👑 qand
お気に入りにしたユーザー ProblemId : 11939 / 自分の提出
問題文最終更新日: 2025-03-29 03:28:43
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 462 (順位表) の他の問題:

Note

The statement of this problem is the same as that of Problem C. Only the constraints differ. The differing parts are highlighted in red.

Problem Statement

You are playing a card game. You have $N$ cards in your hand, card $1$ through card $N$, and you use them to attack an enemy. You also have $M$ energy for using cards.

Card $i$ ( $1\leq i \leq N$ ) initially has a cost of $C_i$. By using it, consuming energy equal to its cost, you can deal $D_i$ damage to the enemy. After that, the costs of all cards in your hand are multiplied by $2$.

A used card is removed from your hand and cannot be used again. Also, you cannot use a card if doing so would make your energy negative.

Under the rules above, you choose any number of cards from your hand and use them in any order. Find the maximum total damage you can deal.

Constraints

  • $1 \leq N \leq 10^4$

  • $0 \leq M \leq$ $10^7$

  • $0 \leq NM \leq 2 \times 10^8$

  • $0\leq C_i \leq M\ (1\leq i \leq N)$

  • $1\leq D_i \leq 10^9\ (1\leq i \leq N)$

  • All input values are integers.

Input

$N$ $M$
$C_1$ $D_1$
$\vdots$
$C_N$ $D_N$

Output

Output the maximum total damage you can deal on $1$ line.

Sample

Sample 1
Input
3 14
3 7
4 2
5 17
Output
24

Let $(x, y)$ denote a card with cost $x$ and damage $y$. Initially, your energy is $14$ and your hand can be written as $[(3,7), (4, 2), (5, 17)]$.

For example, if you use card $1$ and card $3$ in this order, the following happens.

・Use card $1$. You consume $3$ energy and deal $7$ damage. The remaining energy is $11$ and your hand becomes $[(8, 2), (10, 17)]$.

・Use card $3$. You consume $10$ energy and deal $17$ damage. The remaining energy is $1$ and your hand becomes $[(16, 2)]$.

In this way, you can deal a total of $24$ damage. There is no way to deal more damage than this.

Sample 2
Input
2 0
0 114
0 114
Output
228

Your hand may contain cards with cost $0$.

Sample 3
Input
5 710
67 997315121
102 115423521
80 517759378
22 992837571
1 462870814
Output
2970782884

The answer may not fit in a signed $32$ bit integer type.

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。