Grammy에게는 두 명의 팀원 A와 B가 있습니다. 보통 두 팀원은 매일 좋은 식당으로 외식을 하러 가지만, Grammy는 대체로 학교 구내식당에서 밥을 먹습니다. 학교 구내식당에서 먹으면 시간과 돈을 아낄 수 있는 반면, 외식을 하면 택시비가 들기도 합니다. 그럼에도 불구하고 Grammy는 더 맛있는 식사를 위해 팀원들과 함께 외식을 선택할 때가 있습니다.
월말이 다가오면서 Grammy에게는 생활비가 $m$위안밖에 남지 않았고, 이 돈으로 다음 $n$일을 버텨야 합니다. $i$번째 날에 그녀에게는 두 가지 선택지가 있습니다.
- 구내식당에서 식사하여 만족도 $a_i$를 얻고 $b_i$위안을 지출합니다.
- 팀원들과 함께 외식하여 만족도 $c_i$를 얻고 $d_i$위안을 지출합니다.
A와 B는 매일 외식을 하러 가기 때문에 매일 택시비가 발생합니다. $i$번째 날의 택시비를 $e_i$라고 할 때, 세 사람은 택시비를 지불하는 규칙을 다음과 같이 정했습니다.
- Grammy가 $i$번째 날에 외식을 하지 않으면, $\frac{p_i}{100}$의 확률로 A가 택시비를 지불하고, $(1 - \frac{p_i}{100})$의 확률로 B가 지불합니다.
- Grammy가 $i$번째 날에 외식을 하고, Grammy가 마지막으로 택시비를 지불한 이후로(만약 Grammy가 택시비를 한 번도 지불한 적이 없다면 첫째 날부터) A와 B가 각각 적어도 한 번씩 택시비를 지불했다면(그때 Grammy가 함께 외식을 했는지 여부와 관계없이), 이번에는 Grammy가 택시비를 지불합니다. 그렇지 않으면 이전 규칙에 따라 팀원 중 한 명이 지불합니다.
매일 Grammy는 식사 전에 자신의 행동을 선택합니다. 그녀는 전날 누가 택시비를 지불했는지 알고 있으며, 최악의 경우에도 총지출이 $m$위안을 초과하지 않도록 보장하면서 총만족도의 기댓값을 최대화하는 것이 목표입니다. 그녀가 매일 최적의 결정을 내린다면, 총만족도의 기댓값은 얼마입니까?
입력
각 테스트 파일에는 하나의 테스트 케이스만 있습니다.
첫 번째 줄에는 일수와 총지출 한도를 나타내는 두 정수 $n$과 $m$ ($1 \le n \le 2 \times 10^3$, $1 \le m \le 5 \times 10^3$)이 주어집니다.
다음 $n$개의 줄 중 $i$번째 줄에는 여섯 개의 정수 $a_i$, $b_i$, $c_i$, $d_i$, $e_i$, $p_i$ ($0 \le b_i, d_i, e_i \le 5 \times 10^3$, $0 \le a_i, c_i \le 10^9$, $0 \le p_i \le 100$)가 주어집니다. 각 값의 의미는 위에서 설명한 바와 같습니다.
출력
총만족도의 최대 기댓값을 나타내는 숫자 하나를 한 줄에 출력합니다. 만약 최악의 경우에 총지출이 $m$위안 이하가 되도록 하는 계획이 존재하지 않는다면 $-1$을 출력합니다.
출력한 답의 절대 오차 또는 상대 오차가 $10^{-6}$ 이하이면 정답으로 인정됩니다. 형식적으로, 여러분의 출력이 $a$이고 심사위원의 답이 $b$일 때, $\frac{|a-b|}{\max(1,|b|)} \le 10^{-6}$인 경우에만 정답으로 처리됩니다.
예제
2 10
6 4 15 8 10 50
5 2 13 5 8 50
20.000000000000
5 12
2 0 10 5 3 0
2 0 9 4 3 100
2 0 12 7 3 0
2 0 8 4 3 100
2 0 10 6 3 0
25.000000000000
6 20
1 2 3 10 1 69
5 1 12 2 2 23
0 4 2 3 5 41
6 1 6 9 0 84
1 1 14 9 5 98
3 2 13 2 4 43
35.771706880000
3 10
10 4 30 8 1 0
10 4 20 5 1 100
10 6 5 2 1 50
-1