中国式家长更新啦！现在可以养炒鸡可爱的女儿了。鸡尾酒像当初刚玩一样，又每天没日没夜地开始养孩子了。
游戏的每回合分为两个阶段，第一个阶段是学习阶段，可以花费一定的悟性学习技能。
有一条长度为 $N$ 的学习路径，只有当你学习了路径上的第 $i$ 个技能之后，才会在下一回合解锁第 $i+1$ 个技能。（即每回合最多学习一个技能）
第i个技能所需要花费的悟性为 $max(k_i-A-B,c_i)$。其中 $A,B$ 为当前的智商值和情商值。初始状态 $A=0,B=0$。
$k_i$ 为第 $i$ 个技能的最高花费，$c_i$ 为第 $i$ 个技能的最低花费。保证对于任意的 $i(0 < i \le N)$有 $k_i>c_i$
第二阶段是安排活动阶段，可以选择一个已学的技能，并获得这个技能所能提供的智商值和情商值。如果什么技能都没有学，则跳过该阶段。
鸡尾酒想在 $Q$ 回合后学完这条路径上所有 $N$ 个技能，请你帮帮忙算一下悟性值的最小花费。
第一行输入 $N,Q$。$(N \le Q \le 15)$
接下来 $N$ 行描述学习路径上的 $N$ 个技能，每行包括 $4$ 个数字，分别为 $k_i,c_i,a_i,b_i。a_i,b_i$为该技能所能提供的智商值和情商值。
$(0 \le a_i,b_i \le 10^9, 0 \le ci < ki \le 10^9)$
输出一行一个整数代表在 $Q$ 个回合后学完路径上的所有技能所需要的最小花费。
3 5 10 0 3 3 20 5 1 2 50 10 100 100
41
Comet OJ