题目描述

有一个最大承重为 $S$ 的背包，以及 $n$ 件物品。背包最初为空，放入其中的物品从下到上堆叠。

第 $i$ 件物品有五个属性：放入时刻 $in_i$、取出时刻 $out_i$、重量 $w_i$、承重 $s_i$ 和价值 $v_i$，其中 $in_i<out_i$。

你可以选择不使用某件物品，此时得不到它的价值。对于选择使用的物品，必须在 $in_i$ 时刻把它放在当前所有物品的最上方，并在 $out_i$ 时刻将它取出；取出时，它必须位于最上方，随后获得价值 $v_i$。

在任何时刻，背包中所有物品的总重量都不能超过 $S$。对于背包中的每件物品 $i$，位于它上方的所有物品的重量之和都不能超过 $s_i$；这里不包含物品 $i$ 自身的重量。

同一时刻可以进行多次放入或取出操作，操作顺序由你决定。一个物品取出后立即离开背包，不再影响该时刻后续操作的承重。

求能够获得的最大价值之和。

输入格式

第一行包含两个整数 $n,S$。

接下来 $n$ 行，每行包含五个整数 $in_i,out_i,w_i,s_i,v_i$，依次描述一件物品。

输出格式

输出一个整数，表示能够获得的最大价值之和。

数据范围

对于所有数据，$n\le 500$，$S\le 1000$，$0\le in_i<out_i\le 2n$，$w_i,s_i\le 1000$，$v_i\le 10^6$。

任意两件不同物品的放入时刻和取出时刻不会同时相同。

子任务

编号	分值	缩减范围	附加限制
1	20	$n \le 10$	—
2		—	所有物品的 $in_i$ 相同
3	60		—

样例 1

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

样例 1 说明

选择第 $1,2,3,4$ 件物品。

在时刻 $0$ 放入物品 $1$；时刻 $1$ 先放入物品 $3$，再放入物品 $2$。此时物品 $1$ 上方的总重量为 $2$，恰好达到其承重。

时刻 $2$ 取出物品 $2$；时刻 $3$ 先取出物品 $3$，再放入物品 $4$；时刻 $6$ 先取出物品 $4$，再取出物品 $1$。总价值为 $1+1+1+2=5$。

该方案不选择物品 $5$：在时刻 $4$ 再放入它，会使物品 $1$ 上方的总重量变为 $3$，超过其承重 $2$。