Black Holes and Asteroids

There are $N$ black holes and $M$ asteroids on a number line in the current simulation universe. All $N$ black holes have the same pulling force $P$.

If black hole $i$ is at position $b_i$, and asteroid $j$ is at position $a_j$ with mass $w_j$, then black hole $i$ pulls in asteroid $j$ when $\vert b_i - a_j \vert \leq \frac{P}{w_j}$. $(1 \le i \le N;\ 1 \le j \le M)$

One black hole can pull in several asteroids. When several different black holes can pull in the same asteroid, the leftmost black hole pulls it in.

Find the minimum integer $P$ that lets the black holes pull in every asteroid in the simulation universe.

The first line contains the number of black holes $N$ and the number of asteroids $M$, separated by a space. $(1 \le N, M \le 200\,000)$

The second line contains $N$ integers $b_1, b_2, \cdots, b_N$, separated by spaces. $(-1\,000\,000 \le b_i \le 1\,000\,000)$

From the third line onward, the next $M$ lines describe the asteroids. The $j$-th of these lines contains two integers $a_j$ and $w_j$, separated by a space. $(-1\,000\,000 \le a_j \le 1\,000\,000; 1 \le w_j \le 100)$

Each position holds either a single black hole or a single asteroid.

Print the minimum integer $P$ that lets the black holes pull in every asteroid.

$|x|$ is the absolute value of $x$. If $x \ge 0$, then $|x| = x$, and if $x < 0$, then $|x| = -x$.