위층과 아래층

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

콘스탄틴은 즐거운 저녁을 보내려고 활동을 $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/b$이고, 콘스탄틴은 그 활동을 최대 $c$번 할 수 있다.

제한

• $1 \le T \le 100$
• $1 \le N \le 100$
• $0 \le a_i \le b_i \le 1000000$
• 모든 $i$에 대해 $1 \le b_i$이고 $1 \le c_i$이다.
• 한 테스트 케이스의 모든 $c_i$의 합은 $100$ 이하이다.
• $1 \le K \le$ 그 테스트 케이스의 모든 $c_i$의 합

각 테스트 케이스마다 Case #x: Q 형식으로 한 줄씩 출력한다. $x$는 1부터 시작하는 테스트 케이스 번호이고, $Q$는 일리야가 깨어날 최소 확률이다. $Q$는 소수점 아래 아홉 자리까지 출력한다.

답은 모두 유리수이고 소수점 아홉 자리 반올림 경계에서 $10^{-12}$ 이내에 있는 답은 없으므로, 배정밀도 실수로 계산한 값을 반올림하면 된다.