Задача №111128. Проезд через мегаполис
Мегаполис будущего представляет собой прямоугольную сетку из улиц. Улицы параллельны осям координат и пересекаются в точках с целыми координатами x и y. Чтобы проехать от перекрестка A с координатами xa, ya до перекрестка B с координатами xb, yb необходимо проехать |xa - xb| + |ya - yb| кварталов. Обычно, время проезда одного квартала составляет 10 минут, так что кто угодно способен быстро вычислить время своей поездки от A до B. Однако пробки, возникающие в мегаполисе, делают задачу вычисления минимального времени поездки очень сложной, и имеено поэтому ее предстоит решить вам.
Пробка в мегаполисе представляют собой прямоугольник, определенный координатами левого нижнего и правого верхнего угла. Время проезда одного блока в пробке задается для каждой из пробок отдельно. Пробка существует на всех улицах, находящихся внутри прямоугольной области. Иногда пробку быстрее объехать, но иногда лучше все же ехать через пробку. Оба этих случая представлены в примере и на рисунке.
Первая строка входного файла содержит четыре целых числа xa, ya, xb, yb — координаты начального и конечного перекрестков. Вторая строка содержит одно целое число N (1 ≤ N ≤ 1 000) — количество пробок в мегаполисе. Следующие N строк описывают пробки. Каждая пробка описывается пятью числами: x1, i, y1, i, x2, i, y2, i и ti, где первые 4 числа — координаты левого нижнего и правого верхнего углов пробки, а ti (10 ≤ ti ≤ 108) — время проезда одного квартала в этой пробке. Все координаты во входных данных могут принимать значения от 0 до 108, включительно. Области пробок не пересекаются и не касаются. Начальный и конечный перекрестки различны и не находятся ни в пробке, ни на ее границе.
Выведите одно число — минимальное время поездки.
1 6 15 3
4
2 1 3 7 44
5 2 10 4 33
8 5 11 9 22
12 1 14 8 11
192