Migrated from Lutece 2181 攻略妹纸

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

eom在玩galgame！他对游戏中的n个二次元妹纸分别有$a_i$的好感度，而妹纸们对他的好感度分别为$b_i$。在游戏中成功攻略某个妹纸不仅需要她对你的好感度达到$c_i$，还需要你拥有至少为$d_i$的魅力值。很遗憾eom的初始魅力值和妹纸对他的好感度可能并不怎么高，所以他打算氪金来增加魅力值或者妹纸们对他的好感度。他可以氪x软妹币增加1点魅力值，或者氪y软妹币增加一个妹纸1点对他的好感度。eom现在有m软妹币和k的初始魅力值，他不知道怎么理性氪金使得他对所攻略的妹纸的好感度之和（Σ$a_j$，j∈S，S为攻略的妹纸的编号集合）最大以获得等同其数值的愉悦值，所以请聪明的你告诉他最多能获得多大的愉悦值。

Input

第一行有4个整数n，m，k，x，y，含义如题目所示。

接下来n行每行4个整数$a_i$，$b_i$，$c_i$，$d_i$，含义如题目所示。

Output

输出一个整数表示eom可能够获得的最大愉悦值。

Samples

5 11 0 2 1
3 1 3 2
5 2 4 3
9 0 5 1
2 3 4 5
2 2 4 1

12

Constraints

n,m≤5000

所有数都保证在int范围内。

Resources

2019 UESTC ACM Training for Dynamic Programming