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.