어린이용 수영장

어린이용 수영장은 어린아이들이 그 안에서 놀 수 있도록 물을 담을 수 있는 큰 용기이다.

서로 다른 N개의 수원에서 물을 얻을 수 있다. $i^{th}$번째 수원은 $R_{i}$의 유량과 $C_{i}$의 온도로 물을 공급한다. 처음에는 모든 수원이 꺼져 있다. 각 수원은 단 한 번만 켤 수 있고 단 한 번만 끌 수 있으며, 수원을 켜거나 끄는 동작에는 추가 시간이 들지 않는다. 여러 수원을 동시에 켜 둘 수 있다.

수영장에는 무한한 양의 물을 담을 수 있지만, 가능한 한 빨리 수영장을 정확히 V의 부피와 정확히 X의 온도를 가진 물로 채우려고 한다. 수원들을 최적으로 켜고 끌 때(모든 수원을 반드시 사용할 필요는 없다), 이를 달성하는 데 걸리는 최소 시간은 몇 초인가?

이 문제에서는 부피가 $V_{0}$이고 온도가 $X_{0}$인 물과 부피가 $V_{1}$이고 온도가 $X_{1}$인 물을 섞으면, 즉시 부피가 $V_{0}$+$V_{1}$이고 온도가 ($V_{0}$ $X_{0}$ + $V_{1}$ $X_{1}$) / ($V_{0}$ + $V_{1}$)인 물이 만들어진다. 예를 들어, 10도의 물 5L와 40도의 물 10L를 섞으면 30도의 물 15L가 만들어진다. 또한 물은 다른 물과 섞이는 경우를 제외하면 시간이 지나도 뜨거워지거나 차가워지지 않는다고 가정한다.

제한

메모리 제한: 1 GB. 1 ≤ T ≤ 100. 0.1 ≤ X ≤ 99.9. 0.1 ≤ $C_{i}$ ≤ 99.9.

작은 데이터 세트

시간 제한: 240초. 1 ≤ N ≤ 2. 0.0001 ≤ V ≤ 100.0. 0.0001 ≤ $R_{i}$ ≤ 100.0.

큰 데이터 세트

시간 제한: 480초. 1 ≤ N ≤ 100. 0.0001 ≤ V ≤ 10000.0. 0.0001 ≤ $R_{i}$ ≤ 10000.0.

입력의 첫 번째 줄에는 테스트 케이스의 수 T가 주어진다. 이어서 T개의 테스트 케이스가 주어진다. 각 테스트 케이스의 첫 번째 줄에는 공백으로 구분된 세 수가 주어진다. 정수 N과 위에서 설명한 실수 V, X이다.

다음 N개의 줄에는 각각 공백으로 구분된 두 실수 $R_{i}$와 $C_{i}$가 주어지며, 이는 각각 $i^{th}$번째 수원의 유량과 온도이다. 부피는 리터, 유량은 초당 리터, 온도는 섭씨도로 나타낸다.

모든 실수는 소수점 이하 정확히 네 자리까지 주어진다.

각 테스트 케이스마다 "Case #x: y"를 포함하는 한 줄을 출력한다. 여기서 x는 테스트 케이스 번호이며 1부터 시작하고, y는 어린이용 수영장을 올바른 부피와 온도로 채우는 데 걸리는 최소 시간(초)이다. 주어진 입력으로 이를 달성할 수 없다면 y는 문자열 IMPOSSIBLE이어야 한다.

y가 정답과의 절대 오차 또는 상대 오차가 10^{-6} 이내이면 정답으로 간주한다. 이것이 무엇을 의미하는지와 허용되는 실수 형식에 관한 설명은 FAQ에서 확인할 수 있다. 또한 입력의 실수 형식에서 소수점을 . 문자로 나타낸다는 내용도 그곳에서 확인할 수 있다.

Case #6은 작은 데이터 세트의 제한에 포함되지 않는다는 점에 유의한다.

Case #1에서는 사용할 수 있는 유일한 수원의 온도가 마침 필요한 온도와 정확히 같다. 최적의 전략은 즉시 이 수원을 켜고 물이 10 L가 될 때까지 흐르게 두는 것이다. 매초 0.2 L의 물이 나오므로 50초가 걸린다.

Case #2에서 한 가지 최적의 전략은 첫 번째 수원을 켜서 207221.843687375초 동안 흐르게 하고, 종료 약 0.092778156초 전에는 두 번째 수원도 켜는 것이다.

Case #3에서는 사용할 수 있는 두 수원 모두 목표 온도보다 차가우므로 목표 온도에 도달할 방법이 없다.