Harmonious Army

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$.

There are multiple test cases.

Each case starts with a line containing two positive integers $n(n \leq 500)$ and $m(m \leq 10^4)$.

In the following $m$ lines, each line contains five positive integers $u, \; v, \; a, \; b, \; c$ $(1 \leq u, v \leq n, u \neq v, 1 \leq a, c \leq 4 \times 10 ^6, b = a / 4 + c / 3)$, denoting soldiers $u$ and $v$ have 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 \times 10^3$, and the sum of $m$ in all test cases is no larger than $5 \times 10^4$.

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

2019 Multi-University Training Contest 2