9676번 - Bowling Ball 다국어

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₀ the ball is located in the valley number s moving to the upper-right direction and it has an initial kinetic energy K₀. 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², 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₀. 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₀(1 ≤ n ≤ 3000, 1 ≤ s ≤ n, 1 ≤ K₀ ≤ 10¹⁵). 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⁹). It is guaranteed that at least one of c_is 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.)