問題文

N 個のランプが机の上に置かれています。i 個目のランプの最初の状態は整数 A_i で表され、A_i = 0 のとき OFF、A_i = 1 のとき ON です。
太郎君は、電灯に対して M 種類の操作を行うことができます。i 種類目の操作は、ランプ X_i,Y_i,Z_i の状態を同時に反転させるものです。ここで 反転 とは、OFF であるランプを ON にし、ON であるランプを OFF にすることを指します。
最小何回の操作で、すべてのランプの状態を ON にすることができるかを求めてください。ただし、同じ種類の操作を複数回行っても良いものとします。

制約

• 3 \leq N \leq 10
• 0 \leq M \leq 100
• A_i \in \{ 0,1 \}
• 1 \leq X_i \lt Y_i \lt Z_i \leq N
• i \neq j ならば (X_i,Y_i,Z_i) \neq (X_j,Y_j,Z_j)
• 入力はすべて整数

入力例 1

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

出力例 1

2