E - Payment Required Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 450 点

問題文

時は 30XX 年、あるコンテストでは提出を行うたびにお金が必要になりました。

このコンテストには N 問の問題が出題されます。 i 問目の得点は S_i 点であり、 1 回提出を行うために C_i 円が必要です。

高橋君は i 問目に提出すると P_i % の確率でその問題に正解することができます。各提出で正解できるかどうかはそれまでの提出とは独立に決まります。

高橋君の所持金は X 円です。提出のために払った金額の総額が X 円を超えるような提出はできません。

高橋君がコンテストで正解した問題の得点の総和の期待値が最大になるように提出を行った際の総得点の期待値を求めてください。

ただし、高橋君は提出の結果を見てから次にどの問題に提出するかを決めることができるものとします。また、同じ問題に 2 回以上正解しても得点は 1 回正解した場合と変わらないとします。

制約

  • 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
  • 入力される値は全て整数である

入力

入力は以下の形式で標準入力から与えられる。

N X
S_1 C_1 P_1
S_2 C_2 P_2
\vdots
S_N C_N P_N

出力

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

入力例 1

3 2
100 1 50
200 1 20
1000 1 1

出力例 1

95

以下のような提出方法を考えます。

  • まず 1 問目に提出する。
  • 上の提出が正解なら 2 問目に、そうでないなら再び 1 問目に提出する。

この場合の得点の期待値は 95 点です。得点の期待値を 95 点より大きくすることはできないので、 95 を出力してください。

入力例 2

2 7
100 3 50
100 2 50

出力例 2

125

入力例 3

5 32
500 9 57
300 4 8
300 3 32
300 7 99
100 8 69

出力例 3

953.976967020096

入力例 4

7 78
100 1 100
200 2 90
300 3 80
400 4 60
450 5 50
525 6 30
650 7 1

出力例 4

1976.2441416041121021

Score : 450 points

Problem Statement

In the year 30XX, each submission to a certain contest requires a payment.

The contest has N problems. Problem i has S_i points, and each submission costs C_i yen.

When Takahashi submits to the i-th problem, he solves it with probability P_i %. Each submission’s outcome is independent of the others.

He has X yen. He cannot make any submission that would cause his total spending to exceed X yen.

Find the expected value of the total score of the problems he solves when he chooses submissions to maximize this value.

He may decide which problem to submit to next after seeing the result of the previous submission, and solving the same problem more than once awards the same score as solving it once.

Constraints

  • 1 \leq N \leq 8
  • 1 \leq S_i \leq 2718
  • 1 \leq C_i \leq X \leq 5000
  • 1 \leq P_i \leq 100
  • All input values are integers.

Input

The input is given from Standard Input in the following format:

N X
S_1 C_1 P_1
S_2 C_2 P_2
\vdots
S_N C_N P_N

Output

Print the answer. Your output is considered correct if its absolute or relative error does not exceed 10^{-6}.

Sample Input 1

3 2
100 1 50
200 1 20
1000 1 1

Sample Output 1

95

Consider the following submission strategy:

  • First, submit to the 1st problem.
  • If that submission is correct, submit to the 2nd problem; otherwise, submit again to the 1st problem.

The expected total score for this strategy is 95 points. No strategy can exceed an expected score of 95, so print 95.

Sample Input 2

2 7
100 3 50
100 2 50

Sample Output 2

125

Sample Input 3

5 32
500 9 57
300 4 8
300 3 32
300 7 99
100 8 69

Sample Output 3

953.976967020096

Sample Input 4

7 78
100 1 100
200 2 90
300 3 80
400 4 60
450 5 50
525 6 30
650 7 1

Sample Output 4

1976.2441416041121021