Задача №112144. Путешествие (A)
Маленький Петя очень любит путешествовать. В стране Берляндия, где он живет, есть N городов, расположенных на одной прямой. Петя пронумеровал их числами от 1 до N в порядке увеличения красоты. Петя находится в городе 1 и хочет попасть в город N . Чтобы не портить впечатления о поездке, он может посещать города только в порядке увеличения номеров (а, следовательно, и красоты). Для перемещения между городами Петя решил воспользоваться услугами единственной авиакомпании страны — Berland Airlines. Стоимость перелета из города i в город j равна c i * | x i - x j | + t j , где x i — координата города i , x j — координата города j , c i — стоимость единицы самолетного топлива в городе i , а t j — стоимость въезда в город j . Чтобы было о чем рассказать друзьям, Петя хочет потратить как можно больше (да-да, именно больше) денег на эту поездку. Помогите ему в этом. Обратите внимание, что Пете не обязательно бывать во всех городах.
Первая строка содержит целое число N — количество городов в Берляндии ( 1 ≤ N ≤ 100 000 ). Далее следуют N строк. Строка с номером i из них содержит 3 целых числа — x i ( - 10 6 ≤ x i ≤ 10 6 ), c i ( 1 ≤ c i ≤ 10 6 ) и t i ( 1 ≤ t i ≤ 10 6 ). Все координаты x i различны.
Выведите искомое наибольшее количество денег, которые Петя может потратить чтобы добраться из города 1 в город N . Гарантируется, что ответ не превышает 10 12 .
Оценивание:
- 0 -ая группа тестов содержит тесты из условия, оценивается в 0 баллов.
- 1 -ая группа тестов содержит тесты c N ≤ 6000 . Оценивается в 50 баллов. Эти баллы выставляются при прохождении всех тестов группы.
-
2
-ая группа тестов. Дополнительных ограничений нет. Оценивается в 50 баллов. Эти баллы выставляются при прохождении всех тестов группы.
4 5 10 2 0 1 10 15 3 14 17 2 3
123
1 709 50 8
0