Коммивояжёр решил, что определение оптимального расписания его передвижения по дорогам -- это неразрешимая вычислительная задача. Поэтому он занялся бизнесом, используя только передвижение по реке Данубе, имеющей прямое русло. У него есть моторная лодка, которая может довезти его с любого места на реке до любого другого места реки, не тратя на это абсолютно никакого времени. К сожалению, лодка потребляет очень много горючего. На каждый метр проезда против течения реки (к истоку) потребляется горючее стоимостью U долларов, а на каждый метр проезда по течению реки (от истока) -- D долларов.Коммивояжёр хочет посетить N ярмарок, которые будут проводиться в различных местах, расположенных вдоль реки. Каждая ярмарка длится ровно один день. Для каждой ярмарки с номером X коммивояжёр знает её дату проведения Tx, измеряемую в днях с момента покупки коммивояжёром лодки. Ему также известны место расположения ярмарки Lx, измеряемое в метрах от истока реки в направлении вниз по течению, и количество долларов MX, которые он выручит, если посетит эту ярмарку. Он начинает и заканчивает своё путешествие в своем доме, расположенном в S метрах от истока реки в направлении вниз по течению.Помогите коммивояжёру выбрать, какие ярмарки ему следует посетить (если требуется) и в каком порядке, чтобы получить максимальную общую прибыль по окончании путешествия. Общая прибыль коммивояжёра вычисляется как разность между суммой долларов, которую он выручил от посещения ярмарок, и суммой долларов, потраченной им на горючее при передвижении вверх и вниз по реке.Имейте в виду, что если ярмарка A проводится раньше ярмарки B, то коммивояжёр может посетить их только в порядке их дат проведения (то есть, он не может посетить ярмарку B раньше, чем ярмарку A). Если две ярмарки проводятся в один день, то коммивояжёр может посетить эти две ярмарки в любом порядке в тот же день. Нет ограничения на количество ярмарок, посещаемых в один день, но, естественно, коммивояжёр не может посетить одну ярмарку дважды, получив двойную прибыль. При этом он может проезжать через места уже посещённых ярмарок, не получая никакой прибыли.ЗАДАНИЕНапишите программу, которая по заданным датам проведения ярмарок, их местам расположения и по выручке, получаемой от посещения ярмарок, а также месту расположения дома коммивояжёра и стоимостям переезда, определит максимальную возможную прибыль, которую коммивояжёр может получить по окончании своего путешествия. ВХОДНЫЕ ДАННЫЕВаша программа должна читать из стандартного потока ввода следующие данные:• Первая строка содержит в указанном порядке целые числа N, U, D и S, разделённые одиночными пробелами.• Последующие N строк описывают N ярмарок в произвольном порядке, k-я из этих N строк описывает k-ю ярмарку и содержит три целых числа, разделённых одиночными пробелами: день проведения ярмарки Tk, её место расположения Lk, и выручку, которую может получить коммивояжёр от посещения этой ярмарки Mk. ПРИМЕЧАНИЕ: Все места расположения, указанные во входных данных, будут различны. В частности, никакие две ярмарки не будут проводиться в одном месте, и никакая ярмарка не будет проводиться в том же месте, где находится дом коммивояжёра.ОГРАНИЧЕНИЯ1 <= N <= 500 000 Количество ярмарок1 <= D <= U <= 10 Стоимость перемещения на один метр вверх по течению реки (U) и вниз по течению реки (D)1 <= S <= 500 001 Место расположения дома коммивояжёра1 <= Tk <= 500 000 День, в который проводится ярмарка с номером k1 <= Lk <= 500 001 Место расположения ярмарки с номером k1 <= Mk <= 4 000 Количество долларов, которые коммивояжёр получит в результате посещения ярмарки с номером kВЫХОДНЫЕ ДАННЫЕВаша программа должна вывести в стандартный поток вывода одну строку, содержащую одно целое число: максимальную прибыль, которую коммивояжёр может получить по окончании своего путешествия.