题目描述

有 $N$ 头编号为 $1$ 到 $N$ 的骆驼。

第 $i$ 头骆驼的体重为 $w_i$。

你打算让这些骆驼排成一队，并让它们通过由 $M$ 个部分组成的桥。

你需要在骆驼过桥前决定它们的队列顺序（不要求编号递增），并且可以让骆驼之间以任意非负实数的间隔排列。骆驼们会保持这个间隔过桥。

桥的第 $i$ 个部分长度为 $l_i$，承重为 $v_i$。如果有多头骆驼同时处于某个部分的内部（不包括两端），它们体重的总和若超过 $v_i$，桥就会坍塌。

请判断是否存在一种方案，使得骆驼们可以安全过桥而不会导致桥坍塌。如果可以，请输出此时队首骆驼与队尾骆驼之间可能的最小距离。可以证明该最小值为整数，请以整数形式输出。

输入格式

输入以如下格式从标准输入读入。

$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

输出

10

样例 2

输入

2 1
12 345
1 1

输出

-1

样例 3

输入

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

输出

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

输出

3802

说明/提示

限制条件

• 所有输入均为整数。
• $2 \leq N \leq 8$
• $1 \leq M \leq 10^5$
• $1 \leq w_i, l_i, v_i \leq 10^8$

样例解释 1

• 例如，可以让骆驼按 $1,3,2$ 的顺序排列，并让骆驼之间的间隔分别为 $0,10$，这样可以让骆驼们安全过桥。
• 在第 $1$ 个部分，可能出现骆驼 $1,3$ 或者只有骆驼 $2$ 在该部分内部的情况。无论哪种情况，部分内部骆驼的体重总和都不超过该部分的承重 $4$，因此桥不会坍塌。
• 在第 $2$ 个部分，可能出现骆驼 $1,3$ 或者只有骆驼 $2$ 在该部分内部的情况。无论哪种情况，部分内部骆驼的体重总和都不超过该部分的承重 $6$，因此桥不会坍塌。
• 注意，骆驼之间的间隔可以为 $0$，且部分的内部不包括两端。

样例解释 2

• 如果无论如何都会导致桥坍塌，请输出 -1。

由 ChatGPT 4.1 翻译