← 返回题目列表

AtCoder · arc105_c

C. 骆驼和桥梁

中文机器翻译题面 查看原题

分数: 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