eolymp
bolt
Try our new interface for solving problems
Məsələlər

Однажды в Китае 2

Однажды в Китае 2

Zaman məhdudiyyəti 1 saniyə
Yaddaşı istafadə məhdudiyyəti 256 MiB

Скоро увидит свет новая компьютерная игра "Однажды в Китае". Пока же приходится довольствоваться демо-версией. Игра заключается примерно в следующем: один джигит овладевает искусством кунг-фу и начинает обходить разные бандитские логова, где он избивает плохишей и попутно забирает у них награбленные деньги. Уровень владения кунг-фу выражается неким неотрицательным целым числом.

Всего в игре N бандитских логов. i-тое логово имеет три показателя: Q_i, S_i и M_i. Число Q_i указывает минимальное владение кунг-фу, которое должно быть у джигита, чтобы он смог ограбить бандитов в логове i. Если его владение кунг-фу менее Q_i, ему туда лучше не соваться. S_i – это сумма (в юанях), которую сможет забрать джигит из i-ого логова, если его владение кунг-фуQ_i.

Если же его кунг-фу лучше, то он может выбить у бандитов и побольше деньжат. А конкретно, если владение кунг-фу (обозначим его K) в диапазоне от Q_i до Q_i·M_i включительно, джигит заберёт у бандитов сумму S_i·(K/Q_i). Если владение кунг-фу превосходит Q_i·M_i, джигит заберёт ровно S_i·M_i, потому что больше оттуда забирать нечего.

Звучит всё просто, но есть один подвох. Кунг-фу джигит должен обучаться у мастера Цзен, который за каждый час тренировки берёт 1 юань. А как известно, чем выше уровень ученика, тем дольше ему надо заниматься для повышения квалификации. Чтобы повысить уровень от X_1 до X_2, парню нужно A·(X_2^2-X_1^2) часов.

Мастер Цзен проводит тренировки только длительностью в целое количество часов. Он может обучать в кредит, чтобы джигит вернул ему деньги после применения своих навыков.

Учитывая, что в начале игры джигит не владеет кунг-фу (т.е. его уровень 0) и его баланс на нуле, найдите максимально возможную прибыль (т.е. разницу между отбитыми у бандитов средствами и потраченной на тренировки суммой), которую он может получить.

Giriş verilənləri

Первая строка содержит числа N (1N1000) и A (0A10, число дано не более чем с 3 знаками после запятой).

Каждая из следующих N строк содержит числа Q_i, S_i и M_i (1Q_i, S_i1000, 1M_i10. Числа M_i, S_i и Q_i – целые).

Çıxış verilənləri

Одно число - максимальная прибыль джигита. Ваш ответ должен отличаться от правильного не более, чем на 0.000001 (1e-6).

Müəllif Эльдар Богданов
Mənbə Зимняя школа, Харьков 2009, контест Теодора Заркуа и его учеников