Manhattan Warp Machine 2

Time Limit : 1 sec, Memory Limit : 262144 KB

Problem K: Manhattan Warp Machine 2

Problem

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

Input

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

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

Constraints

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

  • 1 ≤ N ≤ 15
  • 1 ≤ M ≤ 15
  • 1 ≤ di ≤ 3×105
  • -105xi, yi, zi ≤ 105
  • 与えられるマンハッタン距離diは全て異なる。
  • 与えられる格子点の座標は全て異なる。

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