No.2693 Sword
タグ : / 解いたユーザー数 135
作問者 :
Kamikazee
/ テスター :
👑 
hibit_at
👑 
seekworser
kikuepl
問題文
あるゲーム世界の主人公である草の Kamikazee は剣を持っています。
剣の攻撃力は現在正整数 $P$ となっています。
また Kamikazee は $N$ 個のアイテムを持っています。
$i$ 番目のアイテムを装備すると、以下のような効果を得ることができます：
- $T_i$ $=$ $1$ のとき、攻撃力をちょうど $B_i$ 上げる
- $T_i$ $=$ $2$ のとき、攻撃力を $2$ 倍にする（ $B_i$ の値は使わない ）
ただし、それが $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もしくは右上の雲マークをクリックしてアカウントを作成してください。