eolymp
bolt
Спробуйте наш новий інтерфейс для відправки розв'язків
Задачі

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

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

Ліміт часу 2 секунди
Ліміт використання пам'яті 64 MiB

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

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

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

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

Вхідні дані

У першому рядку вхідного файлу задано число N - кількість воріт на трасі (0N500), у наступних двох рядках задано S_x, S_y, F_x, F_y - координати точок старту та фінішу відповідно. У кожному з наступних N рядків записано чотире числа a_i, b_i, y_i, c_i - x-координати лівого та правого кінця воріт, y-координата воріт та штраф за непроходження заданих воріт (a_i < b_i, F_y < y_i < S_y, c_i - ціле число, 0c_i10000). Усі координати - цілі числа, які не перевищують по модулю 10000.

Вихідні дані

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

Приклад

Вхідні дані #1
4
3 6
3 1
5 7 4 1
4 5 5 10
1 2 4 5
2 5 2 0
Вихідні дані #1
7.8126