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。
题目来源
没有写明来源