Долина Золотоискателей

ограничение времени на тест: 2 сек.
ограничение памяти на тест: 1024 KB.

ввод: input.txt
вывод: output.txt

 

Американский миллионер Дж. Скрудж хочет приобрести квадратный участок земли в долине Золотоискателей. В этой долине находится N ярко выраженных мест добычи золота. Каждое такое место представляет собой квадрат размера 1x1 (никакие два квадрата не совпадают). Каждое такое место характеризуется величиной Ai - средним годовым доходом. Скрудж хочет приобрести квадратный участок, на территории которого находится такой набор мест добычи золота, что их суммарный средний годовой доход не меньше W. Конечно, искомый участок должен иметь минимальную площадь. Стороны искомого квадрата должны быть параллельны осям координат. Ваша задача помочь найти расположение такого участка.

Входные данные

В первой строке входного файла содержится два целых числа N, W (1 <= N <= 450; 1 <= W <= 50000). В следующих N строках описаны места добычи золота координатами своих левых верхних углов (Xi, Yi) и величиной Ai (1 <= Xi,Yi <= 10000; 1 <= Ai <= 100). Таким образом, каждая из этих N строк содержит по три целых числа Xi, Yi, Ai. Все места добычи золота - это такие квадраты 1x1, стороны которых параллельны осям координат. Известно, что никакие левые верхние углы двух мест добычи не лежат на одной вертикальной или горизонтальной прямой. Система координат введена таким образом, что ось абсцисс идет слева направо, а ось ординат снизу вверх.

Выходные данные

Выведите фразу NO SOLUTION, если искомый участок не существует. В противном случае выведите четыре целых числа - координаты левого верхнего и правого нижнего угла искомого квадратного участка соответственно. Числа выводите через пробелы. Если решений несколько, выведите любое.

Пример

Ввод

4 6
1 1 1
5 5 4
4 2 4
2 3 3

Вывод

2 3 5 0

Метеорология

ограничение времени на тест: 1 сек.
ограничение памяти на тест: 1024 KB.

ввод: input.txt
вывод: output.txt

 

Профессор Гадалкин заметил, что в первый день нового года на подоконник в его лаборатории выпала 1 снежинка, во второй -- 4 снежинки, а в третий -- 9. Он предположил, что в четвертый день выпадет 16, и так далее (по квадратам целых чисел). Ему стало интересно, в какой день выпадет N-ая снежинка. Помогите ему.

Входные данные

Во входном файле содержатся натуральное число N (1 <= N <= 10^6).

Выходные данные

В выходной файл выведите номер искомого дня.

Пример

Ввод

Test #1
3

Test #2
7

Test #3
16

Вывод

Test #1
2

Test #2
3

Test #3
4

Театр

ограничение времени на тест: 1 сек.
ограничение памяти на тест: 1024 KB.

ввод: input.txt
вывод: output.txt

 

В театре N мест, пронумерованных целыми числами от 1 до N. Некоторые из зрителей опоздали на спектакль. Поэтому после третьего звонка те зрители, которые имели билеты на неудобные места, пересели на более удобные места. Опоздавшие зрители, которые пришли уже после третьего звонка, садились на первое попавшееся свободное место. Некоторые места, вероятно, остались свободными.
В антракте один из опоздавших зрителей решил сесть на свое место. Если его место до этого было занято, то тот, кто там сидел, пересаживался на свое место. Если и там кто-то уже сидел, то и этот зритель также вынужден был вернуться на свое место. И так далее.
Поскольку в театр попали только зрители, имевшие на руках билеты, то начавшийся в антракте процесс пересаживания зрителей обязательно заканчивался.
Требуется написать программу, которая посчитает, сколько человек в результате описанного процесса были вынуждены пересесть на свои места.

Входные данные

