Квадрокоптер#11015
Для підвищення обороноздатності країни та з метою повітряної розвідки все активніше використовують квадрокоптери.
Квадрокоптер — це безпілотний літальний апарат, який виконує польоти між пунктами на місцевості. Дальність польоту квадрокоптера обмежена зарядом акумулятора.
Відомі координати пунктів на місцевості, між якими може пересуватися квадрокоптер. Також відомо, у яких пунктах є можливість заряджання квадрокоптера.
Яку мінімальну відстань має пролетіти квадрокоптер (за потребою із підзарядкою у відповідних пунктах, де є така можливість), щоб потрапити з пункту до пункту ? Відомо, що квадрокоптер перед вильотом з пункту має максимальний рівень заряду акумулятора.
У першому рядку записано п’ять чисел:
— кількість населених пунктів (1 \leq N \leq 1000),
— кількість пунктів, у яких є можливість зарядки акумулятора квадрокоптера (1 \leq K \leq N),
— максимальна відстань, яку може пролетіти квадрокоптер із повністю зарядженим акумулятором (дійсне число),
— пункт, з якого вилітає квадрокоптер (1 \leq A \leq N),
— пункт, у який має прибути квадрокоптер (1 \leq B \leq N).
Наступні рядків містять по два числа — - та -координати пунктів.Наступний рядок містить чисел, розділених пробілами — номери пунктів, у яких є можливість зарядки квадрокоптера.
Виведіть дійсне число — мінімальну відстань, яку має пролетіти квадрокоптер, щоб потрапити з пункту у пункт , або , якщо цього зробити не можна.
Приклад 1
Всього є пункти, з них має можливість заряджання акумулятора квадрокоптера. Максимальна відстань, яку може пролетіти квадрокоптер без підзарядки — , квадрокоптер вирушає з пункту і має прилетіти у пункт . Координати пунктів: 1\,(-3,3), 2\,(-3,-2), 3\,(2,2), 4\,(2,-2). Пункт, що має можливість підзарядки — .
Квадрокоптер вирушає з початкового пункту , далі летить у пункт , пролітаючи відстань , далі виконується заряджання акумулятора і переліт у фінальний пункт (відстань — ). Таким чином, сумарна відстань — .
