← 返回题目列表

AtCoder · tessoku_book_br

A70. 灯笼

中文机器翻译题面 查看原题

配点: 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