### 问题描述 小秋家里来了 $$n$$ 位客人，编号为 $$1 , 2 , 3 , … , n $$ 。现在小秋要给每一位客人倒水。 每个客人都有一个满意度，对于第 $$i$$ 个客人，满意度是这样定义的： * 如果小秋给第 $$i$$ 位客人倒了 $$a_i$$ 毫升水，客人的满意度为 $$b_i$$; * 如果小秋给第 $$i$$ 位客人倒了 $$c_i$$ $$(c_i > a_i)$$ 毫升水，客人的满意度为 $$d_i$$; * 如果小秋给第 $$i$$ 位客人倒的水不足 $$a_i$$ 毫升（可以为 $$0$$），客人的满意度为 $$e_i$$； * 如果客人满意度已经是 $$d_i$$，继续给该客人倒水不会改变客人的满意度。 现在小秋有 $$m$$ 毫升水，请问他要怎么样给客人倒水，才能让所有客人的满意度之和最大呢？你只需要求出所有客人满意度之和的最大值。 ### 输入格式 第 $$1$$ 行输入两个正整数 $$n$$ 和 $$m$$，表示客人的数量和小秋拥有水的体积。 接下来 $$n$$ 行，每行五个整数 $$a_i$$, $$b_i$$, $$c_i$$, $$d_i$$, $$e_i$$，第 $$i$$ 行表示给第 $$i$$ 位客人倒了 $$a_i$$ 毫升水满意度为 $$b_i$$，倒了 $$c_i$$ 毫升水满意度为 $$d_i$$，倒水不足 $$a_i$$ 毫升满意度为 $$e_i$$。 ### 输出格式 输出仅一行，包含一个整数，表示所有客人满意度之和的最大值。 ### 样例输入 ``` 3 10 1 1 9 100 -9 4 6 5 40 -20 2 10 5 40 -30 ``` ### 样例输出 ``` 71 ``` ### 说明/提示 对于 $$20$$% 的评测数据，$$1\leq n \leq 20, 1 \leq m \leq 100$$。 对于所有的评测数据，$$1 \leq n , m \leq 1000 $$， $$1 \leq a_i \lt c_i \leq 1000$$ ， $$1 \leq b_i,d_i\leq 10^9$$， $$-10^9 \leq e_i \leq 10^9$$。 在样例中，根据题目要求，最优的一种方案为：给第一位客人倒 $$0$$ 毫升水，满意度为 $$-9$$，给第二和第三位客人都倒 $$5$$ 毫升水，满意度为 $$80$$，满意度为 $$71$$。