Гірськолижні змагання#4784

Гірськолижні змагання

2 секунди

64 мегабайти

Легка

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

Маршрут лижника має бути ламаною лінією, яка починається на вершині гори й закінчується внизу. Кожна наступна вершина цієї ламаної повинна мати строго меншу $y$ -координату, ніж попередня. Приклад такого маршруту показано на рисунку.

За кожні ворота, через які маршрут лижника не проходить, нараховуються штрафні бали. Загальний штраф за спуск — це сума довжини маршруту й штрафних балів за усі непройдені ворота.

Ваше завдання — написати програму, яка обчислить мінімально можливий загальний штраф, який може отримати лижник, проходячи трасу.

Вхідні дані

У першому рядку вхідних даних задано число $N$ — кількість воріт на трасі ( $0 \leq N \leq 500$ 0 \leq N \leq 500). Наступні два рядки містять координати початкової та кінцевої точок: $S_{x}$ S_x, $S_{y}$ S_y, $F_{x}$ F_x, $F_{y}$ F_y. Кожен з наступних $N$ рядків містить чотири числа: $a_{i}$ a_i, $b_{i}$ b_i, $y_{i}$ y_i, $c_{i}$ c_i — $x$ -координати лівого й правого кінців воріт, $y$ -координату воріт та штраф за непроходження цих воріт ( $a_{i} < b_{i}$ a_i < b_i, $F_{y} < y_{i} < S_{y}$ F_y < y_i < S_y, $c_{i}$ c_i — ціле число, $0 \leq c_{i} \leq 10000$ 0 \leq c_i \leq 10000). Всі координати — цілі числа й не перевищують $10000$ за абсолютним значенням.

Вихідні дані

Виведіть мінімально можливий загальний штраф за проходження траси з точністю не менш ніж $4$ знаків після коми.

Приклади

Приклад 1