AT_arc105_c [ARC105C] Camels and Bridge

有 $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`。否则，请输出在桥不坍塌的情况下，队首与队尾骆驼之间可能的最小距离。

## 限制条件 - 所有输入均为整数。 - $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 翻译