Parcels

题意翻译

### 题目描述 有 n 件包裹，每个包裹是一个盒子，都有它自身的质量和载重 (即它上方能承受的最大质量)。scx 最近得到了一个新的包裹处理系统，这个系统以如下方式工作。初始时，有一个 (可以堆放盒子的) 平台，它的载重为 S，接下来，你能以如下的规则在平台上堆放盒子： 如果平台是空的，你可以将盒子堆放在平台上，否则，你只能在新的盒子放在最高的盒子上面。 任何时刻，(平台上) 所有盒子的总质量不能超过 S (即平台的载重)。 对任意一个盒子，任何时刻，在它上面的所有盒子的总质量不能超过这个盒子的载重。 并且你只能取走当前位于最上面的盒子 (即形成栈型结构)。 系统接收到了这 n 件包裹，已知第 i 个包裹在时刻 $in_i$ 出现，它的质量和载重分别为 $w_i,s_i$，每个包裹都有它的价值，其中第 i 个包裹的价值为 $v_i$。然而，为了获得 (赚得) 这 $v_i$ 的价值，这个系统要求它刚好在时刻 $out_i$ 被出售，否则将无法获得任何价值。于是，scx 可以选择跳过部分包裹 (即不接收这些包裹)，当然她也无法获得任何价值。 任何操作所花费的时间可以忽略不计，这意味着你可以在一个时刻做多件事情 (比如取走若干包裹，在对方若干包裹)。 注意一旦一个包裹被取走后，它就不会影响后续对包裹的操作。 由于这系统非常复杂，并且包裹数有很多，scx 想要知道如果她合理利用这个系统，她最多能得到多少钱。 ### 输入格式 第一行包含两个非负整数 $n,S(n≤500,S≤1000)$ ，表示包裹的个数和平台的载重。 接下来的 n 行，每行包含 5 个非负整数 $in_i,out_i,w_i,s_i,v_i(0≤in_i<out_i<2n;w_i,s_i≤1000;1≤v_i≤10^6)$，保证不存在两个包裹的出现时间 ($in_i$) 和出售时间 ($out_i$) 均相同。 ### 输出格式 输出一行一个整数，表示 scx 能得到的价值的最大值。

题目描述

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 $ in_{i} $ , its weight and strength are equal to $ w_{i} $ and $ s_{i} $ , respectively. Each parcel has a value of $ v_{i} $ bourles. However, to obtain this value, the system needs to give the parcel exactly at time $ out_{i} $ , 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 $ in_{i} $ 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 $ out_{i} $ , 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.

输入输出格式

输入格式

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 $ in_{i} $ , its weight and strength are equal to $ w_{i} $ and $ s_{i} $ , respectively. Each parcel has a value of $ v_{i} $ bourles. However, to obtain this value, the system needs to give the parcel exactly at time $ out_{i} $ , 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 $ in_{i} $ 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 $ out_{i} $ , 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.

输出格式

Print a single number — the maximum sum in bourles that Jaroslav can get.

输入输出样例

输入样例 #1

3 2
0 1 1 1 1
1 2 1 1 1
0 2 1 1 1

输出样例 #1

3

输入样例 #2

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

输出样例 #2

5

说明

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 $ in_{i} $ , its weight and strength are equal to $ w_{i} $ and $ s_{i} $ , respectively. Each parcel has a value of $ v_{i} $ bourles. However, to obtain this value, the system needs to give the parcel exactly at time $ out_{i} $ , 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 $ in_{i} $ 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 $ out_{i} $ , 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.