#4218. 不知道高到哪里去了

内存限制:233 MiB 时间限制:20 Sec

题目描述

n+e可是不知道比我们高到哪里去了,早在五年前就已经有了一个规模庞大的后宫,而且现在这个后宫还在不断地扩容中......
现在,在n+e的后宫中,一共有n个妹子,其中,有一些妹子会喜欢(?!)另一个妹子的,这可以用一个亲密度Lxy表示(注意这个关系是单向的,而且一个妹子是可以喜欢自己的)。然而,这些关系里面有一些是不和谐的,比如亲密度过高或者过低都会造成n+e后宫的不稳定(为什么过高会造成不稳定呢?我也不知道,你问n+e去吧),由于n+e参加省队训练去了,没办法自己来稳定后宫,于是他决定更改一些妹子的亲密度(?!),具体来说,他会把某一个妹子变得主动,即所有 是她喜欢别的妹子的关系 的亲密度Lxy增加Px,以及将某一个妹子变得不太友好,即所有 是别的妹子喜欢她的关系 的亲密度Lxy减少Qy(每一个操作在同一个妹子身上只会进行一次, 两个操作在同一个妹子身上可以都进行)。最终,n+e希望他的后宫中,每一对关系都在一个和谐的范围(即[Sxy,Txy])内。不过由于n+e的妹子也是不知道高到哪里去了,所以她们并不希望自己被变得太主动或者太不友好,也就是说P,Q都不可以超过10^6,并且都是非负整数。当然n+e希望自己的后宫的妹子们越亲密越好啦,所以他想让你求出他的后宫的最大可行的亲密度总和。(PS:如果你知道怎么弄出合法方案,n+e说不定会奖励你一个妹子)
题目描述:
给定一张带权有向图,现在对每个点执行两种操作:将其所有出边权值加上一个数,再将其所有入边权值减去一个数,要求最后每条边权值都在输入的范围以内,请求出操作之后边权和最大是多少。

输入格式

第一行输入一个正整数DataT,表示n+e的后宫数。
接下来DataT组数据,每组数据的第一行输入两个正整数n,m,表示n+e的这个后宫中的妹子数量以及关系个数。接下来m行,每行五个正整数(x,y,L,S,T),表示妹子x喜欢妹子y,初始亲密度为L,修改后上下界分别为S,T;

输出格式

对于每组数据,请输出一个整数表示最后的最大亲密度和。若不存在合法方案,请输出”Unlike”(不含引号),每组数据占一行

样例

样例输入


			
2
2 4
1 1 2 5 10
1 2 4 8 10
2 1 3 5 10
2 2 2 7 10
2 4
1 1 1 7 7
1 2 7 7 7
2 1 7 7 7
2 2 7 7 7

样例输出


			
37
Unlike

数据范围与提示

对于100%的数据:0<=L,S,T<=3000

保证输入数据中不会有重边