JOI2012 invitation

时间限制:30s      空间限制:256MB

题目描述

澳洲猴举办了一场宴会,他想要邀请A个男生和B个女生参加,这A个男生从1到A编号,女生也从1到B编号。
现在澳洲猴知道n组朋友关系,这n组朋友关系是这样描述的:男生中编号为Pi到Qi的和女生中编号为Si到Ei的是好朋友,这也就是说(Qi-Pi+1)个男生之间互相是好朋♂友,(Si-Ei+1)个女生之间互相是好朋♂友,(Qi-Pi+1)个男生和(Si-Ei+1)个女生之间互相也是好朋友,总之他们互相是好友关系,并且互相的友好指数为Ti。
现在,澳洲猴只认识一个非常要好的男生C,接着他要进行一系列邀请,使得所有的人都参加这次宴会,邀请的过程是这样的:
选出现有集合中的一个人u(初始时只有C),然后利用这个人u的某个朋友关系i,邀请另一个不在现有集合中的人v进入现有集合,整个集合的幸福值增加Ti。重复直到所有人都进入现有集合,如果不存在将所有人全部邀请的方案,输出-1。


输入格式

输入的第一行为A,B,C三个正整数。
接下来是n。
然后n行,每行5个正整数,Pi,Qi,Si,Ei,Ti,描述一组朋♂友关系。


输出格式

输出一行,最大的幸福指数。如果不存在全部邀请的方案,输出-1。


样例输入

5 6 3 
4 
2 4 1 3 20 
1 2 2 4 40 
4 5 2 3 30 
4 4 4 6 10

样例输出

280

提示

样例1解释:
男3->男2 +20;
男2->男1 +40;
男2->女1 +20;
男2->女2 +40;
男2->女3 +40;
女2->女4 +40;
女3->男4 +30;
女3->男5 +30;
男4->女5 +10;
男4->女6 +10;
对于100%的数据 n<=100000,1<=A,B,Ti<=1e9,Pi<=Qi<=A,Si<=Ei<=B,C<=A。


题目来源

没有写明来源