004 - ヤマモトハハニワ

茶番

ヤマモト、ハニワ。ハニワ、モロイ。
ココニ、$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

耐久度が高くなる場合もある。