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