问题陈述

有 $N$ 只骆驼，编号从 $1$ 到 $N$。

第 $i$ 只骆驼的重量是 $w_i$。

你要将骆驼排成一行，并让它们穿过由 $M$ 部分组成的桥梁。

在它们穿过桥梁之前，你可以选择它们在队列中的顺序 - 不必是从前到后的骆驼 $1$，$2$，$\\ldots$，$N$ - 并指定每对相邻骆驼之间的距离为任意非负实数。骆驼在穿过桥梁时保持指定的距离。

桥梁的第 $i$ 部分的长度为 $l_i$，重量容量为 $v_i$。如果部分内骆驼的重量之和（不包括端点）超过 $v_i$，则桥梁会坍塌。

确定是否可能让骆驼穿过桥梁而不坍塌。如果可能，请找出队列中首尾骆驼之间的最小可能距离。

可以证明答案始终是一个整数，因此输出一个整数。

约束条件

• 输入中的所有值都是整数。
• $2 \\leq N \\leq 8$
• $1 \\leq M \\leq 10^5$
• $1 \\leq w_i, l_i, v_i \\leq 10^8$

输入

输入以以下格式从标准输入给出：

$N$ $M$ $w_1$ $w_2$ $\\cdots$ $w_N$ $l_1$ $v_1$ $\\vdots$ $l_M$ $v_M$

输出

如果骆驼穿过桥梁时桥梁将不可避免地坍塌，则输出 -1。否则，当骆驼穿过桥梁而不坍塌时，请输出队列中首尾骆驼之间的最小可能距离。

示例输入1

3 2
1 4 2
10 4
2 6

示例输出1

10

• 可以通过将它们从前到后排列为 $1$、$3$ 和 $2$，并设置它们之间的距离为 $0$、$10$，使得骆驼可以穿过桥梁而不会坍塌。
  • 对于桥梁的第 $1$ 部分，在某些时刻只有骆驼 $1$ 和 $3$ 在其中，而在某些时刻只有骆驼 $2$ 在其中。在这两种情况下，骆驼的重量之和不超过第 $1$ 部分的重量容量 $4$，因此不会坍塌。
  • 对于桥梁的第 $2$ 部分，在某些时刻只有骆驼 $1$ 和 $3$ 在其中，而在某些时刻只有骆驼 $2$ 在其中。在这两种情况下，骆驼的重量之和不超过第 $2$ 部分的重量容量 $6$，因此不会坍塌。
• 请注意，两只骆驼之间的距离可能为 $0$，并且端点上的骆驼不被视为在部分内。

示例输入2

2 1
12 345
1 1

示例输出2

-1

• 如果骆驼穿过桥梁时桥梁将不可避免地坍塌，则输出 -1。

示例输入3

8 1
1 1 1 1 1 1 1 1
100000000 1

示例输出3

700000000

示例输入4

8 20
57 806 244 349 608 849 513 857
778 993
939 864
152 984
308 975
46 860
123 956
21 950
850 876
441 899
249 949
387 918
34 965
536 900
875 889
264 886
583 919
88 954
845 869
208 963
511 975

示例输出4

3802