茶番
ヤマモト、ハニワ。ハニワ、モロイ。
ココニ、$N$ タイノハニワ、アル。
ソレゾレノハニワ、タイキュウド、アル。$i$ タイメノハニワ、タイキュウド $E_i$ アル。タイキュウドガ $0$ ニナッタトキ、ソノハニワ、コワレル。
ハニワ、セイカクワルイ。
$i$ タイメノハニワガコワレルマエニ $H_i$ タイメノハニワガコワレタトキ、 $i$ タイメノハニワノタイキュウド $A_i$ ナル。
オマエ、コウゲキリョクガ $P$ ノハンマーモッテル。
コウゲキリョクガ $p$ ノハンマーデタイキュウドガ $e$ ノハニワヲタタイタトキ、タタイタアトノハンマーノコウゲキリョク $\max(0, \ p - e)$ ナリ、タタイタアトノハニワノタイキュウド $\max(0, \ e - p)$ ナル。
サイダイデナンタイノハニワガコワセルカ、モトメロ。
問題(翻訳)
$N$ 体の埴輪がある。
それぞれの埴輪には耐久度というものがあり、耐久度が $0$ になるとその埴輪は壊れてしまう。$i$ 体目の埴輪の初期の耐久度は $E_i$ である。
これらの埴輪にはもう一つ特徴がある。
$i$ 体目の埴輪が壊れる前に $H_i$ 体目の埴輪が壊れると、$i$ 体目の耐久度が $A_i$ になるのだ。
あなたは攻撃力が $P$ であるハンマーを一つ持っている。
攻撃力が $p$ であるハンマーで耐久度が $e$ である埴輪を叩いたとき、叩いた後のハンマーの攻撃力は $\max(0, \ p - e)$ となり、叩いた後の埴輪の耐久度は $\max(0, \ e - p)$ となる。
あなたには、このハンマーを使って最大で何体の埴輪が壊せるかを求めて欲しい。
入力
入力は以下の形式で標準入力から与えられる。
$N \ P$
$E_1 \ H_1 \ A_1$
$\vdots$
$E_N \ H_N \ A_N$
出力
壊すことのできる埴輪の数の最大値を出力せよ。出力の最後に改行を入れること。
制約
全ての入力ケースについて以下を満たす。
- $2 \leq N \leq 15$
- $1 \leq P \leq 10^9$
- $1 \leq H_i \leq N$
- $i \neq H_i$
- $1 \leq E_i, \ A_i \leq 10^9$
入出力例
入力例1
3 10 5 2 3 9 3 1 7 2 5
出力例1
2
三体目の埴輪を壊した後に二体目の埴輪を壊すのが最適である。
入力例2
3 10 9 2 18 6 3 23 10 1 33
出力例2
1
耐久度が高くなる場合もある。