You are given an integer capacity and a list requests. A vehicle with capacity seats travels along a line of stations, visiting them in increasing order of station number.
Each element in requests contains [count, from, to, price] meaning that up to count seats are wanted from station from to station to, and each of those seats earns price if you serve it.
For each request you may serve any number of seats from 0 to count. A seat you serve is occupied from station from until station to. It is free again from station to onward, so a request that ends at a station and a request that starts at that same station can share one seat. At no point of the route may more than capacity seats be occupied at once.
Return the maximum total revenue.
Examples
Example 1
Input: capacity = 1, requests = [[1,10,20,10],[1,20,30,10],[1,10,30,15]]
Output: 20
Explanation: The first request ends at station 20 and the second starts there, so the single seat covers both and earns 10 + 10 = 20. Serving the third request instead would earn only 15.
Example 2
Input: capacity = 3, requests = [[3,1,5,4],[2,2,3,9]]
Output: 22
Explanation: Serving 2 seats for the second request earns 2 * 9 = 18. Those seats are occupied from station 2 to station 3, which leaves 1 free seat there, so 1 seat for the first request adds 4.
Example 3
Input: capacity = 2, requests = [[3,1,4,7]]
Output: 14
Explanation: The request wants 3 seats but the vehicle has only 2, so at most 2 seats are served, earning 2 * 7 = 14.
Constraints
1≤n≤2000 where n=requests.length
1≤capacity≤109
requests[i] is [count, from, to, price]
1≤count≤1000
1≤from<to≤109
1≤price≤500
Loading editor...
Run checks the sample cases; Submit runs every case.
Samples 3
Custom 0
passedwrong answertime limiterrorran, no expected valuenot run