cho.shFrom Seoul to Gyeongsan
Choose walking or cycling for each of N legs so the total time is at most K and the total donation is maximal.
Medium5Dynamic programmingBrute forceImplementationNo attempts yetTime limit2sMemory limit512 MBProblem
The actor Han Jeong-ol plans to travel from Seoul to Gyeongsan this summer and collect donations along the way. The cities on the route and the order of the visits are fixed in advance. The trip starts in Seoul, passes through each city exactly once in that order, and ends in Gyeongsan.
Let N be the number of cities other than Seoul. The stretch from Seoul to the second city is leg 1, the stretch from the second city to the third city is leg 2, and the stretch that arrives in Gyeongsan is leg N. There are N legs in total. Han Jeong-ol covers each leg either on foot or by bicycle. For every leg you are given the walking time in minutes, the donation collected by walking in won, the cycling time in minutes, and the donation collected by cycling in won.
As an example, consider a route with two cities between Seoul and Gyeongsan (N=3).
| Leg | Walking time | Walking donation | Cycling time | Cycling donation |
|---|---|---|---|---|
| Leg 1 (Seoul to city A) | 500 minutes | 200 won | 200 minutes | 100 won |
| Leg 2 (city A to city B) | 800 minutes | 370 won | 300 minutes | 120 won |
| Leg 3 (city B to Gyeongsan) | 700 minutes | 250 won | 300 minutes | 90 won |
The choice made on each leg changes both the total donation and the total travel time. With enough time available, walking every leg collects the most, 200 + 370 + 250 = 820 won, and the trip takes 500 + 800 + 700 = 2000 minutes.
Han Jeong-ol can spend only K minutes on the charity trip. In the example above, if K=1650, the best plan walks leg 1 and leg 2 and cycles leg 3, which collects 660 won and takes 1600 minutes.
Given the time and the donation of both options on every leg, write a program that finds the largest donation Han Jeong-ol can collect on a trip from Seoul to Gyeongsan that finishes within K minutes. A trip that finishes within K minutes always exists.
Input
The first line has two natural numbers N and K separated by a space (3≤N≤100, 0<K≤100000).
Each of the next N lines has four natural numbers separated by spaces. Line i+1 describes leg i and gives, in order, the walking time in minutes, the donation collected by walking in won, the cycling time in minutes, and the donation collected by cycling in won. Every time value is at most 10000 and every donation value is at most 1000000. The input has N+1 lines in total.
Output
Print on the first line the largest donation that can be collected on a trip finishing within K minutes.