Let's divide all trucks into the classes by *l* + *r* + *c*. It can be seen, that all the trucks that can be included in the answer are in the same class.

Let's solve the problem separately for each class. Consider all trucks from same class in the order they appear, and keep the following value: z[k] = the maximum sum that you can get, if the last taken truck has *r*_{i} = *k*. Consider the truck number *i* - there are 2 options to update z:

It can update z[*r*_{i}] with *z*[*r*_{i} + *c*_{i}] + *v*_{i}, i. e. continue the motorcade, which has last truck with *r* = *r*_{i} + *c*_{i}. (For neighboring trucks should be true the following: *r*_{prev} = *r*_{i} + *c*_{i})

If *l*_{i} = 0, it can update z[*r*_{i}] with *v*_{i}, i. e. became the first truck in the new motorcade. (For the first truck should be true the following: *l*_{i} = 0)

The answer will be in z[0].

To restore the trucks included in the answer, we can keep with the maximal sum in z the index of last truck that updated this sum. Also we store the ancestor p for each truck that updated something in z. This ancestor is calculated when we consider *i*-th truck and doesn't change further: p[i] = -1 if truck *i* became beginning of the motorcade, otherwise p[i] = last truck that updated z[*r*_{i} + *c*_{i}].

We start restore of the answer from last truck updated z[0]. After that we restore everything using only p.

PS The task with "at least" is also solvable with the same limits on input data.