Задача C. Брокер

Автор:А. Щуров   Ограничение времени:1 сек
Входной файл:input.txt   Ограничение памяти:512 Мб
Выходной файл:output.txt  

Условие

Брокер Лёша решил подзаработать, для чего собирается совершить N звонков в разные банки. Стратегия Лёши проста: он просит у очередного банка деньги и иногда их получает. Банк под номером i может выдать брокеру ровно mi денег и делает это только в том случае, если у брокера на момент звонка уже есть ri денег на счету. С самого начала на счету брокера содержится A денег.

Очередной звонок происходит так: Лёша тратит ti секунд на то, чтобы выяснить, сколько и при каких условиях банк может дать ему денег. Каждая секунда разговора по телефону стоит ему C денег.

Если счет брокера удовлетворяет условию банка, и если самому брокеру выгодно продолжать разговор, он тратит дополнительно ti секунд на совершение сделки и вежливое завершение разговора, после чего ему на счет поступает mi денег. В ином случае Лёша мгновенно отменяет сделку, бросает трубку и получает от банка 0 денег.

Брокеру Лёше выгодно продолжать разговор только в том случае, если прибыль от совершения сделки больше, чем прибыль от её отмены. Прибыль равна разнице между получаемой суммой и затратами на звонок и может быть отрицательной.

Плату за телефонные разговоры списывают со счета брокера один раз в конце дня после совершения всех звонков. Посчитайте баланс счета брокера после списания.

Формат входного файла

В первой строке входные данные содержат три целых числа N, A и C — количество звонков, исходное количество денег на счету и стоимость одной секунды разговора.

В следующих N строках содержится по три числа ti, ri и mi — количество секунд, затрачиваемых на получение информации от i-го банка, требование i-го банка к количеству денег на счету брокера и количество денег, которое i-й банк готов заплатить.

Формат выходного файла

Выходные данные должны содержать одно целое число — баланс счета брокера в конце дня. Баланс может быть отрицательным.

Ограничения

0 ≤ N ≤ 102

0 ≤ A, C, ri, mi ≤ 104

1 ≤ ti ≤ 103

Примеры тестов

Входной файл (input.txt) Выходной файл (output.txt)
1
3 1000 10
10 500 1000
1000 0 20
5 2000 8400
100

0.080s 0.020s 15