201052: [AtCoder]ARC105 C - Camels and Bridge

Memory Limit：1024 MB Time Limit：2 S
Judge Style：Text Compare Creator：
Submit：0 Solved：0

Description

Score : $500$ points

Problem Statement

There are $N$ camels numbered $1$ through $N$.

The weight of Camel $i$ is $w_i$.

You will arrange the camels in a line and make them cross a bridge consisting of $M$ parts.

Before they cross the bridge, you can choose their order in the line - it does not have to be Camel $1$, $2$, $\ldots$, $N$ from front to back - and specify the distance between each adjacent pair of camels to be any non-negative real number. The camels will keep the specified distances between them while crossing the bridge.

The $i$-th part of the bridge has length $l_i$ and weight capacity $v_i$. If the sum of the weights of camels inside a part (excluding the endpoints) exceeds $v_i$, the bridge will collapse.

Determine whether it is possible to make the camels cross the bridge without it collapsing. If it is possible, find the minimum possible distance between the first and last camels in the line in such a case.

It can be proved that the answer is always an integer, so print an integer.

Constraints

  • All values in input are integers.
  • $2 \leq N \leq 8$
  • $1 \leq M \leq 10^5$
  • $1 \leq w_i,l_i,v_i \leq 10^8$

Input

Input is given from Standard Input in the following format:

$N$ $M$
$w_1$ $w_2$ $\cdots$ $w_N$
$l_1$ $v_1$
$\vdots$
$l_M$ $v_M$

Output

If the bridge will unavoidably collapse when the camels cross the bridge, print -1. Otherwise, print the minimum possible distance between the first and last camels in the line when the camels cross the bridge without it collapsing.

Sample Input 1

3 2
1 4 2
10 4
2 6

Sample Output 1

10
  • It is possible to make the camels cross the bridge without it collapsing by, for example, arranging them in the order $1$, $3$, $2$ from front to back, and setting the distances between them to be $0$, $10$.
    • For Part $1$ of the bridge, there are moments when only Camel $1$ and $3$ are inside the part and moments when only Camel $2$ is inside the part. In both cases, the sum of the weights of camels does not exceed $4$ - the weight capacity of Part $1$ - so there is no collapse.
    • For Part $2$ of the bridge, there are moments when only Camel $1$ and $3$ are inside the part and moments when only Camel $2$ is inside the part. In both cases, the sum of the weights of camels does not exceed $6$ - the weight capacity of Part $2$ - so there is no collapse.
  • Note that the distance between two camels may be $0$ and that camels on endpoints of a part are not considered to be inside the part.

Sample Input 2

2 1
12 345
1 1

Sample Output 2

-1
  • Print -1 if the bridge will unavoidably collapse.

Sample Input 3

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

Sample Output 3

700000000

Sample Input 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

Sample Output 4

3802

Input

题意翻译

给定 $n$ 只骆驼和每条骆驼的重量 $a_i$。 这些骆驼要通过一条路，这条路被分为 $m$ 个部分，每个部分的长度为 $l_i$，限重为 $v_i$。 同时经过这部分的骆驼的重量和不能超过限重，否则就会坍塌。 你可以指定这 $n$ 只骆驼的顺序和两两之间的距离，问第一只骆驼和最后一只的最短距离。如果走不了，输出 $-1$。 $n \leq 8,m \leq 10^5,l_i,r_i,v_i \leq 10^8$。 ###### $\text{\tiny{Translated by @hj23308.}}$

Source/Category

加入题单

算法标签：