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.