위층/아래층

Konstantin과 Ilia는 같은 집에 산다. Konstantin은 위층에 살며, 점프하거나 가구를 이리저리 옮기는 활동, 그리고 일반적으로 소음을 내는 활동을 즐긴다. Ilia는 아래층에 살며 잠자는 것을 즐긴다.

즐거운 저녁 시간을 보내기 위해 Konstantin은 적어도 K개의 활동을 하려고 한다. 어젯밤 Ilia는 Konstantin에게 자신을 깨우지 않도록 노력해 달라고 부탁했고, Konstantin은 매우 좋은 이웃이므로 이에 동의했다. 불행히도 그는 Ilia의 부탁을 다소 지나치게 문자 그대로 받아들였고, Ilia가 잠든 뒤 깨어날 확률을 최소화하도록 활동을 선택할 것이다.

Konstantin이 할 수 있는 각 활동에는 확률 $a_{i}$/$b_{i}$가 대응된다. Konstantin이 이 활동을 하면, 활동이 끝날 때 Ilia는 활동 시작 시 잠들어 있었는지와 관계없이 확률 $a_{i}$/$b_{i}$로 깨어 있고, 그렇지 않으면 잠들어 있다. 또한 Konstantin은 가능한 각 활동을 최대 $c_{i}$번 할 수 있다(그보다 많이 하면 지루할 것이고, Konstantin은 지루하면 즐거운 저녁 시간을 보낼 수 없다).

Konstantin은 다음 조건을 만족하도록 할 활동들을 순서대로 선택하려 한다.

• 한 활동의 총횟수는 적어도 K이다.

• i번째 활동은 $c_{i}$번을 초과하여 하지 않는다.

• 활동을 하는 동안 Ilia가 한 번 이상 깨어날 확률 Q가 가능한 한 작다. Ilia는 처음에 깨어 있으므로, 그가 깨어나려면 어떤 활동이 끝날 때 잠들어 있고 바로 다음 활동이 끝날 때 깨어 있어야 한다.

Konstantin이 즐거운 저녁 시간을 보내면서 달성할 수 있는 가장 작은 Q는 얼마인가? Konstantin은 Ilia가 깨어 있는지 잠들어 있는지 알 수 없으므로, 그 정보를 이용해 활동을 조정할 수 없다는 점에 유의한다.

제한

메모리 제한: 1GB. 1 ≤ T ≤ 100. 모든 i에 대해 0 ≤ $a_{i}$ ≤ $b_{i}$ ≤ 1000000. 모든 i에 대해 1 ≤ $b_{i}$이고 1 ≤ $c_{i}$이다. 1 ≤ K ≤ 해당 테스트 케이스의 모든 $c_{i}$의 합.

테스트 세트 1 (결과 공개)

시간 제한: 30초. 1 ≤ N ≤ 100. 각 테스트 케이스에서 모든 $c_{i}$의 합은 100보다 크지 않다.

테스트 세트 2 (결과 비공개)

시간 제한: 60초. 1 ≤ N ≤ 10000. 각 테스트 케이스에서 모든 $c_{i}$의 합은 $10^{6}$보다 크지 않다.

입력의 첫 줄에는 테스트 케이스의 수 T가 주어진다. 이어서 T개의 테스트 케이스가 주어진다. 각 테스트 케이스는 정수 N, K 한 쌍만 있는 한 줄로 시작한다. 이어지는 N개의 줄은 각각 Konstantin이 선택할 수 있는 활동 하나를 나타낸다. 각 줄은 "$a_{i}$/$b_{i}$ $c_{i}$" 형식이며, 이는 활동이 끝난 뒤 Ilia가 확률 $a_{i}$/$b_{i}$로 깨어 있게 하고 Konstantin이 지루해지지 않고 최대 $c_{i}$번 할 수 있는 활동이 있음을 뜻한다.

각 테스트 케이스마다 "Case #x: Q"을 포함하는 한 줄을 출력한다. 여기서 x는 1부터 시작하는 케이스 번호이고, Q는 Konstantin이 활동을 하는 동안 Ilia가 깨어날 수 있는 가장 작은 확률이다. 절대 오차 또는 상대 오차가 10^{-6} 이하인 답은 정답으로 인정된다.