Коммивояжер
Коммивояжер, yollar üzrə hərəkət cədvəlini optimallaşdırmağın mümkün olmadığını düşündüyü üçün, yalnız Dunay çayı boyunca hərəkət edərək bizneslə məşğul olmağa qərar verdi. Onun bir motorlu qayığı var və bu qayıqla çayın istənilən nöqtəsindən digərinə heç bir vaxt sərf etmədən gedə bilər. Təəssüf ki, qayıq çox yanacaq sərf edir. Çayın axarına qarşı hər metr üçün (mənbəyə doğru) yanacaq dəyəri u dollar, çayın axarına doğru hər metr üçün isə d dollar sərf olunur.
Коммивояжер n yarmarkaya baş çəkmək istəyir, bu yarmarkalar çayın müxtəlif yerlərində keçiriləcək. Hər yarmarka bir gün davam edir. Hər x nömrəli yarmarka üçün коммивояжер onun keçirilmə tarixini t_x bilir, bu tarix коммивояжер qayığı aldıqdan sonra günlərlə ölçülür. Ona həmçinin yarmarkanın yerləşdiyi yer l_x məlumdur, bu yer çayın mənbəyindən aşağı axın istiqamətində metrlə ölçülür, və əgər o, bu yarmarkaya baş çəkərsə, əldə edəcəyi dollar miqdarı m_x məlumdur. O, səyahətinə öz evində başlayır və bitir, bu ev çayın mənbəyindən aşağı axın istiqamətində s metr məsafədə yerləşir.
Коммивояжerə hansı yarmarkalara baş çəkməli olduğunu (əgər tələb olunursa) və hansı ardıcıllıqla baş çəkməli olduğunu seçməkdə kömək edin ki, səyahətinin sonunda maksimum ümumi mənfəət əldə etsin. Коммивояжerın ümumi mənfəəti yarmarkalara baş çəkməkdən əldə etdiyi dollarların cəmi ilə çay boyunca yuxarı və aşağı hərəkət edərkən sərf etdiyi dollarların fərqi kimi hesablanır.
Nəzərə alın ki, əgər A yarmarkası B yarmarkasından əvvəl keçirilirsə, коммивояжer onlara yalnız keçirilmə tarixləri ardıcıllığı ilə baş çəkə bilər (yəni, o, B yarmarkasına A yarmarkasından əvvəl baş çəkə bilməz). Əgər iki yarmarka eyni gündə keçirilirsə, коммивояжer həmin gün bu iki yarmarkaya istənilən ardıcıllıqla baş çəkə bilər. Bir gündə baş çəkilən yarmarkaların sayına məhdudiyyət yoxdur, lakin təbii ki, коммивояжer bir yarmarkaya iki dəfə baş çəkib ikiqat mənfəət əldə edə bilməz. Bununla belə, o, artıq baş çəkilmiş yarmarkaların yerlərindən keçə bilər, lakin heç bir mənfəət əldə etmədən.
Yarmarkaların keçirilmə tarixləri, onların yerləşdiyi yerlər və yarmarkalara baş çəkməkdən əldə edilən mənfəət, həmçinin коммивояжerın evinin yerləşdiyi yer və hərəkət xərcləri verildikdə, коммивояжerın səyahətinin sonunda əldə edə biləcəyi maksimum mümkün mənfəəti müəyyən edən proqram yazın.
Giriş verilənləri
Birinci sətir ardıcıllıqla n, u, d və s tam ədədlərini ehtiva edir, tək boşluqlarla ayrılmışdır. Sonrakı n sətir n yarmarkanı təsvir edir, bu n sətirdən k-cı k-cı yarmarkanı təsvir edir və tək boşluqlarla ayrılmış üç tam ədəd ehtiva edir: yarmarkanın keçirilmə günü t_k, onun yerləşdiyi yer l_k və коммивояжerın bu yarmarkaya baş çəkməkdən əldə edə biləcəyi mənfəət m_k.
Bütün yarmarkaların yerləşdiyi yerlər fərqlidir. Xüsusilə, heç bir iki yarmarka eyni yerdə keçirilməyəcək və heç bir yarmarka коммивояжerın evinin yerləşdiyi yerdə keçirilməyəcək. MƏHDUDİYYƏTLƏR1 <= N <= 500 000 Yarmarkaların sayı1 <= D <= U <= 10 Çayın axarına qarşı hər metr üçün hərəkət xərci (U) və çayın axarına doğru hər metr üçün hərəkət xərci (D)1 <= S <= 500 001 Коммивояжerın evinin yerləşdiyi yer1 <= Tk <= 500 000 k nömrəli yarmarkanın keçirildiyi gün1 <= Lk <= 500 001 k nömrəli yarmarkanın yerləşdiyi yer1 <= Mk <= 4 000 k nömrəli yarmarkaya baş çəkməkdən əldə edilən dollar miqdarı Giriş məlumatları
Bir sətirdə bir tam ədəd çıxarın - коммивояжerın səyahətinin sonunda əldə edə biləcəyi maksimum mənfəət.