Антон сторож на очень важном объекте. Как и положено всем важным объектам, он обнесён забором. Правда, время не пощадило этот забор, и в нём есть дыры, через которые на объект могут попадать нарушители.
Известно, что изначально забор состоял из n столбов и n соединяющих их секций. Забор ограничивал территорию, являющуюся выпуклым многоугольником. Однако, со временем, некоторые секции забора развалились и теперь через эти дыры можно почти беспрепятственно пройти внутрь: Антону сложно следить за всеми дырами в заборе. Известно, что в заборе нет двух отсутствующих секций подряд.
Поняв, что, если на объект будет попадать слишком много нарушителей, Антон решил взять инициативу в свои руки и заделать некоторые дыры. Для этого он попросил у начальства моток колючей проволоки. Полученный им моток из l метров колючей проволоки нужно будет потом вернуть в целости, поэтому Антону запрещено его резать. Антон может закрепить один из концов мотка с проволокой в любом месте на границе объекта.
После чего, он может пойти вдоль границы по или против часовой стрелки, разматывая моток, и закрепить второй конец там, где он остановился. Он хочет выбрать место, с которого ему нужно начинать так, чтобы оставшиеся в заборе дыры имели минимально возможную длину. Помогите ему определить эту длину.
Формат входных данных
В первой строке входного файла содержится три целых числа n (3 <= n <= 105) количество столбов в заборе, l (0 <= l <= 1018) длина выданного Антону мотка проволоки и k (0 <= k <=n/2) количество дыр в заборе.
Во второй строке по возрастанию заданы k чисел ai (1 < ai <= n). Числу ai соответствует отсутствие секции забора между столбами ai и ai+1 mod n. Гарантируется, что из двух соседних секций хотя бы одна не отсутствует.
В следующих n строках находится по два целых числа xi и yi (|xi| <= 1018, |yi| <= 1018) координаты i-го столба забора. Многоугольник может быть задан в порядке обхода как по, так и против часовой стрелки.
Формат выходных данных
Выведите единственное число минимальную суммарную длину дыр в заборе после установки колючей проволоки. Ответ будет считаться правильным, если если он отличается от правильного не более, чем на p · 10?6
, где p периметр многоугольника.
Примеры
|
Ввод |
Вывод |
6 4 3
1 3 5
0 0
3 0
4 1
3 2
0 2
-1 1 |
2.82842712474619 |