Кулька для боулінгу
У Неверлендах є багато гірських хребтів. Кожен гірський хребет складається з кількох долин і вершин. Схил між двома послідовними вершинами і долинами завжди дорівнює або 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" (без лапок).