No.3076 Goodstuff Deck Builder
タグ : / 解いたユーザー数 57
作問者 : 👑
binap
/ テスター :
👑 
p-adic
hamamu
遭難者
注意
この問題の問題文は問題Dと共通です。制約のみ異なります。
問題文
あなたはカードゲームをしています。カード $1$ からカード $N$ までの $N$ 枚のカードを手札に持っており、これらを用いて敵に攻撃します。またカードを使用するためのエネルギーを $M$ 持っています。
カード $i$ ( $1\leq i \leq N$ ) は初め $C_i$ のコストを持ち、コストと同じ値だけエネルギーを消費して使用することで敵に $D_i$ のダメージを与えることができます。その後、手札にあるすべてのカードのコストを $2$ 倍します。
使用したカードは手札から取り除かれ再び使用することはできません。またエネルギーが負になるようにカードを使用することはできません。
上記のルールのもとで手札のカードから任意の枚数を選び、任意の順で使用します。与えられる合計ダメージの最大値を求めてください。
制約
$1 \leq N \leq 10^4$
$0 \leq M \leq 10^3$
$0\leq C_i \leq M\ (1\leq i \leq N)$
$1\leq D_i \leq 10^9\ (1\leq i \leq N)$
入力は全て整数。
入力
$N$ $M$ $C_1$ $D_1$ $\vdots$ $C_N$ $D_N$
出力
与えられる合計ダメージの最大値を $1$ 行で出力してください。
サンプル
サンプル1
入力
3 14 3 7 4 2 5 17
出力
24
コスト $x$ でダメージ $y$ のカードを $(x, y)$ と表すことにします。初めのエネルギーは $14$ で、初めの手札は $[(3,7), (4, 2), (5, 17)]$ と表せます。
例えばカード $1$、カード $3$ をこの順に使用すると以下のようになります。
カード $1$ を使用。エネルギーを $3$ 消費して $7$ ダメージを与える。残りエネルギーは $11$ で手札は $[(8, 2), (10, 17)]$ となります。
カード $3$ を使用。エネルギーを $10$ 消費して $17$ ダメージを与える。残りエネルギーは $1$ で手札は $[(16, 2)]$ となります。
このようにして合計 $24$ ダメージを与えることができます。これより大きなダメージを与える方法はありません。
サンプル2
入力
2 0 0 114 0 114
出力
228
手札にコスト $0$ のカードが含まれる場合があります。
サンプル3
入力
5 710 67 997315121 102 115423521 80 517759378 22 992837571 1 462870814
出力
2970782884
答えは符号付き $32$ bit整数型に収まらない場合があります。
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。