配点: 1000 点
問題文
N 灯放在桌子上。i 灯的第一个状态是一个整数 A_i 当A_i = 0 时关闭,A_i = 1 时为 ON。
太郎反对电灯。
可以执行 M 类型的操作。i 第二种操作是灯
它同时反转 X_i,Y_i,Z_i 的状态。这里,“反转”是指将熄灭的灯变为点亮,将点亮的灯变为熄灭。
求打开所有灯所需的最少操作次数。然而,多次执行相同类型的操作是可以接受的。
制約
- 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)
- 所有输入均为整数
入力
输入如下格式从标准输入给出。
N M A_1 A_2 \ldots A_N X_1 Y_1 Z_1 \vdots X_M Y_M Z_M
出力
请打印答案。但是,如果无论执行多少次操作都无法打开所有灯,请改为 请输出 -1 。
入力例 1
4 2 0 1 1 0 1 2 3 2 3 4
出力例 1
2