블랙홀과 소행성

현재 시뮬레이션 우주에는 수직선 위에 블랙홀 $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)$

두 번째 줄에 $N$개의 정수 $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$이면 $\vert x \vert = x$이고, $x < 0$이면 $\vert x \vert = -x$다.