DESCRIPTION:
A driver is travelling along a route and a capacity of accomodating maximum CAP passengers.There are N requests and each request i(0 to n-1) has 4 information.
request[i][0] = number of passengers to be onboarded
request[i][1] = the start station number
request[i][2] = the stop station number
request[i][3] = the fare per-person
Now, the driver has the liberty to choose any number of passengers less than or equal to requested for each request. The number of passengers in the vehicle cannot be more than CAP.
Help him maximize the total revenue, given the requests.
(Offlining the requests is possible).
CONSTRAINTS:
1<=N=>2000
CAP<=10^9
requests[i][j]<=10^9
EXAMPLE INPUT:
CAP=1
n=3
requests=[[1,10,20,10],[1,20,30,10],[1,10,30,15]]
ANSWER: maximum_revenue = 20
EXPLANATION: Since, going for 3rd request would earn him only 151=15 as revenue, he better go for the first two requests, and he can earn 101 + 10*1 = 20 as revenue.