В первой строке входного файла содержится целое число N (1 < N <= 7500), количество мест в зале. Вторая строка содержит последовательность из N целых чисел, разделенных пробелами, где первое число определяет номер места в билете у зрителя, который занял место с номером 1, второе - номер места в билете у зрителя, который занял место с номером 2, и так далее. Если место было свободно, то соответствующее число равно 0. Все положительные числа в последовательности различны. В третьей строке содержится одно число - номер места в билете у опоздавшего зрителя, который в антракте решил пересесть на свое место. Гарантируется, что этот зритель сидел не на своем месте в зале до антракта.

Выходные данные

Выходной файл должен содержать одно число - количество зрителей, поменявших свои места в антракте, включая опоздавшего зрителя.

Пример

Ввод

Test #1
10
0 2 5 3 4 0 0 0 0 0
4

Test #2
2
2 1
1

Вывод

Test #1
3

Test #2
2

Средний балл

ограничение времени на тест: 1 сек.
ограничение памяти на тест: 1024 KB.

ввод: input.txt
вывод: output.txt

 

За четверть Петя получил N оценок. Оценки заданы в хронологическом порядке начиная с самой ранней последовательностью A1, A2,..., AN. Ему стал интересен отрезок времени, в который он учился в среднем лучше всего. Он зафиксировал число K (1 <= K <= N) и хочет найти такой отрезок времени, чтобы K идущих подряд оценок имели наибольшее среднее арифметическое среди всевозможных отрезков из K идущих подряд оценок. Помогите ему в этом.

Входные данные

В первой строке входного файла содержатся два натуральных числа N, K (1 <= N <= 7500; 1 <= K <= N). Далее во второй строке содержится последовательность положительных целых чисел A1, A2,..., AN (1 <= Ai <= 5). Числа в последовательности записаны через пробел.

Выходные данные

В первую строку выходного файла выведите искомое наибольшее среднее арифметическое не менее чем с тремя знаками после десятичной точки. Во вторую строку выведите целое число Q, обозначающее, что подпоследовательность A_Q, A_Q+1,..., A_Q+K-1 - искомый отрезок подряд идущих оценок. Если ответов несколько, выведите любой.

Пример

Ввод

7 3
5 4 3 4 5 5 3

Вывод

4.667

Слияние строк

ограничение времени на тест: 1 сек.
ограничение памяти на тест: 1024 KB.

ввод: input.txt
вывод: output.txt

 

Даны две непустые строки S1 и S2. Ваша задача слить эти две строки в новую строку, вставив символы одной строки между (возможно также перед и после) символами другой строки, сохранив при этом порядок следования символов в исходных строках. Результирующая строка должна быть палиндромом. Палиндромом называется строка, одинаково читающаяся как справа налево, так и слева направо.

Входные данные

Во входном файле в первой строке содержится S1, во второй -- S2. Строки состоят исключительно из заглавных букв латинского алфавита. Длины каждой из строк не превосходят 20 символов.

Выходные данные

Выведите -1 если невозможно слить строки, чтобы результат получился палиндромом. В противном случае выведите искомый палиндром. Если решений несколько, выведите любое.

Пример

Ввод

Test #1
AACBA
BA

Test #2
AC
AC

Вывод

Test #1
ABACABA

Test #2
-1

356. Игра "Перевертыши"

ограничение времени на тест: 5 сек.
ограничение памяти на тест: 1024 KB.

ввод: input.txt
вывод: output.txt

 

Поле для игры "Перевертыши" представляет собой прямоугольную доску, расчерченную на NxM квадратов. На каждом квадрате есть кнопка и лампочка. Лампочка может гореть одним из трех цветов: красным, зеленым или синим. При нажатии на кнопку какой-либо клетки меняется цвет лампочки на ней и на всех клетках, имеющих с данной общую сторону. Смена цвета всегда осуществляется по правилу: красный меняется на зеленый, зеленый на синий, а синий на красный. Цель игры: за наименьшее количество нажатий кнопок добиться того, чтобы лампочки на всем поле светились одним цветом. Ваша задача написать программу, которая находит это количество.

Входные данные

