Dağ xizəyi yarışları
Görkəmli xizəkçi yarışlara hazırlaşarkən, eniş üçün optimal marşrutu seçmək məqsədilə kağız üzərində xizək trasının sxemini çəkdi. Bu sxemdə tras üzərində yerləşən qapılar üfüqi seqmentlərlə göstərilib və heç bir qapı cütü ortaq nöqtəyə malik deyil.
Marşrut dağın zirvəsindəki start nöqtəsindən başlayıb, ətəyindəki finiş nöqtəsində bitən qırıq xətt olmalıdır. Marşrut elə seçilməlidir ki, qırıq xəttin hər növbəti zirvəsinin y-koordinatı əvvəlki zirvəsinin y-koordinatından ciddi şəkildə kiçik olsun. Mümkün marşrutlardan biri şəkildə göstərilib.
Marşrutdan keçməyən hər qapı üçün xizəkçiyə cərimə xalları verilir. Marşrut üzrə eniş üçün ümumi cərimə, marşrutun uzunluğu və keçilməmiş qapılar üçün cərimə xallarının cəmi kimi hesablanır.
Trasdan keçərkən xizəkçinin ala biləcəyi minimal ümumi cəriməni müəyyən edən proqram yazmaq lazımdır.
Giriş verilənləri
Giriş faylının birinci sətirində trasdakı qapıların sayı N verilir (0 ≤ N ≤ 500), növbəti iki sətirdə isə start və finiş nöqtələrinin koordinatları S_x, S_y, F_x, F_y verilir. Növbəti N sətirdə hər biri dörd ədəd a_i, b_i, y_i, c_i - qapının sol və sağ ucunun x-koordinatları, qapının y-koordinatı və verilmiş qapıdan keçməmək üçün cərimə (a_i < b_i, F_y < y_i < S_y, c_i - tam ədəd, 0 ≤ c_i ≤ 10000) yazılıb. Bütün koordinatlar modulu 10000-dən çox olmayan tam ədədlərdir.
Çıxış verilənləri
Çıxış faylında trasdan keçmək üçün mümkün olan ən kiçik ümumi cəriməni ən az 4 ondalık dəqiqliklə göstərin.