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 翻译