В первой строке входного файла содержатся два натуральных числа N и M (1 <= N, M <= 10), где N -- количество строк на доске, а M -- количество столбцов. Далее в N строках содержится описание начального состояния поля. Поле задается цветами лампочек на каждой клетке. Символ "R" обозначает красный цвет, "G" -- зеленый, а "B" -- синий.

Выходные данные

В выходной файл выведите единственное целое число -- наименьшее количество нажатий кнопок, необходимое для того, чтобы лампочки на всем поле светились одним цветом. Если решения не существует, выведите -1.

Пример

Ввод

Test #1
5 5
BBBGG
BBBBG
BBBBB
GBBBB
GGBBB

Test #2
1 3
RRG

Вывод

Test #1
2

Test #2
1

Многоугольник

ограничение времени на тест: 1 сек.
ограничение памяти на тест: 1024 KB.

ввод: input.txt
вывод: output.txt

 

На доске нарисован правильный N-угольник. Его вершины занумерованы числами от 1 до N в порядке обхода против часовой стрелки. В этом многоугольнике проведено K диагоналей. Никакие две диагонали не пересекаются внутри многоугольника, они могут пересекаться лишь только в вершинах. В результате N-угольник теперь представлен как набор многоугольников. Ваша задача для каждого многоугольника из набора вывести количество углов в нем.

Входные данные

В первой строке входного файла записаны два целых числа N, K (3 <= N <= 5000; 0 <= K <= N - 3). Далее в K строках заданы сами диагонали парами номеров соединяемых вершин. Числа во всех строках разделяются пробелами.

Выходные данные

В первую строку выведите Q - количество многоугольников в наборе. Во вторую строку выведите через пробелы для каждого многоугольника в наборе количество углов в нем. Числа во второй строке выводите в любом порядке.

Пример

Ввод

9 4
1 8
8 3
3 1
3 6

Вывод

5
3 3 4 4 3

Сумма цифр

ограничение времени на тест: 1 сек.
ограничение памяти на тест: 1024 KB.

ввод: input.txt
вывод: output.txt

 

На уроке информатики учитель задал Пете задачу нахождения суммы цифр двузначного числа. Петя быстро справился с задачей. Так как он одинаково знает языки Pascal и C++, то решение он написал на обоих языках.

Var a: longint; begin assign(input, 'input.txt'); reset(input); read(a); close(input); assign(output, 'output.txt'); rewrite(output); writeln(a div 10 + a mod 10); close(output); end.

#include <stdio.h> int main() { freopen("input.txt", "rt", stdin); freopen("output.txt", "wt", stdout); int a; scanf("%d", &a); printf("%dn", a / 10 + a % 10); return 0; }

После этого учитель решил усложнить задачу, сказав, что теперь она должна суммировать цифры любого трехзначного числа. Помогите Пете решить усложненную задачу. Разумеется, вам надо представить решение лишь на одном языке программирования.

Входные данные

Во входном файле содержится натуральное число a (100 <= a <= 999).

Выходные данные

В выходной файл выведите искомую сумму цифр числа a.

Пример

Ввод

Test #1
546

Test #2
994

Вывод

Test #1
15

Test #2
22

Осадки

ограничение времени на тест: 1 сек.
ограничение памяти на тест: 1024 KB.

ввод: input.txt
вывод: output.txt

 

Анализируя статистику выпадения осадков за последние несколько лет, метеоролог Гадалкин сделал вывод, что весь следующий год осадки будут выпадать, подчиняясь следующему правилу. В первый день года выпадет A мм осадков, а в каждый следующий день будет выпадать на 1 мм больше, за исключением тех дней, номера которых делятся на 5. В эти дни количество осадков будет меньше на 2 мм, чем в предыдущий день. Например, если A = 4, то осадки будут выпадать следующим образом: 4, 5, 6, 7, 5, 6, 7, 8, 9, 7,... Ваша задача найти суммарное количество осадков за первые B дней года по прогнозу метеоролога.

Входные данные

