인기 있는 한 액션 게임의 상점에는 $n$개의 서로 다른 치명타 장비가 판매되고 있습니다. $i$번째 장비는 $\frac{p_i}{100}$의 확률로 배율 $v_i$인 치명타를 발동시키며, 가격은 $w_i$ 코인입니다. 각 장비는 최대 한 번만 구매할 수 있습니다.

여러 장비가 동시에 치명타를 발동시키면 가장 높은 배율만 적용됩니다. 어떤 장비도 치명타를 발동시키지 않으면 유효 배율은 $0$으로 간주됩니다.

여러분은 최대 $m$ 코인을 사용하여 일부 장비를 구매할 수 있습니다. 구매한 장비들의 유효 배율의 기댓값을 최대화해야 합니다.

입력

여러 개의 테스트 케이스가 주어집니다. 입력의 첫째 줄에는 테스트 케이스의 개수를 나타내는 정수 $T$ ($1 \le T \le 300$)가 주어집니다. 각 테스트 케이스에 대해:

첫째 줄에는 장비의 개수와 사용할 수 있는 최대 코인 수를 나타내는 두 정수 $n$과 $m$ ($1 \le n, m \le 3 \times 10^3$)이 주어집니다.

다음 $n$개의 줄 중 $i$번째 줄에는 $i$번째 장비를 나타내는 세 정수 $p_i$, $v_i$, $w_i$ ($1 \le p_i \le 100, 1 \le v_i \le 10^9, 1 \le w_i \le 3 \times 10^3$)가 주어집니다.

모든 테스트 케이스에 걸쳐 $n$의 합과 $m$의 합은 각각 $3 \times 10^3$을 넘지 않음이 보장됩니다.

출력

각 테스트 케이스마다 최대 기대 유효 배율을 나타내는 실수 하나를 한 줄에 출력합니다.

출력한 답의 절대 오차 또는 상대 오차가 $10^{-6}$ 이하이면 정답으로 인정됩니다. 공식적으로, 여러분의 답을 $a$, 정해의 답을 $b$라고 할 때, $\frac{|a-b|}{\max(1,|b|)} \le 10^{-6}$을 만족할 때 그리고 그때에만 정답으로 처리됩니다.

예제

예제 입력 1

2
3 15
75 50 5
50 100 10
25 200 15
2 10
50 10 100
70 30 1000

예제 출력 1

68.750000000000
0.000000000000