Rolling Hongshu

To see his girl friend, sweet potato has to go over thousands of mountains. What make things worse, many bitter potatoes lives in these mountains. They hate sweet potato because they don't have girl friends.

In the world of potatoes, friction force does not exist. So the way potatoes travel is very simple: they start with an initial speed, rolling forward and waiting to get to the destination.

Bitter potatoes lived in different places. When sweet potato rolls passing their home, they begin to chase him (surely by rolling with an initial speed). If sweet potato is caught by a bitter potato, his date with girl friend has to be canceled.

Now sweet potato wants to know the minimum initial speed necessary to see his girl friend.

First line is an integer T (T ≤ 50), the number of test cases.

At the beginning of each case is three integers, N, M and w, indicate the number of peaks in the mountains, the number of bitter potatoes and the weight of sweet potato separately.

2 ≤ N ≤ 1000, 0 ≤ M ≤ 1000, 0 < w < 100000.

The next N lines each contain a pair of integers. Each pair of integers xi, hi describe a peak. xi is the horizontal distant between sweet potato's home and the peak. hi is the height of the peak. All xi are different. 0 = x1 < x2 < … < xn ≤ 100000000, -100000000 ≤ hi ≤ 100000000. Between adjacent peaks is a smooth slope. The bitter potatoes are on these slopes.

The following M lines each contain 3 integers. Each triple of integers pi, vi, mi describe a bitter potato. pi is the horizontal distant between his home and sweet potato’s home. vi is his initial speed. mi is his weight. 0 < pi < xn, 0 ≤ vi ≤ 100000000, 0 < mi < 100000

The gravitational constant in potatoes' world is 20.

Sweet potato's home is at point (x1, h1). His girl friend lives at point (xn, hn).

For each case, you should output “Case k: ” first. Following a number, the lower bound of sweet potato's initial speed rounded to two decimal places.

1
6 2 100
0 0
2 5
3 2
4 1
5 3
8 -2
2 15 100
5 11 100

Case 1: 20.62

The 36th ACM/ICPC Asia Regional Chengdu Site —— Online Contest