블랙홀과 소행성

현재 시뮬레이션 우주에는 수직선 위에 블랙홀 $N$개와 소행성 $M$개가 있다. 블랙홀 $N$개의 끌어당기는 힘은 모두 $P$로 같다.

블랙홀 $i$의 위치를 $b_i$, 소행성 $j$의 위치를 $a_j$, 질량을 $w_j$라고 하자. $\vert b_i - a_j \vert \leq \frac{P}{w_j}$이면 블랙홀 $i$가 소행성 $j$를 끌어당겨 빨아들인다. $(1 \le i \le N;\ 1 \le j \le M)$

하나의 블랙홀이 여러 소행성을 빨아들이는 것도 가능하다. 서로 다른 여러 블랙홀이 하나의 소행성을 끌어들일 수 있을 때에는 위치가 가장 왼쪽에 있는 블랙홀이 소행성을 빨아들인다.

시뮬레이션 우주에 있는 모든 소행성을 블랙홀이 빨아들이기 위해 필요한 정수 $P$의 최솟값을 구하라.

첫 번째 줄에 블랙홀의 수 $N$과 소행성의 수 $M$이 공백으로 구분되어 주어진다. $(1 \le N, M \le 200\,000)$

두 번째 줄에 정수 $b_1, b_2, \cdots, b_N$이 공백으로 구분되어 주어진다. $(-1\,000\,000 \le b_i \le 1\,000\,000)$

세 번째 줄부터 $M$개의 줄에 걸쳐 소행성의 정보가 주어진다. $j$번째 줄에는 정수 $a_j$와 $w_j$가 공백으로 구분되어 주어진다. $(-1\,000\,000 \le a_j \le 1\,000\,000; 1 \le w_j \le 100)$

한 위치에는 블랙홀 하나 또는 소행성 하나만 존재할 수 있다.

모든 소행성을 블랙홀이 빨아들이기 위해 필요한 정수 $P$의 최솟값을 출력한다.

$|x|$는 $x$의 절댓값을 의미하며, $x \ge 0$이면 $|x| = x$이고, $x < 0$이면 $|x| = -x$다.