Codeforces Round 219 (Div. 1) |
---|
Закончено |
На главной улице города устраивают фестиваль. Улица поделена на n участков, пронумерованных от 1 до n слева направо. Расстояние от любого участка до соседнего равно 1.
На фестивале запустят m фейерверков. При этом, i-ый (1 ≤ i ≤ m) запуск придется на время ti в участке ai. Если вы будете в участке x (1 ≤ x ≤ n) во время i-ого запуска, вы получите счастья в размере bi - |ai - x| (обратите внимание, что значение счастья может быть отрицательным).
За единичный промежуток времени вы можете пройти до d единиц длины, но сходить с главной улицы запрещено. В начальный момент времени (момент времени 1) вы можете оказаться на произвольном участке, ваша цель — максимизировать сумму полученного от просмотра фейерверков счастья. Найдите наибольшее суммарное счастье.
Обратите внимание, что в одно время могут запускаться два или несколько фейерверков.
В первой строке записано три целых числа n, m, d (1 ≤ n ≤ 150000; 1 ≤ m ≤ 300; 1 ≤ d ≤ n).
В каждой из следующих m строк записаны целые числа ai, bi, ti (1 ≤ ai ≤ n; 1 ≤ bi ≤ 109; 1 ≤ ti ≤ 109). В i-ой строке записано описание i-ого запуска.
Гарантируется, что условие ti ≤ ti + 1 (1 ≤ i < m) будет удовлетворено.
Выведите единственное целое число — максимальную сумму счастья, которую можно получить от просмотра всех фейерверков.
Пожалуйста, не используйте спецификатор %lld для чтения или записи 64-битных чисел на С++. Рекомендуется использовать потоки cin, cout или спецификатор %I64d.
50 3 1
49 1 1
26 1 4
6 1 10
-31
10 2 1
1 1000 4
9 1000 4
1992
Название |
---|