We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  • Hackerrank Home
  • Prepare
    NEW
  • Certify
  • Compete
  • Career Fair
  • Hiring developers?
  1. Prepare
  2. Algorithms
  3. Search
  4. Maximizing Mission Points

Maximizing Mission Points

Problem
Submissions
Leaderboard
Discussions
Editorial

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

image

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.

Author

pranet

Difficulty

Hard

Max Score

70

Submitted By

3415

Need Help?


View discussions
View editorial
View top submissions

rate this challenge

MORE DETAILS

Download problem statement
Download sample test cases
Suggest Edits
  • Blog
  • Scoring
  • Environment
  • FAQ
  • About Us
  • Support
  • Careers
  • Terms Of Service
  • Privacy Policy