위층과 아래층

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

콘스탄틴은 저녁을 즐겁게 보내려고 활동을 적어도 $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$는 소수점 아래 아홉 자리까지 반올림해 출력한다. 이 문제의 테스트 데이터에 나오는 답은 모두 반올림 경계에서 충분히 떨어져 있으므로, 배정밀도로 계산한 값을 아홉 자리로 출력하면 된다.