Tramvay
Hər səhər şəhərin kənarından mərkəzinə eyni marşrutla tramvayda n nəfər səyahət edir. Uzun müddətlik səyahətlərdən sonra onlar bir-birini kifayət qədər yaxşı tanıyıblar. Heç kimin inciməməsi üçün, kimlərin oturmalı və kimlərin dayanmalı olduğunu, həmçinin hansı dayanacaqlar arasında bu qərarın verilməli olduğunu müəyyən etmək istəyirlər. Bütün dayanacaqlar 1 -dən p-ə qədər nömrələnib.
Sərnişinlərdən biri riyazi modelləşdirmə üzrə mütəxəssisdir. O, sərnişinlərin ümumi məmnuniyyət dəyərini nəzərə almağı təklif etdi. Hər bir i-ci sərnişin üçün iki dəyər qiymətləndirilib — a_i və b_i. Əgər sərnişin bir dayanacaq arasında oturursa, ümumi məmnuniyyətə a_i əlavə olunur, əgər o dayanırsa, b_i əlavə olunur.
Tramvayda cəmi m oturacaq var. Sərnişinlər istənilən dayanacaqda dərhal oturub-dura bilərlər. Bundan əlavə, bəzi sərnişinlər boş yerlər olsa belə, ayaq üstə səyahət etməyə üstünlük verirlər (onlar üçün a_i < b_i).
Hər bir i-ci sərnişin üçün a_i və b_i dəyərləri, həmçinin tramvaya mindiyi və düşdüyü dayanacaqların nömrələri məlum olduqda, maksimal əldə edilə bilən ümumi məmnuniyyət dəyərini hesablayan proqram yazın.
Giriş verilənləri
Birinci sətir boşluqla ayrılmış üç tam ədəd n, m və p (1 ≤ n, m, p ≤ 100 000, 2 ≤ p) - sərnişinlərin sayı, oturacaq yerlərin sayı və marşrutdakı dayanacaqların sayı.
Sonrakı n sətirin hər biri növbəti sərnişin haqqında dörd tam ədəd a_i, b_i, c_i, d_i şəklində məlumat verir: ilk iki ədəd məmnuniyyət parametrinə töhfəni müəyyən edir, üçüncü - sərnişinin tramvaya mindiyi dayanacağın nömrəsi, sonuncu - tramvaydan düşdüyü dayanacağın nömrəsi (-10^6 ≤ a_i, b_i ≤ 10^6, 1 ≤ c_{i }< d_{i }≤ p).
Çıxış verilənləri
Sərnişinlərin əldə edə biləcəyi maksimal ümumi məmnuniyyəti çıxarın.
Nümunə üçün şərhlər
Maksimal ümumi məmnuniyyət aşağıdakı şəkildə əldə edilir:
Birinci dayanacaqda ikinci və üçüncü sərnişinlər daxil olur və otururlar;
İkinci dayanacaqda birinci və dördüncü sərnişinlər daxil olur, ikinci sərnişin birinciyə yer verir;
Üçüncü dayanacaqda birinci və üçüncü sərnişinlər qalxır və düşür, ikinci və dördüncü sərnişinlər onların yerlərinə otururlar;
Dördüncü dayanacaqda birinci və üçüncü sərnişinlər düşür.