Комівояжер
Комівояжер вирішив, що визначення оптимального розкладу його пересування дорогами — це нерозв'язна обчислювальна задача. Тому він зайнявся бізнесом, використовуючи лише пересування по річці Дунай, яка має пряме русло. У нього є моторний човен, який може довезти його з будь-якого місця на річці до будь-якого іншого місця річки, не витрачаючи на це абсолютно ніякого часу. На жаль, човен споживає дуже багато пального. На кожен метр проїзду проти течії річки (до витоку) споживається пальне вартістю u доларів, а на кожен метр проїзду за течією річки (від витоку) — d доларів.
Комівояжер хоче відвідати n ярмарків, які будуть проводитися в різних місцях, розташованих вздовж річки. Кожен ярмарок триває рівно один день. Для кожного ярмарку з номером x комівояжер знає його дату проведення t_x, вимірювану в днях з моменту покупки комівояжером човна. Йому також відомі місце розташування ярмарку l_x, вимірюване в метрах від витоку річки в напрямку вниз за течією, і кількість доларів m_x, які він отримає, якщо відвідає цей ярмарок. Він починає і закінчує свою подорож у своєму домі, розташованому в s метрах від витоку річки в напрямку вниз за течією.
Допоможіть комівояжеру вибрати, які ярмарки йому слід відвідати (якщо потрібно) і в якому порядку, щоб отримати максимальний загальний прибуток по закінченні подорожі. Загальний прибуток комівояжера обчислюється як різниця між сумою доларів, яку він отримав від відвідування ярмарків, і сумою доларів, витраченою ним на пальне при пересуванні вгору і вниз по річці.
Майте на увазі, що якщо ярмарок A проводиться раніше ярмарку B, то комівояжер може відвідати їх тільки в порядку їх дат проведення (тобто, він не може відвідати ярмарок B раніше, ніж ярмарок A). Якщо два ярмарки проводяться в один день, то комівояжер може відвідати ці два ярмарки в будь-якому порядку в той же день. Немає обмеження на кількість ярмарків, відвідуваних в один день, але, звісно, комівояжер не може відвідати один ярмарок двічі, отримавши подвійну вигоду. При цьому він може проїжджати через місця вже відвіданих ярмарків, не отримуючи ніякої вигоди.
Напишіть програму, яка за заданими датами проведення ярмарків, їх місцями розташування і за виручкою, отримуваною від відвідування ярмарків, а також місцем розташування дому комівояжера і вартостями переїзду, визначить максимальний можливий прибуток, який комівояжер може отримати по закінченні своєї подорожі.
Вхідні дані
Перша рядок містить у зазначеному порядку цілі числа n, u, d і s, розділені одиночними пробілами. Наступні n рядків описують n ярмарків у довільному порядку, k-й з цих n рядків описує k-й ярмарок і містить три цілі числа, розділені одиночними пробілами: день проведення ярмарку t_k, його місце розташування l_k, і виручку, яку може отримати комівояжер від відвідування цього ярмарку m_k.
Усі місця розташування ярмарків різні. Зокрема, жодні два ярмарки не будуть проводитися в одному місці, і жоден ярмарок не буде проводитися в тому ж місці, де знаходиться дім комівояжера. ОБМЕЖЕННЯ 1 <= N <= 500 000 Кількість ярмарків 1 <= D <= U <= 10 Вартість переміщення на один метр вгору за течією річки (U) і вниз за течією річки (D) 1 <= S <= 500 001 Місце розташування дому комівояжера 1 <= Tk <= 500 000 День, в який проводиться ярмарок з номером k 1 <= Lk <= 500 001 Місце розташування ярмарку з номером k 1 <= Mk <= 4 000 Кількість доларів, які комівояжер отримає в результаті відвідування ярмарку з номером k Вхідні дані
Вивести один рядок, що містить одне ціле число - максимальний прибуток, який комівояжер може отримати по закінченні своєї подорожі.