Задача H. Гипер-каналы ≡

Условие

На зараженной радиацией планете некоторые точки соединены между собой гипер-каналами. Когда человек заходит в гипер-канал в одной точке, он мгновенно оказывается в другой. Все гипер-каналы двусторонние — то есть их можно использовать для перемещения в обоих направлениях (как из первой точки во вторую, так и из второй в первую).

К сожалению, гипер-каналы платные - каждый проход через гипер-канал стоит 10 у.е.

Перемещаться по поверхности планеты из одной точки в другую, не используя гипер-каналы, чревато для здоровья (радиация, однако!).

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

Формат входного файла

Во входном файле записаны сначала два числа — начальные координаты расположения путешественника, затем еще два числа — координаты точки, куда ему надо попасть. Затем записано число N — количество гипер-каналов на планете (0 \le N \le 500). Затем идет N описаний гипер-каналов. Каждый гипер-канал описывается четверкой чисел. Первые два задают координаты одной из соединяемых гипер-каналом точек, последние два — координаты другой. Все координаты — целые числа, не превышающие по модулю 1000000.

Формат выходного файла

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

Примеры тестов

10 10
-10 -10
1
2 2 3 3

171717

10 10
-10 -10
2
-10 -10 1 1
10 10 1 1

20

10 10
10 10
4
1 1 2 2
10 10 20 20
2 2 1 1 
10 10 20 20

0