- Prepare
- Algorithms
- Search
- Maximizing Mission Points

# Maximizing Mission Points

# Maximizing Mission Points

Xander Cage has a list of cities he can visit on his new top-secret mission. He represents each city as a tuple of . The values of , , and are distinct across all cities.

We define a mission as a sequence of cities, , that he visits. We define the total of such a mission to be the sum of the of all the cities in his mission list.

Being eccentric, he abides by the following rules on any mission:

- He can choose the number of cities he will visit (if any).
- He can start the mission from any city.
- He visits cities in order of strictly increasing .
- The absolute difference in between adjacent visited cities in his mission must be
*at most*. - The absolute difference in between adjacent visited cities in his mission must be
*at most*.

Given , , and the definitions for cities, find and print the maximum possible total that Xander can earn on a mission.

**Input Format**

The first line contains three space-separated integers describing the respective values of , , and .

Each line of the subsequent lines contains four space-separated integers denoting the respective , , , and for a city.

**Constraints**

**Output Format**

Print a single integer denoting the maximum possible that Xander can earn on a mission.

**Sample Input 0**

```
3 1 1
1 1 1 3
2 2 2 -1
3 3 3 3
```

**Sample Output 0**

```
5
```

**Explanation 0**

Xander can start at city , then go to city , and then go to city for a maximum value of total

Note that he cannot go directly from city to city as that would violate his rules that the absolute difference in between adjacent visited cities be and the absolute difference in between adjacent visited cities be . Because and , he cannot directly travel between those cities.