Чтобы немного подзаработать, Макс решил заняться фрилансом. Изучив предложения на специализированных сайтах, он выбрал N наиболее интересных заказов, и теперь собирается выполнить их все.
Каждый заказ характеризуется стоимостью Pi — количеством рублей, которое Макс получит за выполненную работу. Для каждого из заказов Макс оценил трудоёмкость Ti — количество дней, которое уйдёт на выполнение работы. Наконец, у каждого заказа указан дедлайн Di — номер дня, когда этот заказ требуется выполнить (дни нумеруются с единицы).
Если Макс сдаёт работу позже дедлайна, он обязан заплатить заказчику по 100 рублей за каждый просроченный день. Например, если заказ имеет дедлайн в день 3, а Макс выполнил его в день 5, то Макс оштрафовывается на 200 рублей.
С другой стороны, если Макс сдаёт работу раньше дедлайна, то уже заказчик платит ему по 100 рублей за каждый день, оставшийся до дедлайна. Например, если заказ имеет дедлайн в день 8, а Макс выполнил его в день 4, то Макс получает дополнительные 400 рублей.
Так как Макс достаточно меркантилен, ему интересно, какую максимальную выгоду можно получить, если выполнить все заказы в оптимальном порядке. Помогите ему найти ответ на этот вопрос. Помните, что в каждый из дней Макс может работать только над одним заказом.