#4388. JOI2012 invitation

内存限制:256 MiB 时间限制:30 Sec

题目描述

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