問題一覧 > 通常問題

No.3076 Goodstuff Deck Builder

レベル : / 実行時間制限 : 1ケース 3.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 55
作問者 : 👑 binap / テスター : 👑 p-adic hamamu 遭難者
1 ProblemId : 11932 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2025-03-29 03:28:06

注意

この問題の問題文は問題Dと共通です。制約のみ異なります。

問題文

あなたはカードゲームをしています。カード 11 からカード NN までの NN 枚のカードを手札に持っており、これらを用いて敵に攻撃します。またカードを使用するためのエネルギーを MM 持っています。

カード ii ( 1≤i≤N1\leq i \leq N ) は初め CiC_i のコストを持ち、コストと同じ値だけエネルギーを消費して使用することで敵に DiD_i のダメージを与えることができます。その後、手札にあるすべてのカードのコストを 22 倍します。

使用したカードは手札から取り除かれ再び使用することはできません。またエネルギーが負になるようにカードを使用することはできません。

上記のルールのもとで手札のカードから任意の枚数を選び、任意の順で使用します。与えられる合計ダメージの最大値を求めてください。

制約

  • 1≤N≤1041 \leq N \leq 10^4

  • 0≤M≤1030 \leq M \leq 10^3

  • 0≤Ci≤M (1≤i≤N)0\leq C_i \leq M\ (1\leq i \leq N)

  • 1≤Di≤109 (1≤i≤N)1\leq D_i \leq 10^9\ (1\leq i \leq N)

  • 入力は全て整数。

入力

NN MM
C1C_1 D1D_1
⋮\vdots
CNC_N DND_N

出力

与えられる合計ダメージの最大値を 11 行で出力してください。

サンプル

サンプル1
入力
3 14
3 7
4 2
5 17
出力
24

コスト xx でダメージ yy のカードを (x,y)(x, y) と表すことにします。初めのエネルギーは 1414 で、初めの手札は [(3,7),(4,2),(5,17)][(3,7), (4, 2), (5, 17)] と表せます。

例えばカード 11、カード 33 をこの順に使用すると以下のようになります。

  • カード 11 を使用。エネルギーを 33 消費して 77 ダメージを与える。残りエネルギーは 1111 で手札は [(8,2),(10,17)][(8, 2), (10, 17)] となります。

  • カード 33 を使用。エネルギーを 1010 消費して 1717 ダメージを与える。残りエネルギーは 11 で手札は [(16,2)][(16, 2)] となります。

このようにして合計 2424 ダメージを与えることができます。これより大きなダメージを与える方法はありません。

サンプル2
入力
2 0
0 114
0 114
出力
228

手札にコスト 00 のカードが含まれる場合があります。

サンプル3
入力
5 710
67 997315121
102 115423521
80 517759378
22 992837571
1 462870814
出力
2970782884

答えは符号付き 3232 bit整数型に収まらない場合があります。

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