問題一覧 > 通常問題

No.2693 Sword

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 134
作問者 : KamikazeeKamikazee / テスター : 👑 timitimi hibit_athibit_at 👑 seekworserseekworser kikueplkikuepl
0 ProblemId : 10604 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2024-03-21 21:55:16

問題文

あるゲーム世界の主人公である草の Kamikazee は剣を持っています。
剣の攻撃力は現在正整数 $P$ となっています。
また Kamikazee は $N$ 個のアイテムを持っています。
$i$ 番目のアイテムを装備すると、以下のような効果を得ることができます:

  • $T_i$ $=$ $1$ のとき、攻撃力をちょうど $B_i$ 上げる
  • $T_i$ $=$ $2$ のとき、攻撃力を $2$ 倍にする( $B_i$ の値は使わない )
Kamikazee がちょうど $K$ 個のアイテムを装備する場合、剣の攻撃力の最大値を求めてください。
ただし、それが $10^{18}$ を超える場合は -1 を出力してください。
アイテムの効果は $i$ の昇順に適用されます。詳しくはサンプルケースを参照してください。

入力

$N\ P\ K$
$T_1\ B_1$
$T_2\ B_2$
$\vdots$
$T_N\ B_N$

  • 入力はすべて整数
  • $1 \leq K \leq N \leq 1000$
  • $1 \leq P \leq 10^{18}$
  • $1 \leq T_i \leq 2$
  • $T_i$ が $1$ のとき $1 \leq B_i \leq 10^9$
  • $T_i$ が $2$ のとき $B_i = 0$

出力

剣の攻撃力の最大値を出力してください。

サンプル

サンプル1
入力
3 4 2
1 2
1 3
2 0
出力
14

この例では、最初は剣の攻撃力は $4$ です。
$2$ 番目と $3$ 番目のアイテムを装備すると、剣の攻撃力は以下のように推移します:
まず、$2$ 番目のアイテムの効果によって攻撃力が $7$ となります。
次に、$3$ 番目のアイテムの効果によって攻撃力が $14$ となります。
これが剣の攻撃力の最大値です。

サンプル2
入力
5 1 3
2 0
2 0
1 4
1 4
1 4
出力
13

この例では、最初は剣の攻撃力は $1$ です。
$3$ 番目、$4$ 番目、そして $5$ 番目のアイテムを装備すると、剣の攻撃力は以下のように推移します::
まず、$3$ 番目のアイテムの効果によって攻撃力が $5$ となります。
次に、$4$ 番目のアイテムの効果によって攻撃力が $9$ となります。
最後に、$5$ 番目のアイテムの効果によって攻撃力が $13$ となります。
これが剣の攻撃力の最大値です。
最適解ではありませんが、$1$ 番目、$2$ 番目、そして $3$ 番目のアイテムを装備することができます。
その場合、剣の攻撃力は $8$ となります。アイテムの効果が適用されるのは $i$ の昇順であることに注意してください。

サンプル3
入力
1 1 1
1 1
出力
2

この例では、アイテムが $1$ 種類しかありません。それを装備することで、剣の攻撃力は $2$ となり、これが最大値です。

サンプル4
入力
2 999999999999999999 1
1 1
2 0
出力
-1

$2$ 番目のアイテムを装備するのが最適解です。
剣の攻撃力 $999999999999999999$ が倍増されますが、これは $10^{18}$ を超えるので、$-1$ を出力してください。

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