Jaroslav 拥有一家小型快递服务公司。他最近获得并推出了一种新的包裹处理系统。每个包裹都是一个盒子,盒子有它的重量和强度。该系统的工作原理如下。它最初有一个空平台,您可以按照以下规则放置盒子:
- 如果平台是空的,则将盒子直接放在平台上,否则将其放在平台最上面的盒子上。
- 平台上所有箱子的总重量在任何时候都不能超过平台S的强度。
- 平台上任何箱子的强度在任何时候都必须不小于上方箱子的总重量。
你只能从平台上拿走最上面的盒子。
系统收到n个包裹,第i个包裹恰好在时间ini到达,其重量和强度分别等于wi和si。每个地块的价值为 vi 布尔斯。然而,为了获得这个值,系统需要在outi时间准确地给出包裹,否则Jaroslav将得到0 bourles。因此,Jaroslav 可以跳过任何包裹而不将其放在平台上,在 ini 时间正式交付它,但不会得到任何东西。
问题中的任何操作都会立即执行。这意味着可以同时以任意顺序进行多项接收和递送包裹的操作。
请注意,在outi时间投递的包裹会立即进入系统之外,并且同时发生的以下活动不会被考虑在内。
由于系统非常复杂,并且收到的包裹很多,Jaroslav 要求您说出使用他的系统他最多可以获得多少金额。
输入
输入的第一行包含两个空格分隔的整数 n 和 S (1 ≤ n ≤ 500, 0 ≤ S ≤ 1000)。接下来是 n 行,第 i 行包含五个空格分隔的整数:ini、outi、wi、si 和 vi(0 ≤ ini < outi < 2n、0 ≤ wi、si ≤ 1000、1 ≤ vi ≤ 106)。保证对于任何 i 和 j (i ≠ j),要么 ini ≠ inj,要么 outi ≠ outj。
输出
打印一个数字 — Jaroslav 可以获得的最大布尔值。
示例
输入 #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
注意
第二个样本的注释(T 是时间点):
- T = 0:第一个包裹到达,我们放在第一个平台。
- T = 1:第二个和第三个包裹到达,我们将第三个包裹放在平台上当前顶部(即第一个)包裹上,然后将第二个包裹放在第三个包裹上。现在第一个地块的重量为 w2 + w3 = 2,第三个地块的重量为 w2 = 1。
- T = 2:我们交付第二个包裹并获得 v2 = 1 bourle。现在第一个包裹的重量为 w3 = 1,第三个包裹的重量为 0。
- T = 3:第四个包裹来了。首先我们给出第三个地块并得到 v3 = 1 bourle。现在第一个地块的重量为 0。我们将第四个地块放在上面——第一个地块的重量为 w4 = 2。
- T = 4:第五个包裹来了。我们不能把它放在平台的顶部地块上,因为这样第一个地块的重量将是w4 + w5 = 3,超过其强度s1 = 2,这是不可接受的。我们跳过第五个包裹,却一无所获。
- T = 5:什么也没发生。
- T = 6:我们交付第四个包裹,然后是第一个包裹,并为他们获得 v1 + v4 = 3 布尔。
请注意,您可以跳过第四个包裹而获得第五个包裹,但在这种情况下,最终总和将为 4 布尔。