3858: Harmonious Army
内存限制：128 MB
时间限制：1.000 S
评测方式：文本比较
命题人：
提交：1
解决：1
题目描述
Now, Bob is playing an interesting game in which he is a general of a harmonious army. There are n soldiers in this army. Each soldier should be in one of the two occupations, Mage or Warrior. There are m pairs of soldiers having combination ability. There are three kinds of combination ability. If the two soldiers in a pair are both Warriors, the army power would be increased by a. If the two soldiers in a pair are both Mages, the army power would be increased by c. Otherwise the army power would be increased by b, and b=a/4+c/3, guaranteed that 4|a and 3|c. Your task is to output the maximum power Bob can increase by arranging the soldiers' occupations.
Note that the symbol a|b means that a divides b, e.g. , 3|12 and 8|24.
Note that the symbol a|b means that a divides b, e.g. , 3|12 and 8|24.
输入
There are multiple test cases.
Each case starts with a line containing two positive integers n(n≤500) and m(m≤1e4).
In the following m lines, each line contains five positive integers u,v,a,b,c (1≤u,v≤n,u≠v,1≤a,c≤4×106,b=a/4+c/3), denoting soldiers u and vhave combination ability, guaranteed that the pair (u,v) would not appear more than once.
It is guaranteed that the sum of n in all test cases is no larger than 5×103, and the sum of m in all test cases is no larger than 5×1e4.
Each case starts with a line containing two positive integers n(n≤500) and m(m≤1e4).
In the following m lines, each line contains five positive integers u,v,a,b,c (1≤u,v≤n,u≠v,1≤a,c≤4×106,b=a/4+c/3), denoting soldiers u and vhave combination ability, guaranteed that the pair (u,v) would not appear more than once.
It is guaranteed that the sum of n in all test cases is no larger than 5×103, and the sum of m in all test cases is no larger than 5×1e4.
输出
For each test case, output one line containing the maximum power Bob can increase by arranging the soldiers' occupations.
样例输入 复制
3 2
1 2 8 3 3
2 3 4 3 6样例输出 复制
12