Dağ xizəyi yarışları#4784
Bir xizəkçi yarışa hazırlaşır və enişin ən yaxşı yolunu müəyyən etmək üçün xizək yamacının sxemini çəkib. Bu sxemdə yamacdakı qapılar üfüqi parça kimi təsvir olunub. Heç iki qapı üst-üstə düşmür və ya ümumi nöqtəyə malik deyil.
Xizəkçinin yolu dağ zirvəsindən başlayıb, yamacın aşağısında bitən qırıq xətt olmalıdır. Bu qırıq xəttin hər bir növbəti zirvəsi əvvəlkindən ciddi şəkildə kiçik -koordinatına malik olmalıdır. Belə bir yolun nümunəsi şəkildə göstərilmişdir.
Xizəkçi yolunun keçmədiyi hər bir qapı üçün cəza xalları verilir. Enmənin ümumi cəzası, yolun uzunluğu və keçilməmiş qapıların cəza ballarının cəmidir.
Səndən tələb olunan, xizəkçi yamacı başa vuranda ala biləcəyi minimal ümumi cəzanı hesablamaq üçün bir proqram yazmaqdır.
Girişin birinci sətrində — trasda olan qapıların sayı verilir (0 \leq N \leq 500). Sonrakı iki sətrdə başlanğıc və son nöqtələrinin koordinatları təqdim olunur: S_x, S_y, F_x, F_y. Növbəti sətrin hər birində isə dörd ədəd verilir: a_i, b_i, y_i, c_i — qapının sol və sağ ucunun -koordinatları, qapının -koordinatı və həmin qapıdan keçilmədikdə verilən cəza (a_i < b_i, F_y < y_i < S_y, c_i tam ədəddir, 0 \leq c_i \leq 10000). Bütün koordinatlar tam ədədlərdir və modulca -dən böyük deyil.
Xizəkçinin trası başa vurmaq üçün ala biləcəyi minimal ümumi cəzanı ən azı onluq dəqiqliklə çap et.
Nümunə 1