Now, Bob is playing an interesting game in which he is a general of a harmonious army. There are nnsoldiers in this army. Each soldier should be in one of the two occupations, Mage or Warrior. There are mm 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 aa. If the two soldiers in a pair are both Mages, the army power would be increased by cc. Otherwise the army power would be increased by bb, and b=a/4+c/3b=a/4+c/3, guaranteed that 4|a4|a and 3|c3|c. Your task is to output the maximum power Bob can increase by arranging the soldiers' occupations.
Note that the symbol a|ba|b means that aa divides bb, e.g. , 3|123|12 and 8|248|24.
Input
There are multiple test cases.
Each case starts with a line containing two positive integers n(n≤500)n(n≤500) and m(m≤104)m(m≤104).
In the following mm lines, each line contains five positive integers u,v,a,b,cu,v,a,b,c(1≤u,v≤n,u≠v,1≤a,c≤4×106,b=a/4+c/3)(1≤u,v≤n,u≠v,1≤a,c≤4×106,b=a/4+c/3), denoting soldiers uu and vv have combination ability, guaranteed that the pair (u,v)(u,v) would not appear more than once.
It is guaranteed that the sum of nn in all test cases is no larger than 5×1035×103, and the sum of mm in all test cases is no larger than 5×1045×104.
Output
For each test case, output one line containing the maximum power Bob can increase by arranging the soldiers' occupations.