В одной далёкой, далёкой галактике... С течением
времени сформировалась система подобная Солнечной, содержащая N
обитаемых планет. Одинокий исследовательский межпланетный корабль с небольшим
количеством топлива на борту по воле случая либо провидения оказался в этой
системе в точке А. Объект исследования находится на планете с номером B.
Двигатель корабля, к сожалению, не может работать на вакууме, поэтому его
необходимо заправлять топливом. Расход топлива на перелёт из одной точки в
другую равен округлённому вверх отношению (d / 100), где d —
расстояние между точками. Начальный запас топлива на корабле ограничен, и для
его пополнения экипаж вынужден закупать топливо на планетах. Поскольку
экономика каждой планеты весьма самостоятельна, то и цена топлива на разных
планетах различается. Требуется найти минимальное количество денег, необходимое
для того, чтобы добраться до объекта исследований.
В первой строке входного файла содержатся 6 чисел: XA, YA, ZA — координаты точки A (–1000 <= XA, YA, ZA <= 1000), N — количество
планет в системе, B — номер планеты, на которую направляется звездолёт
(1 <= B <= N <= 50) и K — запас
топлива на корабле (1 <= K <= 1000).
Далее идут N строк, каждая из которых содержит
по 4 числа: Xi, Yi, Zi — координаты i-й
планеты (–1000 <= Xi, Yi, Zi <= 1000) и Ci — цена единицы топлива на этой планете (1 <= Ci <= 1000).
Все числа во входных данных целые.
Выведите в выходной файл одно число — минимальное
количество денежных единиц, необходимое для достижения планеты B, или
–1, если невозможно долететь до планеты B.
Пример
|
ввод
|
Вывод
|
|
0
0 0 4 3 3
100
100 0 2
300
0 0 10
400
0 0 1
200
-200 0 3
|
6
|
