Шар для боулинга
В Неверлендах множество горных хребтов. Каждый хребет состоит из чередующихся долин и вершин. Уклон между двумя последовательными вершинами и долинами всегда равен либо 1, либо -1, а высоты всех вершин и долин выражены целыми числами. Шар для боулинга катится по части хребта, состоящей из n долин и n-1 вершин. Шар всегда касается поверхности хребта (он не прыгает). Горы перед первой и после последней долины слишком высоки, поэтому шар не может покинуть хребет. В момент времени t_0 шар находится в долине номер s, двигаясь вверх-вправо, и имеет начальную кинетическую энергию K_0. На следующей иллюстрации показан горный хребет с 4 долинами и 3 вершинами, и шар, находящийся во 2-й долине (нумерация слева направо).
Из курса физики известно, что в любой момент времени t шар обладает гравитационной потенциальной энергией P_t = mgh и кинетической энергией K_t = (½)mv^2, где m — масса шара, g — ускорение свободного падения (здесь равно 10), а h и v — высота и скорость шара в момент времени t. Благодаря преобразованию энергии из потенциальной в кинетическую и наоборот, полная энергия шара P_t + K_t остается постоянной во время его движения, если только он не попадает в долину: в i-й долине (слева) теряется c_i единиц кинетической энергии из-за трения, или он останавливается, если его кинетическая энергия ниже c_i, но трение отсутствует в других местах. Заметьте, что шар теряет c_s единиц энергии, когда покидает начальную долину в момент времени t_0. Вы можете предположить, что диаметр шара равен 0, а его масса равна 1. Ваша задача — определить долину или вершину, на которой шар остановится.
Входные данные
Вход содержит несколько тестов. Первая строка каждого теста содержит три разделенных пробелами положительных целых числа n, s и K_0 (1 ≤ n ≤ 3000, 1 ≤ s ≤ n, 1 ≤ K_0 ≤ 10^15). Каждая из следующих n строк содержит два целых числа h_{i } и c_i, высоту и трение i-й долины. j-я строка из следующих n-1 строк содержит H_j, высоту j-й вершины слева (0 ≤ h_i, c_i, H_j ≤ 10^9). Гарантируется, что хотя бы одно из значений c_i больше нуля. Ввод заканчивается строкой "0 0 0 0", которую не следует обрабатывать.
Выходные данные
Для каждого теста выведите строку, соответствующую одному из следующих форматов в зависимости от того, остановится ли шар в долине или на вершине.
Если шар остановится в долине номер k, выведите "Valley: k" (без кавычек).
Если шар остановится на вершине номер k, выведите "Summit: k" (без кавычек).