問題文

パ研部長のぺんぎんくんは、パ研の部室を増やしたいと思いました。

ぺんぎんくんのいる学校には N 個の部屋があり、部屋 1 から部屋 N までの番号が付けられています。

また、M 本の廊下があり、i 番目の廊下は部屋 U_i と部屋 V_i を双方向に結んでいます。これらの廊下を使って移動することで、どの部屋からどの部屋にも行くことができます。

現在、パ研の部室は部屋 1 のみです。ぺんぎんくんは今日を 1 日目として、 1 日 1 回以下の操作を行うことで、N-1 日目に全ての部屋がパ研の部室となっているようにします。

• 現時点でパ研の部室である部屋のいずれかと直接廊下で結ばれていてかつ現時点ではパ研の部室ではない部屋を 1 つ選び、新しくパ研の部室とする。

i 日目に部屋 j を新しくパ研の部室にしたとき、ぺんぎんくんの嬉しさは A_{i,j} 上昇します。はじめ、ぺんぎんくんの嬉しさは 0 です。

N-1 日目の操作が終わった時点でのぺんぎんくんの嬉しさとして考えられる値の最大値を求め、出力してください。

制約

• 2 \leq N \leq 15
• 1 \leq M \leq \frac{N(N-1)}{2}
• 1 \leq U_i < V_i \leq N
• (U_i,V_i) \neq (U_j,V_j)\ (i \neq j)
• 1 \leq A_{i,j} \leq 10^5\ (2 \leq j \leq N),\ A_{i,j} = 0\ (j = 1)
• どの部屋からどの部屋へも 0 本以上の廊下を経由して移動することができる
• 入力は全て整数

入力例 1

3 3
1 2
1 3
2 3
0 2 3
0 4 3

出力例 1

7

1 日目に部屋 2 を部室とし、2 日目に部屋 3 を部室とすると、嬉しさは A_{1,2} + A_{2,3} = 5

1 日目に部屋 3 を部室とし、2 日目に部屋 2 を部室とすると、嬉しさは A_{1,3} + A_{2,2} = 7

となるので、答えとして 7 を出力してください。

入力例 2

4 5
1 3
2 3
3 4
2 4
1 4
0 1 2 3
0 31 41 59
0 1 6 82

出力例 2

115

原案: primenumber_zz