지하수 저수량

지하수는 땅속에 생긴 호수, 못, 강을 가리키는 말이다. 비가 내리면 물의 일부가 흙과 암석 층으로 스며들어 지표 아래 어딘가에서 이런 물줄기를 이룬다. 뿌리가 충분히 긴 식물은 비가 한동안 오지 않아도 이 지하수를 끌어다 쓴다. 사람도 우물을 깊게 파서 지하수를 쓴다. 가뭄이 들면 지하수가 일부만 남거나 아예 말라 버리고, 다시 채우려면 상당한 양의 비가 필요하다.

이 문제에서는 지하수가 완전히 마른 상태에서 비가 내려 물이 어디까지 채워지는지 계산한다. 저수지 바닥 암반의 단면은 점 $(x_i, y_i)$를 차례로 이은 꺾인 선으로 주어진다. $x$ 좌표는 $x_1 = 0$에서 $x_n = 1$까지 엄격히 증가하고, 어느 선분도 정확히 수평이 아니다. 그래서 어느 지점에 떨어진 물이 어느 쪽으로 흐르는지 항상 정해진다. $y$ 값이 큰 점이 더 위에 있고, 하늘은 $y = +\infty$ 쪽이다. $x = 0$과 $x = 1$에는 무한히 높은 벽이 서 있어서 물은 지도 밖으로 빠져나가지 못한다.

비는 수직으로, 폭 전체에 고르게 내린다. 세기가 $r$이면 시간 1 동안 가로 폭 1에 물 $r$만큼이 떨어진다. 따라서 시간 $t$ 동안 가로 구간 $[a, b]$에 떨어지는 물의 양은 $r \times t \times (b - a)$이다. 경사면에 떨어진 물은 아래로 흘러 웅덩이에 모인다. 웅덩이가 가득 차면 넘치는 물은 그 웅덩이를 막고 있는 두 능선 중 낮은 쪽을 넘어 옆 웅덩이로 흘러간다. 저수지는 완전히 빈 상태에서 시작한다.

비가 내리는 시간 $t$ 동안 저수지 어딘가에서 수면이 도달하는 가장 높은 높이를 구하라.

첫 줄에 데이터 집합의 개수 $K$가 주어진다. 이어서 $K$개의 데이터 집합이 다음 형식으로 주어진다.

각 데이터 집합의 첫 줄에는 수 세 개 $n$, $r$, $t$가 주어진다. 정수 $n$은 저수지 바닥 단면을 이루는 점의 개수이고 $2 \le n \le 50$이다. 실수 $r$은 비의 세기이고 $0.0 \le r \le 1000.0$이다. 실수 $t$는 비가 내리는 시간이고 $0.0 \le t \le 1000.0$이다.

다음 줄에는 바닥 단면의 점을 나타내는 실수 $2n$개가 $x_1\ y_1\ x_2\ y_2\ \dots\ x_n\ y_n$ 순서로 주어진다. $0 = x_1 < x_2 < x_3 < \dots < x_n = 1$이고 $-1000.0 \le y_i \le 1000.0$이다. 이웃한 두 점의 $y$ 값은 서로 다르다.

각 데이터 집합마다 먼저 Data Set x:를 한 줄에 출력한다. $x$는 데이터 집합의 번호이고 1부터 센다.

다음 줄에 비가 내리는 동안 저수지 어딘가에서 수면이 도달한 가장 높은 높이를 소수점 아래 둘째 자리까지 반올림해 출력한다. 물이 전혀 고이지 않은 웅덩이는 수면이 바닥 높이에 있는 것으로 본다.

각 데이터 집합 뒤에 빈 줄을 하나 출력한다.