T105118 背包(knapsack)

有一个背包和$n$个物品，要把某些物品彼此压着放在背包里 。 背包最大承重为$S$。已知第$i$个物品放上去的时间 ，拿走的时间$in$ ，拿走时间$out$，重量$w$ ，承重$s$ ， 价值$v$ 。 对于同一时刻，有多个物品进出的话，顺序任意。 如果将一个物品放入背包，必须满足以下要求 ： - 在 $in$ 时间进，放在最上面。 - $out$ 时间出，出的时候他在最上面并且得到价值$v$。 - 当他在背包内时，他上方的物品的重量必须时刻小于等于$s$ 。 它也可以不放入背包 ，则得不到价值。 问你可以得到的最大价值。

第一行包括两个整数$n,S$ 接下来的$n$行，每行五个整数分别表示第$i$个物品放上去的时间$in$，拿走的时间$out$ ，重量$w$ ，承重$s$ ，价值$v$ 。

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

对于$20\%$的数据，$n \le 10$。 对于额外$20\%$的数据，保证所有$in$相同。 对于$100\%$的数据，$n \le 500,S \le 1000,0 \le in \lt out \lt 2n,w \le 1000,s \le 1000,v \le 10^6$。 保证任意两个物品$i,j$之间不会放入时间和拿走时间都相同