# Roller coaster velociraptor P78006

Statement

thehtml

You are going to get on a roller coaster when you realize that a velociraptor is coming straigh at you. Fortunately, you have a way to escape: the roller coaster. You know that the velociraptor can follow you through the rail, but he will not fit in the tunnel of the roller coaster. You start to push the car in the platform while the velociraptor is chasing you. For obvious reasons you want to get on the car as soon as possible: you want to obtain the speed enough to reach the tunnel and get rid of the velociraptor, but you do not want to push more than the strictly needed in case it catches you in the platform.

You know all the rises and way down that the roller coaster has. Moreover, you know that for each metre in vertical that goes up, the car loses a speed of K kilometres per hour, while for each metre in vertical that goes down, recovers the same lost speed of K kilometres per hour (the laws of physics are not fulfilled in theme parks; if not, it would not have any sense paying so much for the ticket). You also know that there is not any friction with the rail, and that is possible that the car has speed 0 during some moment of the route (you can gather momentum and car would continue) but at any moment it can have negative speed.

Input

The first line of the test data contains the number of cases to solve. Each case starts with 3 integers N, X and K in a line, where N is the number of stretches of the roller coaster, X is the coordinate x of the point where the tunnel is, and K is the speed in kilometres per hour that is lost (respectively, is won) for each metre gone up (respectively, gone down) in vertical. The following N+1 lines contain N+1 pairs of coordinates (xi,yi), separated by a space, that describe the extremes of the N straight stretches that the attraction is composed of. It is fulfilled that (x1,y1) is always (0,0), and that the xi are stricly increasing that is, xi < xi+1. Moreover, the tunnel always is in the beginning of a stretch of the roller coaster, that is, exists a point xi with 1<iN such that xi = X.

Output

For each case, your program must print in a line the minimal speed in kilometres per hour which you have to leave the platform with to reach the beginning of the tunnel, assuring that during the whole route the speed of the car is greater or equal than 0.

Scoring

• TestA:  ‍ Tests with no more than 20 cases where N ≤ 15 and X ≤ 1000.  ‍30 Points ‍
• TestB:  ‍ Tests with no more than 20 cases where N ≤ 25000 and X ≤ 106.  ‍70 Points ‍
Public test cases
• Input

```5
5 51 10
0 0
2 97
51 11
67 -85
148 -116
214 -68
5 87 19
0 0
87 -79
124 -170
167 -221
197 -146
205 -230
5 35 15
0 0
35 -33
132 -10
141 -64
178 -97
226 -126
5 249 7
0 0
77 -46
132 -96
182 -107
249 -184
329 -212
5 196 7
0 0
37 -7
97 8
183 40
196 126
280 58
```

Output

```970
0
0
0
882
```
• Input

```2
2 10 7
0 0
10 0
20 0
4 30 7
0 0
10 10
20 10
30 0
40 0
```

Output

```0
70
```
• Information
Author
Ricardo Martin
Language
English
Translator
Carlos Molina
Original language
Spanish
Other languages
Spanish
Official solutions
C++
User solutions
C++