暗度陈仓

时间限制:10s      空间限制:512MB

题目描述

话说攘外必先安内,在KD正确的指导方针和响应群众号召的伟大带领下,基地内部的各种重大问题算是都被料理完
毕了,剩下的就只需要彻底清扫S的残留部队即可。但是如何有效的完成这项艰巨的使命,却是非常值得深思的事
情,大家都苦无良策。而正在此时,KD忽然想起了某动画中的MM,同时一个巧妙的战术也就诞生了= =。就是表面
上装作要正面进攻,却偷偷将全部兵力投入到偷袭行动中,趁定时炸弹爆炸造成敌方伤亡混乱之际,趁虚而入将敌
人一举歼灭。哇哈哈哈,能想出这么牛B的战术真是前无来者后无古人啊,这一役的成功注定会让KD名留青史永垂
不朽,想着想着KD的口水就不禁流了出来。(上一句请忽略。)果然,虚幻的假象迷惑了敌人的双眼,KD伟大的人
格魅力让敌人甚至派遣出了他们的最终武器SUG(S**t unscientific gun)来对基地进行正面攻打。不过站在KD独
具特色的慧眼和超乎想象的理性思维的角度来看,SUG从本质上来说就是普通的大炮而已。虽然这是很有意义的,
但是现在还是不是自我表扬的时刻了,由于兵力都已经调走,基地被狂轰滥炸也是在所难免,但是为了革命的伟大
胜利,这一点点小的牺牲根本不足挂齿。可是KD毕竟在基地中藏片万G,想忍痛割爱还是有些力不从心,所以KD决
定利用基地中残余的武器OSJP(Original super junk plane)尽量摧毁敌人的SUG从而减少基地将会遭到的损伤。
在KD超越人类的思维中,战场可以抽象成二维坐标系,由于敌人的SUG都是炮口朝向基地的,所以可以抽象成平行
于Y轴的线段。KD可以为每架OSJP指定一些轰炸段,而每架OSJP轰炸完它被指定的所有目标段后就报废了,一个轰
炸段只能是一个平行于Y轴的单位线段。正因为是OSJP,所以每架OSJP被指定的轰炸段中任意两段在Y轴上的投影都
不允许重叠,否则这架OSJP就直接报废了。那么,剩下的问题便是到底该如何指定轰炸段才能炸掉敌人总威力尽量
大的SUG,KD一时纠结了,所以它决定将这个乏力的任务交给因为怕死所以留在基地没参加偷袭行动的你。为了拯
救世界,请务必计算出这个答案。


输入格式

第一行两个正整数N、M,表示敌人SUG的数量和KD拥有的OSJP的数量。
接下来N行每行四个整数X、Y1、Y2、P,表示有一个SUG位置为横坐标X,纵坐标Y1到Y2这一段,威力为P。
当然,根据光电效应这些SUG是不会有任何互相重叠的长度的。
N<=1000;M<=100;1<=Y1<Y2<=5001;1<=P<=100000;1<=X<=5001。
注意事项:
当且仅当一个SUG所覆盖的所有单位线段都被轰炸了,才算被炸掉并把它的威力累加入总摧毁威力值。


输出格式

输出一个整数ANS,表示计算出的最大值。如果无法计算出结果,请输出“Unworkable”,KD会用该测试点0分来惩罚你的失败。


样例输入

5 2
1 1 3 2
1 4 6 2
2 3 5 2
3 2 4 2
4 3 4 1

样例输出

8

提示

注意:数据不保证Y1<Y2


题目来源

没有写明来源

Menuappsclose