AT_abc402_e [ABC402E] Payment Required

時は 30XX 年、あるコンテストでは提出を行うたびにお金が必要になりました。 このコンテストには $ N $ 問の問題が出題されます。 $ i $ 問目の得点は $ S_i $ 点であり、 $ 1 $ 回提出を行うために $ C_i $ 円が必要です。 高橋君は $ i $ 問目に提出すると $ P_i $ % の確率でその問題に正解することができます。各提出で正解できるかどうかはそれまでの提出とは独立に決まります。 高橋君の所持金は $ X $ 円です。提出のために払った金額の総額が $ X $ 円を超えるような提出はできません。 高橋君がコンテストで正解した問題の得点の総和の期待値が最大になるように提出を行った際の総得点の期待値を求めてください。 ただし、高橋君は提出の結果を見てから次にどの問題に提出するかを決めることができるものとします。また、同じ問題に $ 2 $ 回以上正解しても得点は $ 1 $ 回正解した場合と変わらないとします。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ X $ $ S_1 $ $ C_1 $ $ P_1 $ $ S_2 $ $ C_2 $ $ P_2 $ $ \vdots $ $ S_N $ $ C_N $ $ P_N $

答えを出力せよ。真の値と出力との絶対誤差または相対誤差が $ 10^{-6} $ 以下のとき、正解と判定される。

### Sample Explanation 1 以下のような提出方法を考えます。 - まず $ 1 $ 問目に提出する。 - 上の提出が正解なら $ 2 $ 問目に、そうでないなら再び $ 1 $ 問目に提出する。 この場合の得点の期待値は $ 95 $ 点です。得点の期待値を $ 95 $ 点より大きくすることはできないので、 $ 95 $ を出力してください。 ### Constraints - $ 1\le N\le 8 $ - $ 1\le S_i\le 2718 $ - $ 1\le C_i\le X\le 5000 $ - $ 1\le P_i\le 100 $ - 入力される値は全て整数である