Входной файл содержит два натуральных числа A, B, записанных через пробел. Числа не превосходят 100.

Выходные данные

Выходной файл должен содержать единственное целое число - искомое суммарное количество осадков.

Пример

Ввод

4 10

Вывод

64

Анализ построения

ограничение времени на тест: 1 сек.
ограничение памяти на тест: 1024 KB.

ввод: input.txt
вывод: output.txt

 

На военном параде солдаты были построены таким образом, что каждый из них встал в центр клетки, заранее нарисованной прямоугольной таблицы NxM клеток. Вам предстоит произвести анализ построения, а именно найти два числа. Первое число это рост самого высокого солдата среди самых низких в каждой строке таблицы, а второе - рост самого низкого солдата среди самых высоких солдат в каждом столбце.

Входные данные

В первой строке входного файла содержатся два натуральных числа N, M (1 <= N <= 50; 1 <= M <= 50). Далее в N строках содержится описание построения в виде таблицы положительных целых чисел, содержащей рост каждого солдата. Каждая из этих строк содержит по M натуральных чисел. Рост любого солдата не превышает 1000.

Выходные данные

В выходной файл выведите искомые два числа. Числа отсортируйте по неубыванию (то есть выведите сначала меньшее, потом большее в случае их неравенства).

Пример

Ввод

Test #1
2 3
9 2 3
4 8 7

Test #2
2 2
4 5
3 6

Вывод

Test #1
4 7

Test #2
4 4

Цветные кубики

ограничение времени на тест: 1 сек.
ограничение памяти на тест: 1024 KB.

ввод: input.txt
вывод: output.txt

 

Мальчик Петя выложил линию из N кубиков разных цветов и размеров. Девочка Лена убирает по одному кубику, но убирать кубик она может только в том случае, если соседние кубики у него одного цвета и/или размера. Какое наибольшее количество кубиков сможет убрать Лена?

Входные данные

В первой строке записано целое число N (1 <= N <= 100). Далее идет N строк по два целых числа Ci и Ri - цвет и размер i-го кубика соответственно (1 <= Ci, Ri <= 100).

Выходные данные

В первую строку выведите целое неотрицательное Q - наибольшее количество кубиков, которое может убрать Лена. Во вторую строку выведите Q чисел - номера кубиков в порядке их удаления из линии. Номера кубиков определяются порядком их задания во входных данных. Заметим, что Q <= N - 2, так как кубики, находящиеся с краю, убирать нельзя. Если решений несколько, выведите любое.

Пример

Ввод

Test #1
5
2 1
1 2
1 2
2 1
1 1

Test #2
5
1 1
2 2
1 1
2 2
2 2

Вывод

Test #1
3
4 3 2

Test #2
2
3 4

Шпионская сеть

ограничение времени на тест: 1 сек.
ограничение памяти на тест: 1024 KB.

ввод: input.txt
вывод: output.txt

 

Начальнику службы внутренней безопасности Берляндии стало известно, что на территорию страны проникла группа вражеских шпионов. Известно, что шпионы работают не только в поисках государственных тайн, но и шпионят друг за другом, собирая компроматы на своих коллег. Известно, что некоторые шпионы вошли в контакт со службой безопасности и готовы предоставить имеющиеся у них компроматы за определенную плату. Наличие компромата на шпиона, немедленно повлечет его арест и получение всех собранных им компроматов. Таким образом, получение за деньги информации от одного шпиона, возможно, повлечет целую волну арестов. Ваша задача, как сотрудника государственного информационного центра, найти такой набор шпионов, получение информации от которых позволит арестовать всех остальных шпионов в стране. Шпионы, предоставившие информацию, не считаются опасными государству и их арестовывать не надо. Конечно, государство должно потратить наименьшее количество денег.

Входные данные

