数学考试
时间限制:C/C++/Rust/Pascal 1秒,其他语言2秒
空间限制:C/C++/Rust/Pascal 64 M,其他语言128 M
64bit IO Format: %lld

题目描述

牛妹参加了 2022 年普通高校全牛世界招生统一考试。数学试题太难,她决定复读。
为了在考试中取得更好的成绩,牛妹决定对数学进行特训。特训练习共 n 道题,第 i 题的难度为 a_i,分值为 b_i。为了更好提高自己的数学水平,牛妹决定按照题目顺序做题
做题会对牛妹的压力指数 P 产生影响。牛妹在长期磨练中养成了一颗大心脏,做完i 题后,牛妹可以选择保持自己的压力指数 P 不变、使 P 增加 Q_i 或使 P 减少 W_i。压力指数上限为 K,下限为 0。如果 P 增加 Q_i 后大于 K,牛妹就不可以选择让自己的压力指数增加 Q_i;同理,如果 P 减少 W_i 后小于 0,牛妹就不可以选择让自己的压力指数减少 W_i
牛妹相信压力可以转化为动力。当牛妹在压力为 P 的状态下完成第 i 题时,她一定可以做对这一题,并可以积累 的经验。但压力太大会反噬牛妹,当 时,牛妹不能做对第 i 题,无法积累任何经验。请注意,无论是否做对,都算作完成了第 i,在做完后,才更改压力值。
牛妹想要知道,完成本次数学特训后,她最多可以积累多少经验。牛妹初始的压力值可以由牛妹在 0 - K 范围内自由选定。
请注意,本题的空间限制较为特别,仅有 64MB。

输入描述:

输入共  行。
输入的第一行为两个正整数 n,K
接下来 n 行,每行四个正整数,第 行分别为

输出描述:

输出共一行,为牛妹可以积累经验的最大值。
示例1

输入

复制
4 10
1 100 1 1
2 100 1 1
3 100 1 1
4 100 1 1

输出

复制
100