위층과 아래층

문제

콘스탄틴과 일리야는 같은 집에 산다. 위층에 사는 콘스탄틴은 뛰거나 가구를 옮기는, 소리가 나는 활동을 좋아한다. 아래층에 사는 일리야는 자는 것을 좋아한다.

콘스탄틴은 저녁을 즐겁게 보내려고 활동을 적어도 $K$ 번 하려 한다. 어젯밤 일리야가 자기를 깨우지 말아 달라고 부탁했고, 좋은 이웃인 콘스탄틴은 그러겠다고 했다. 그는 이 부탁을 말 그대로 받아들여서, 일리야가 잠든 뒤에 다시 깨어날 확률이 가장 작아지도록 활동을 고른다.

$i$ 번 활동에는 확률 $a_i / b_i$ 가 붙어 있다. 콘스탄틴이 이 활동을 하면 활동이 끝난 시점에 일리야는 확률 $a_i / b_i$ 로 깨어 있고, 나머지 확률로 잠들어 있다. 이 결과는 활동을 시작할 때 일리야가 자고 있었는지와 상관없으며, 다른 어떤 활동의 결과와도 독립이다. 또 $i$ 번 활동은 최대 $c_i$ 번까지 할 수 있다. 그보다 많이 하면 지루해지고, 지루하면 저녁이 즐겁지 않다.

콘스탄틴은 다음을 만족하도록 활동의 순서를 미리 정한다.

활동의 총 횟수는 $K$ 이상이다.
$i$ 번 활동은 $c_i$ 번을 넘겨 하지 않는다.
일리야가 한 번이라도 깨는 확률 $Q$ 가 가장 작다.

일리야는 처음에 깨어 있다. 그래서 일리야가 깬다는 것은 어떤 활동이 끝난 시점에 잠들어 있고, 그다음 활동이 끝난 시점에 깨어 있다는 뜻이다.

콘스탄틴은 일리야가 깨어 있는지 자고 있는지 알 수 없으므로, 활동의 순서를 전부 미리 정해 두고 저녁 내내 바꾸지 않는다.

콘스탄틴이 즐거운 저녁을 보내면서 얻을 수 있는 가장 작은 $Q$ 를 구하라.

입력

첫 줄에 테스트 케이스의 수 $T$ 가 주어진다. 각 테스트 케이스의 첫 줄에는 두 정수 $N$ 과 $K$ 가 주어진다. 이어지는 $N$ 개의 줄에는 콘스탄틴이 고를 수 있는 활동이 한 줄에 하나씩 a/b c 형식으로 주어진다. 이 활동을 하면 일리야가 확률 $a_i / b_i$ 로 깨어 있고, 콘스탄틴은 이 활동을 최대 $c_i$ 번 할 수 있다. 예를 들어 3/4 2는 끝난 시점에 일리야가 확률 $3/4$ 로 깨어 있고 최대 두 번까지 할 수 있는 활동이다.

제한

$1 \le T \le 100$
$1 \le N \le 10^4$
$0 \le a_i \le b_i \le 10^6$ , $1 \le b_i$ , $1 \le c_i$
한 테스트 케이스에 있는 모든 $c_i$ 의 합을 $S$ 라고 하면 $1 \le K \le S$ 이고 $S \le 10^6$ 이다.

출력

각 테스트 케이스마다 Case #x: Q 형식으로 한 줄씩 출력한다. $x$ 는 1부터 시작하는 테스트 케이스 번호이고, $Q$ 는 콘스탄틴이 활동을 하는 동안 일리야가 깰 가장 작은 확률이다.

$Q$ 는 소수점 아래 아홉 자리까지 반올림해 출력한다. 이 문제의 테스트 데이터에 나오는 답은 모두 반올림 경계에서 충분히 떨어져 있으므로, 배정밀도로 계산한 값을 아홉 자리로 출력하면 된다.