В первой строке записано целое число N (0 < N <= 7500). Далее в N строках содержатся описания шпионов. Каждая строка содержит описание одного шпиона. Описание начинается с целого числа Ai, которое равно 0, если шпион не вошел в контакт со спецслужбами или цене, за которую он предоставит все имеющиеся у него компроматы (0 <= Ai <= 100). Далее идет неотрицательное целое число Pi, которое равно количеству компроматов у данного шпиона. Затем идет список из Pi различных целых чисел от 1 до N - номера шпионов, на которых есть компромат у i-го шпиона. Гарантируется, что сумма всех Pi не превосходит 15000.

Выходные данные

Выведите в первой строке число Q, равное наименьшей сумме, которую должно затратить государство для ареста всех шпионов. Если это сделать невозможно, выведите -1. В случае положительного ответа во вторую строку выведите количество шпионов в искомом наборе. В третью строку выведите номера шпионов в искомом наборе в любом порядке. Если решений несколько, выведите любое.

Пример

Ввод

Test #1
4
0 0
30 2 1 4
10 1 2
20 2 3 1

Test #2
3
0 1 2
3 0
0 1 2

Вывод

Test #1
10
1
3

Test #2
-1

Банк

ограничение времени на тест: 2 сек.
ограничение памяти на тест: 1024 KB.

ввод: input.txt
вывод: output.txt

 

Вам выпал счастливый билет! Вы выиграли в лотерею! В качестве приза вам завели счет в Берляндском Сберегательном Банке и каждое утро в течение N дней стали зачислять на счет некоторую сумму. В первое утро вам зачислят A1 бердолларов, во второе - A2 бердолларов,..., в N-ое утро - AN бердолларов. При зачислении на ваш счет некоторой суммы, она просто прибавляется к вашему текущему счету. Каждый вечер вы можете произвести операцию снятия денег со счета. Снимать можно исключительно все деньги. Так как банк выдает деньги только в бурлях, то пересчет осуществляется с учетом курса обмена. Так как в Берляндии очень высокая инфляция, в первый вечер вы можете снять деньги по курсу 1 бурль за бердоллар, во второй - 2 бурля за бердоллар, и так далее. За одну операцию снятия денег со счета вы уплачиваете банку T бурлей. Таким образом, если в i-ый вечер у вас на счету S бердолларов, и вы осуществляете операцию снятия со счета, то вы получите наличными S * i - T бурлей. После операции снятия со счета денег, ваш счет обнуляется. Заметим, что, так как счет вечером N дня закрывается, перед его закрытием вы обязаны снять с него остаток денег, если он не нулевой. К несчастью, вы не прочли правила лотереи и слишком поздно узнали, что некоторые или даже все Ai могут быть отрицательными. Если сумма S * i - T при снятии денег со счета становится отрицательной, это значит, что вы должны уплатить банку соответствующую сумму в бурлях из ваших наличных. Таким образом, в конце N-го дня ваш баланс наличных может стать отрицательным. Ваша задача так снимать деньги со счета, чтобы максимизировать ваш баланс наличных.

Входные данные

В первой строке входного файла содержатся два целых числа N, T (1 <= N <= 15000; 0 <= T <= 15000). Во второй строке содержится последовательность целых чисел A1, A2,..., AN. Все эти числа по модулю не превосходят 1000.

Выходные данные

Выведите максимальный баланс ваших наличных к концу N-го дня. Гарантируется, что результат поместится в переменную типа double.

Пример

Ввод

7 1
-10 3 -2 4 -6 2 3

Вывод

17

Пояснение. Операции снятия вы должны производить в конце 1-го дня, 5-го и 7-го.

Числоводов и числа

ограничение времени на тест: 1 сек.
ограничение памяти на тест: 1024 KB.

ввод: input.txt
вывод: output.txt

 

Профессор Числоводов любит натуральные числа, но среди них он не любит числа, которые делятся на 2 и/или на 5. Он хочет найти K-ое число среди чисел, которые ему нравятся. Начало ряда чисел, которые ему нравятся, выглядит так: 1, 3, 7, 9, 11, 13, 17, 19, 21, 23,...

Входные данные

