分数: 500 点
问题陈述
有 N 骆驼编号 1 通过 N.
骆驼的重量 i is 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 位于只有 Camel 的部分和时刻 2 位于零件内部。在这两种情况下,骆驼的重量总和不超过 4 - 零件的重量容量 1 - 所以没有崩溃。
- 对于零件 2 桥上,有的时候只有骆驼 1 和 3 位于只有 Camel 的部分和时刻 2 位于零件内部。在这两种情况下,骆驼的重量总和不超过 6 - 零件的重量容量 2 - 所以没有崩溃。
- 请注意,两只骆驼之间的距离可能是 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