시간 제한 | 메모리 제한 | 제출 | 정답 | 맞은 사람 | 정답 비율 |
---|---|---|---|---|---|

1 초 | 128 MB | 0 | 0 | 0 | 0.000% |

There are a lot of mountain ranges in the Neverlands. Every mountain range consists of a number of valleys and summits. The slope between two consecutive summit and valley is always either 1 or -1, and all the summits and the valleys have integer heights. A bowling ball is swinging on a part of a mountain range consisting of n valleys and n-1 summits. The ball is always touching down the surface of the mountain range (it does not jump). Mountains before the first and after the last valleys are too high such that the ball can never exit the mountain range. At time t_{0} the ball is located in the valley number s moving to the upper-right direction and it has an initial kinetic energy K_{0}. The following figure shows a mountain range with 4 valleys and 3 summits, and the ball located in the 2^{nd} valley (enumerated from left to right).

By the simple physics we know that at any time t the ball has a gravitational potential energy P_{t}=mgh and also a kinetic energy K_{t}=(1/2)mv^{2}, where m is the mass of the ball, g is the constant of the Earth gravity (here equals to 10), and h and v are the height and the velocity of the ball at time t. By the transformation of energy from potential to kinetic or vice versa, the total energy of the ball P_{t}+K_{t} is fixed during its movements, unless it falls into a valley: at the ith valley (from left), c_{i} units of the kinetic energy is lost due to friction or it stops if its kinetic energy is below c_{i} but consider no friction in other locations. Note that the ball loses c_{s} unit of energy when it leaves the starting valley at time t_{0}. You can assume the ball diameter is equal to 0 and its mass is equal to 1. Your task is to find the valley or summit at which the ball will stop.

There are multiple test cases in the input. The first line of each test case contains three space-separated positive integers n, and s and K_{0}(1 ≤ n ≤ 3000, 1 ≤ s ≤ n, 1 ≤ K_{0} ≤ 10^{15}). Each of the following n lines contains two integers h_{i} and c_{i}, the height and friction of the i^{th} valley. The j^{th} line of the next n-1 lines contains H_{j}, the height of The j^{th} summit from the left (0 ≤ h_{i},c_{i},H_{j} ≤ 10^{9}). It is guaranteed that at least one of c_{i}s is greater than zero. The input terminates with “0 0 0 0” which should not be processed.

For each test case, output a line conforming one of the following formats depending on whether the ball stops at either a valley or a summit.

- If the ball stops at valley number k, output “Valley: k” (omit the quotes.)
- If the ball stops at Summit number k, output “Summit: k (omit the quotes.)

4 2 17 1 1 2 1 1 1 1 2 3 3 2 1 1 1000000000000000 1 1 0 0 0 0

Summit: 2 Valley: 1

ACM-ICPC > Regionals > Asia > Iran > Tehran Site 2013 G번