Во входном файле содержится натуральное число K (1 <= K <= 1000).

Выходные данные

В выходной файл выведите искомое число.

Пример

Ввод

Test #1
2

Test #2
6

Test #3
9

Вывод

Test #1
3

Test #2
13

Test #3
21

Лыжник

ограничение времени на тест: 1 сек.
ограничение памяти на тест: 1024 KB.

ввод: input.txt
вывод: output.txt

 

Лыжник катается по снежному полю. Его передвижения можно описать строкой из символов 'S', 'N', 'W', 'E' (что соответствует перемещениям на 1 метр в направлении юга, севера, запада или востока соответственно). Известно, что если он прокладывает лыжню, то есть катится по ранее не посещенному отрезку пути, то время такого передвижения равно 5 с, а если он катится по лыжне, то 1 с. Найдите время лыжника в пути.

Входные данные

В первой строке входного файла содержится непустая строка из символов 'S', 'N', 'W', 'E'. Длина строки не превосходит 100 символов.

Выходные данные

файл должен содержать одно число - время в секундах лыжника в пути.

Пример

Ввод

Test #1
WWEN

Test #2
WWEE

Вывод

Test #1
16

Test #2
12

Эх, дороги

ограничение времени на тест: 1 сек.
ограничение памяти на тест: 1024 KB.

ввод: input.txt
вывод: output.txt

 

В Н-ской губернии N городов. Губернатор решил построить сеть высокоскоростных шоссе, соединяющих города. Каждое шоссе является двусторонним и должно соединять некоторую пару городов. Переезжать с одного шоссе на другое можно только в городе, который является концевым для обоих шоссе. Министр транспорта представил губернатору проект. Проект содержит описания M шоссе и предполагаемое время их постройки. Губернатор ознакомился с проектом и выдвинул ряд ценных замечаний. Он сказал, что шоссе из города A в город B лишнее, если к моменту его постройки можно проехать из A в B по ранее построенным шоссе (возможно через некоторое количество промежуточных городов). Он отдал проект своему аналитику, который должен указать первое лишнее шоссе в проекте и последнее не лишнее.

Входные данные

В первой строке входного файла содержатся два целых числа N, M (1 <= N <= 100; 0 <= M <= 100), записанных через пробел. Далее M строк содержат описания M шоссе в порядке их построения. Каждое шоссе задается парой различных чисел A, B (1 <= A, B <= N) - парой номеров соединяемых городов. Все числа в строках разделяются пробелами. В проекте между парой городов может быть более одного шоссе.

Выходные данные

Выведите в выходной файл два числа через пробел. Первое число это номер первого лишнего шоссе в проекте, а второе - номер последнего шоссе, которое лишним не является. Если номера не существует, выводите число 0.

Пример

Ввод

Test #1
3 3
1 2
3 2
1 3

Test #2
3 2
1 2
3 2

Вывод

Test #1
3 2

Test #2
0 2

Треугольная спираль

ограничение времени на тест: 10 сек.
ограничение памяти на тест: 1024 KB.

ввод: input.txt
вывод: output.txt

 

Выведите в выходной файл треугольную спираль из натуральных подряд идущих чисел от 1. Треугольная спираль должна иметь вид прямоугольного равнобедренного треугольника с катетами длиной N. Нумерация должна начинаться с верхней вершины и идти по часовой стрелке. Спирали для N = 2, 3, 6 приводятся в примерах.

Входные данные

В первой строке входного файла содержится натуральное число N (1 <= N <= 1500).

Выходные данные

В выходной файл выведите искомую треугольную спираль.

Пример

Ввод

Test #1
2

Test #2
3

Test #3
6

Вывод

Test #1
1
3 2

Test #2
1
6 2
5 4 3

Test #3
1
15 2
14 16 3
13 21 17 4
12 20 19 18 5
11 10 9 8 7 6

Родник

ограничение времени на тест: 2 сек.
ограничение памяти на тест: 1024 KB.

ввод: input.txt
вывод: output.txt

 

