问题描述

有一个背包和 $n$ 个物品，要把某些物品彼此压着放在背包里 。

背包最大承重为 $S$ 。

已知第 $i$ 个物品放上去的时间 $in_i$ ，拿走的时间 $out_i$ ，重量 $w_i$ ，承重 $s_i$， 价值 $v_i$，$in_i < out_i$。

对于同一时刻，有多个物品进出的话，顺序任意。

如果将一个物品放入背包，必须满足以下要求 ：

• 在 $in$ 时间进，放在最上面。
• $out$ 时间出，出的时候他在最上面并且得到价值$v$ 。
• 当他在背包内时，他上方的物品的重量必须时刻小于等于$s_i$ 。

它也可以不放入背包 ，则得不到价值。 问你可以得到的最大价值。

输入格式

第一行包括两个整数$n，S$。

接下来的$n$ 行，每行五个整数分别表示第$i$个物品放上去的时间 $in_i$ ，拿走的时间$out_i$ ，重量$w_i$ ，承重$s_i$ ，价值 $v_i$ 。

输出格式

包括一个整数， 表示最大价值。

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

数据范围

对于$20\%$ 的数据，$n\leq 10$ 。

对于额外$20\%$ 的数据，保证所有 $in_i$ 相同。

对于 $100\%$ 的数据，$n\leq 500，S\leq 1000，0\leq in_i \leq out_i \leq 2n，w_i\leq 1000，s_i\leq 1000，v_i\leq 10^6$ 。保证任意两个物品 $i，j$ 之间不会放入时间和拿走时间都相同。

附加样例下载