Супершпион Лэнс Стерлинг находится в городе и отправляется на задание. Для удобства, введем в городе прямоугольную систему координат, единичный отрезок которой имеет длину один метр. Сейчас Лэнс находится в тайном убежище в точке с координатами $$$(x_s, y_s)$$$, ему требуется добраться до точки с координатами $$$(x_t, y_t)$$$. Он может перемещаться со скоростью один метр в секунду в любом направлении. Однако, он очень проголодался, поэтому решил перед заданием заскочить перекусить.
Всего в городе есть $$$n$$$ заведений, в которых Лэнс может пообедать. Заведение номер $$$i$$$ находится в точке $$$(x_i, y_i)$$$, и Лэнс знает, что он проведет в нем ровно $$$t_i$$$ секунд. Помогите ему определить минимальное время, которое потребуется, чтобы добраться до точки назначения, зайдя по пути перекусить в одно из заведений.
В первой строке даны четыре целых числа $$$x_s$$$, $$$y_s$$$, $$$x_t$$$ и $$$y_t$$$ — координаты тайного убежища и точки назначения ($$$|x_s|, |y_s|, |x_t|, |y_t| \le 1\,000$$$).
В следующей строке дано одно целое число $$$n$$$ — количество заведений, где Лэнс может пообедать ($$$1 \le n \le 1\,000$$$).
В следующих $$$n$$$ строках дано по три целых числа $$$x_i$$$, $$$y_i$$$ и $$$t_i$$$ — координаты $$$i$$$-го заведения и количество секунд, которое придется потратить, чтобы пообедать в этом заведении ($$$|x_i|, |y_i| \le 1\,000$$$; $$$1 \le t_i \le 1\,000$$$).
Выведите одно вещественное число — минимальное количество секунд, которое потребуется Лэнсу, чтобы добраться из убежища до точки назначения, зайдя по пути перекусить. Ответ будет считаться правильным, если его абсолютная или относительная погрешность не будет превышать $$$10^{-9}$$$.
Баллы за каждую подзадачу начисляются только в случае, если все тесты для этой подзадачи и необходимых подзадач успешно пройдены.
| Подзадача | Баллы | Ограничения | Необходимые подзадачи | Информация о проверке |
| 1 | 20 | $$$y_s, y_t, y_i = 0$$$ | первая ошибка | |
| 2 | 20 | $$$n = 1$$$ | первая ошибка | |
| 3 | 60 | Нет дополнительных ограничений | 1, 2 | первая ошибка |
0 0 10 0 1 5 0 3
13.000000000000000
0 -5 0 -3 1 0 5 10
28.000000000000000
0 0 5 5 2 3 3 2 3 4 1
8.236067977499790