Карта рельефа местности представляет собой прямоугольное поле размером NxM, составленное из цифр. Цифра обозначает высоту соответствующего участка местности над уровнем моря. Известно, что скоро в одной из клеток начнет бить родник (в какой клетке он начнет бить неизвестно). Вода перетекает с данной клетке на соседнюю, если высота соседней клетки ниже или если вода течет по горизонтальному участку менее K клеток с места своего спуска с более высокой клетки (или от позиции родника). Например, если K = 0, то вода не может перетекать с клетки на клетку равной высоты. Соседними считаются клетки, имеющие с данной общую сторону.

0000000000 0111111110 0122222210 0123333210 0123443210 0123443210 0123333210 0122222210 0111111110 0000000000 рис 1.

~~~~~~~000 ~~*~~11110 ~~22222210 ~123333210 ~123443210 0123443210 0123333210 0122222210 0111111110 0000000000 рис 2.

Допустим, K = 2, и карта имеет вид (см. рис. 1). Если родник будет бить в клетке (2, 3), то вода распространится, как показано на рис. 2 ('*' - позиция родника, '~' - затопленная клетка). Если же родник будет бить в любой из 4-ех центральных клеток, то вся местность будет затоплена.
Ваша задача вывести карту местности после затопления, если родник будет бить в таком месте, что затопленная площадь будет максимальна.

Входные данные

Во входном файле в первой строке содержится три натуральных числа N, M, K (1 <= N, M <= 40; 0 <= K <= 10). Далее в N строках содержится карта рельефа местности. Каждая строка карты состоит из M цифр (цифры пробелами не разделяются).

Выходные данные

Выведите карту местности после затопления. Символом '*' выделите место истока родника, а символами '~' - затопленные клетки. Затопленная площадь должна быть наибольшей. Если решений несколько, выведите любое.

Пример

Ввод

Test #1
7 9 1
555505555
555515555
555525555
555535555
555545555
555545555
555555555

Test #2
4 4 2
0999
0229
9929
0000

Вывод

Test #1
5555~5555
5555~5555
5555~5555
5555~5555
55~5~5555
5~*~~5555
55~555555

Test #2
~~~*
~~~~
99~~
~~~~

Путь через пустыню

ограничение времени на тест: 1 сек.
ограничение памяти на тест: 65536 KB.

ввод: input.txt
вывод: output.txt

 

В пустыне есть N оазисов. Вы передвигаетесь по пустыне пешком, и не можете нести с собой более M килограммов груза. Вы планируете совершить путешествие из оазиса 1 в оазис N. В первом оазисе находится магазин, в котором вы можете приобретать продовольствие, в других оазисов магазина нет. В каждом оазисе находится родник. На переход длины L километров вы тратите L килограммов еды и L литров воды (еда и вода тратится непрерывно в процессе перехода). В оазисах вы можете оставлять продовольствие в любом количестве. Какое наименьшее количество еды надо приобрести в первом магазине? Помните, что 1 л воды имеет массу ровно 1 кг.

Входные данные

В первой строке входного файла содержатся два натуральных числа N и M (1 <= N <= 300; 1 <= M <= 10000), где N - количество оазисов в пустыне, а M - максимальная масса, которую вы можете нести во время переходов. Далее в N строках содержатся описания оазисов. Каждое описание - это пара целых чисел, координаты соответствующего оазиса. Все координаты по абсолютной величине не превосходят 10^4.

Выходные данные

В выходной файл выведите единственное вещественное число - наименьшее количество килограмм еды, необходимое для путешествия. Число выводите с точностью 5 знаков после десятичной точки. Если путешествие совершить невозможно, выведите -1. Гарантируется, что результат поместится в переменную типа extended (long double для C/C++) и не будет превосходить 10^9.

Пример

Ввод

Test #1
4 100
10 -20
-10 5
30 15
15 35

Test #2
2 100
0 0
100 100

Вывод

Test #1
135.09811

Test #2
-1