题目描述

澳洲猴举办了一场宴会，他想要邀请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。

题目来源

没有写明来源