Problem K: Manhattan Warp Machine 2

Problem

とある宇宙では、3次元の格子点上に星が存在し、宇宙人達はマンハッタンワープ装置という装置を使い、星間を移動している。
このワープ装置には、N個のボタンが付いており、ボタンiを押すと、現在いる星からのマンハッタン距離がd_iである任意の星にワープすることができる。
ワープ装置は改良され、コストがかからずに移動出来る。
今、(0, 0, 0)の星にいるある宇宙人があるM個の星を訪れたいと考えている。
M個の星を全て訪れるのに最短で何回ワープをする必要があるか答えよ。
もし、1つでも訪れることが不可能な星がある場合は-1を出力せよ。
M個の星は好きな順番に訪れることが出来、全て訪れた後に(0, 0, 0)に戻って来る必要は無い。
3次元上の全ての格子点には必ず星が存在する。
点(x₁, y₁, z₁)と点(x₂, y₂, z₂)間のマンハッタン距離は| x₁ - x₂ | + | y₁ - y₂ | + | z₁ - z₂ |で表される。

Input

N M
d1 ... dN
x1 y1 z1
...
xM yM zM

入力は全て整数で与えられる。
1行目にN, Mが与えられる。
2行目に移動可能なマンハッタン距離d_iが空白区切りで与えられる。
3行目以降のM行に、M個の訪れたい星の格子点の座標(x_i, y_i, z_i)が1行ずつ空白区切りで与えられる。

Constraints

入力は以下の条件を満たす。

• 1 ≤ N ≤ 15
• 1 ≤ M ≤ 15
• 1 ≤ d_i ≤ 3×10⁵
• -10⁵ ≤ x_i, y_i, z_i ≤ 10⁵
• 与えられるマンハッタン距離d_iは全て異なる。
• 与えられる格子点の座標は全て異なる。

Output

M個の星全てを訪れるのにかかる最短ワープ回数を1行に出力せよ。 訪れることが不可能な星がある場合は-1を出力せよ。

Sample Input 1

2 1
1 2
5 0 0

Sample Output 1

3

Sample Input 2

2 2
9 3
3 0 0
3 9 0

Sample Output 2

2

Sample Input 3

1 1
4
3 0 0

Sample Output 3

-1