#P480D. Parcels
-
ID: 3110
Type: RemoteJudge
2000ms
256MiB
Tried: 0
Accepted: 0
Difficulty: (None)
Uploaded By:
Hydro
Tags> Parcels
No submission language available for this problem.
Description
Jaroslav owns a small courier service. He has recently got and introduced a new system of processing parcels. Each parcel is a box, the box has its weight and strength. The system works as follows. It originally has an empty platform where you can put boxes by the following rules:
- If the platform is empty, then the box is put directly on the platform, otherwise it is put on the topmost box on the platform.
- The total weight of all boxes on the platform cannot exceed the strength of platform S at any time.
- The strength of any box of the platform at any time must be no less than the total weight of the boxes that stand above.
You can take only the topmost box from the platform.
The system receives n parcels, the i-th parcel arrives exactly at time ini, its weight and strength are equal to wi and si, respectively. Each parcel has a value of vi bourles. However, to obtain this value, the system needs to give the parcel exactly at time outi, otherwise Jaroslav will get 0 bourles for it. Thus, Jaroslav can skip any parcel and not put on the platform, formally deliver it at time ini and not get anything for it.
Any operation in the problem is performed instantly. This means that it is possible to make several operations of receiving and delivering parcels at the same time and in any order.
Please note that the parcel that is delivered at time outi, immediately gets outside of the system, and the following activities taking place at the same time are made without taking it into consideration.
Since the system is very complex, and there are a lot of received parcels, Jaroslav asks you to say what maximum amount of money he can get using his system.
The first line of the input contains two space-separated integers n and S (1 ≤ n ≤ 500, 0 ≤ S ≤ 1000). Then n lines follow, the i-th line contains five space-separated integers: ini, outi, wi, si and vi (0 ≤ ini < outi < 2n, 0 ≤ wi, si ≤ 1000, 1 ≤ vi ≤ 106). It is guaranteed that for any i and j (i ≠ j) either ini ≠ inj, or outi ≠ outj.
Print a single number — the maximum sum in bourles that Jaroslav can get.
Input
The first line of the input contains two space-separated integers n and S (1 ≤ n ≤ 500, 0 ≤ S ≤ 1000). Then n lines follow, the i-th line contains five space-separated integers: ini, outi, wi, si and vi (0 ≤ ini < outi < 2n, 0 ≤ wi, si ≤ 1000, 1 ≤ vi ≤ 106). It is guaranteed that for any i and j (i ≠ j) either ini ≠ inj, or outi ≠ outj.
Output
Print a single number — the maximum sum in bourles that Jaroslav can get.
Samples
3 2
0 1 1 1 1
1 2 1 1 1
0 2 1 1 1
3
5 5
0 6 1 2 1
1 2 1 1 1
1 3 1 1 1
3 6 2 1 2
4 5 1 1 1
5
Note
Note to the second sample (T is the moment in time):
- T = 0: The first parcel arrives, we put in on the first platform.
- T = 1: The second and third parcels arrive, we put the third one on the current top (i.e. first) parcel on the platform, then we put the secod one on the third one. Now the first parcel holds weight w2 + w3 = 2 and the third parcel holds w2 = 1.
- T = 2: We deliver the second parcel and get v2 = 1 bourle. Now the first parcel holds weight w3 = 1, the third one holds 0.
- T = 3: The fourth parcel comes. First we give the third parcel and get v3 = 1 bourle. Now the first parcel holds weight 0. We put the fourth parcel on it — the first one holds w4 = 2.
- T = 4: The fifth parcel comes. We cannot put it on the top parcel of the platform as in that case the first parcel will carry weight w4 + w5 = 3, that exceed its strength s1 = 2, that's unacceptable. We skip the fifth parcel and get nothing for it.
- T = 5: Nothing happens.
- T = 6: We deliver the fourth, then the first parcel and get v1 + v4 = 3 bourles for them.
Note that you could have skipped the fourth parcel and got the fifth one instead, but in this case the final sum would be 4 bourles.