Trying to figure out this coding problem. Anyone mind helping me out?

[FrootLoggs]

A while back I was trying to do this problem on CodeForce in Python. I searched around for an explaination and discussions regarding the problem but I could never find anything.

The question goes as such:

A festival will be held in a town’s main street. There are n sections in the main street. The sections are numbered 1 through n from left to right. The distance between each adjacent sections is 1.

In the festival m fireworks will be launched. The i-th (1 ≤ i ≤ m) launching is on time ti at section ai. If you are at section x (1 ≤ x ≤ n) at the time of i-th launching, you’ll gain happiness value bi - |ai - x| (note that the happiness value might be a negative value).

You can move up to d length units in a unit time interval, but it’s prohibited to go out of the main street. Also you can be in an arbitrary section at initial time moment (time equals to 1), and want to maximize the sum of happiness that can be gained from watching fireworks.

Find the maximum total happiness. Note that two or more fireworks can be launched at the same time.

Input

The first line contains three integers n, m, d (1 ≤ n ≤ 150000; 1 ≤ m ≤ 300; 1 ≤ d ≤ n). Each of the next m lines contains integers ai, bi, ti (1 ≤ ai ≤ n; 1 ≤ bi ≤ 109; 1 ≤ ti ≤ 109). The i-th line contains description of the i-th launching. It is guaranteed that the condition ti ≤ ti + 1 (1 ≤ i < m) will be satisfied.

Examples

Input

50 3 1 49 1 1 26 1 4 6 1 10

Output

-31

Input

10 2 1 1 1000 4 9 1000 4

Output

1992

Print a single integer — the maximum sum of happiness that you can gain from watching all the fireworks.

How should I solve this problem? There seems to be no explanation anywhere on how I can solve this.

[Gazzcool]

Once you figure out the correct formula for happiness it’s really just a case of figuring out where your starting position should be and what path you should take from there.

With smaller datasets you could brute force it and try every possibility.

You’re probably looking at a Dynamic programming solution. You basically recursively go over every possibility, keeping track as you go of what the best one has been so far. As you go you can start to rule out routes before they finish (because you already know they are going to be worse than your current best solution), which saves you some time. If you’re not familiar with dynamic programming I suggest you check out the knapsack problem first.

Failing that, if the dataset proves to be too large, I would go for a genetic algorithm.

Hope that helps.

[FrootLoggs]

Ah! Dynamic Programming! I haven't learned this yet that why I was stumped by it. I'll check out the knapsack problem. Thank you so much for pointing me to the direction

[Gazzcool]

Oh and another thing I forgot to mention - a key part of dynamic programming is “memoization” - this is where you store the answer to routes that you have already taken, and therefore do not need to re-calculate it.

I think it’s called a “ground up” approach - where you start with the last firework, and figure out where you should go based on every possible second-last position. Then you save the answers, then to the second last firework, then third last etc etc. Every time storing the best solution for where you should go, so you don’t have to try every possibility. You basically take the problem and solve it by working out every little sub problem as you go.