C. Весело смотреть на фейерверки
ограничение по времени на тест
4 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

На главной улице города устраивают фестиваль. Улица поделена на 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