(追記) (追記ここまで)

29755번 - 블랙홀과 소행성 다국어

시간 제한	메모리 제한	제출	정답	맞힌 사람	정답 비율
1 초	1024 MB	826	271	231	35.484%

문제

현재 시뮬레이션 우주에는 수직선 위에 블랙홀 $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$의 최솟값을 출력한다.

제한

예제 입력 1

예제 출력 1

노트

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

W3sicHJvYmxlbV9pZCI6IjI5NzU1IiwicHJvYmxlbV9sYW5nIjoiMCIsInRpdGxlIjoiXHViZTE0XHViNzk5XHVkNjQwXHVhY2ZjIFx1YzE4Y1x1ZDU4OVx1YzEzMSIsImRlc2NyaXB0aW9uIjoiPHA+XHVkNjA0XHVjN2FjIFx1YzJkY1x1YmJhY1x1YjgwOFx1Yzc3NFx1YzE1OCBcdWM2YjBcdWM4ZmNcdWM1ZDBcdWIyOTQgXHVjMjE4XHVjOWMxXHVjMTIwIFx1YzcwNFx1YzVkMCBcdWJlMTRcdWI3OTlcdWQ2NDAgJE4kXHVhYzFjXHVjNjQwIFx1YzE4Y1x1ZDU4OVx1YzEzMSAkTSRcdWFjMWNcdWFjMDAgXHVjODc0XHVjN2FjXHVkNTVjXHViMmU0LiBcdWJlMTRcdWI3OTlcdWQ2NDAgJE4kXHVhYzFjXHVjNzU4IFx1YjA0Y1x1YzViNFx1YjJmOVx1YWUzMFx1YjI5NCBcdWQ3OThcdWM3NDAgJFAkXHViODVjIFx1YWMxOVx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHViZTE0XHViNzk5XHVkNjQwICRpJFx1Yzc1OCBcdWM3MDRcdWNlNThcdWFjMDAgJGJfaSRcdWFjZTAsIFx1YzE4Y1x1ZDU4OVx1YzEzMSAkaiRcdWM3NTggXHVjNzA0XHVjZTU4XHViOTdjICRhX2okLCBcdWM5YzhcdWI3YzlcdWM3NDQgJHdfaiRcdWI3N2NcdWFjZTAgXHVkNTg4XHVjNzQ0IFx1YjU0YywgXHVjNzc0IFx1YzJkY1x1YmJhY1x1YjgwOFx1Yzc3NFx1YzE1OCBcdWM2YjBcdWM4ZmNcdWM1ZDBcdWMxMWNcdWIyOTQgJFxcdmVydCBiX2kgLSBhX2ogXFx2ZXJ0IFxcbGVxIFxcZnJhY3tQfXt3X2p9JCBcdWM3NzggXHVhY2JkXHVjNmIwLCBcdWJlMTRcdWI3OTlcdWQ2NDAgJGkkXHVhYzAwIFx1YzE4Y1x1ZDU4OVx1YzEzMSAkaiRcdWI5N2MgXHViMDRjXHVjNWI0XHVjNjQwIFx1YmU2OFx1YzU0NFx1YjRlNFx1Yzc3OFx1YjJlNC4gJCgxIFxcbGUgaSBcXGxlIE47JCAkMSBcXGxlIGogXFxsZSBNKSQ8XC9wPlxyXG5cclxuPHA+XHVkNTU4XHViMDk4XHVjNzU4IFx1YmUxNFx1Yjc5OVx1ZDY0MFx1Yzc3NCBcdWM1ZWNcdWI3ZWMgXHVjMThjXHVkNTg5XHVjMTMxXHVjNzQ0IFx1YmU2OFx1YzU0NFx1YjRlNFx1Yzc3NFx1YjI5NCBcdWFjODNcdWIzYzQgXHVhYzAwXHViMmE1XHVkNTU4XHViYTcwLCBcdWMxMWNcdWI4NWMgXHViMmU0XHViOTc4IFx1YzVlY1x1YjdlYyBcdWJlMTRcdWI3OTlcdWQ2NDBcdWM3NzQgXHVkNTU4XHViMDk4XHVjNzU4IFx1YzE4Y1x1ZDU4OVx1YzEzMVx1Yzc0NCBcdWIwNGNcdWM1YjRcdWI0ZTRcdWM3N2MgXHVjMjE4IFx1Yzc4OFx1Yzc0NCBcdWI1NTAgXHVjNzA0XHVjZTU4XHVhYzAwIFx1YWMwMFx1YzdhNSBcdWM2N2NcdWNhYmRcdWM1ZDAgXHVjNzg4XHViMjk0IFx1YmUxNFx1Yjc5OVx1ZDY0MFx1Yzc3NCBcdWMxOGNcdWQ1ODlcdWMxMzFcdWM3NDQgXHViZTY4XHVjNTQ0XHViNGU0XHVjNzc4XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWMyZGNcdWJiYWNcdWI4MDhcdWM3NzRcdWMxNTggXHVjNmIwXHVjOGZjXHVjNWQwIFx1Yzc4OFx1YjI5NCBcdWJhYThcdWI0ZTAgXHVjMThjXHVkNTg5XHVjMTMxXHVjNzQ0IFx1YmUxNFx1Yjc5OVx1ZDY0MFx1Yzc3NCBcdWJlNjhcdWM1NDRcdWI0ZTRcdWM3NzRcdWFlMzAgXHVjNzA0XHVkNTc0IFx1ZDU0NFx1YzY5NFx1ZDU1YyBcdWM4MTVcdWMyMTggJFAkXHVjNzU4IFx1Y2Q1Y1x1YzE5Zlx1YWMxMlx1Yzc0NCBcdWFkNmNcdWQ1NThcdWIyOTQgXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzQ0IFx1Yzc5MVx1YzEzMVx1ZDU1OFx1YzJkY1x1YzYyNC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Y2NhYiBcdWJjODhcdWM5ZjggXHVjOTA0XHVjNWQwIFx1YmUxNFx1Yjc5OVx1ZDY0MFx1Yzc1OCBcdWMyMTggJE4kXHVhY2ZjIFx1YzE4Y1x1ZDU4OVx1YzEzMVx1Yzc1OCBcdWMyMTggJE0kXHVjNzc0IFx1YWNmNVx1YmMzMVx1YzczY1x1Yjg1YyBcdWFkNmNcdWJkODRcdWI0MThcdWM1YjQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiAkKDEgXFxsZSBOLCBNIFxcbGUgMjAwXFwsMDAwKSQ8XC9wPlxyXG5cclxuPHA+XHViNDUwIFx1YmM4OFx1YzlmOCBcdWM5MDRcdWM1ZDAgJE4kXHVhYzFjXHVjNzU4IFx1YzgxNVx1YzIxOCAkYl8xJCwgJGJfMiQsICRcXGNkb3RzJCwgJGJfTiRcdWM3NzQgXHVhY2Y1XHViYzMxXHVjNzNjXHViODVjIFx1YWQ2Y1x1YmQ4NFx1YjQxOFx1YzViNCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuICQoLTFcXCwwMDBcXCwwMDAgXFxsZSBiX2kgXFxsZSAxXFwsMDAwXFwsMDAwKSQ8XC9wPlxyXG5cclxuPHA+XHVjMTM4IFx1YmM4OFx1YzlmOCBcdWM5MDRcdWJkODBcdWQxMzAgJE0kXHVhYzFjXHVjNzU4IFx1YzkwNFx1YzVkMCBcdWFjNzhcdWNjZDAgXHVjMThjXHVkNTg5XHVjMTMxXHVjNzU4IFx1YzgxNVx1YmNmNFx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1YWRmOFx1YzkxMSAkaiRcdWJjODhcdWM5ZjggXHVjOTA0XHVjNWQwXHViMjk0IFx1YzgxNVx1YzIxOCAkYV9qJCwgJHdfaiRcdWFjMDAgXHVhY2Y1XHViYzMxXHVjNzNjXHViODVjIFx1YWQ2Y1x1YmQ4NFx1YjQxOFx1YzViNCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuICQoLTFcXCwwMDBcXCwwMDAgXFxsZSBhX2ogXFxsZSAxXFwsMDAwXFwsMDAwOyQgJDEgXFxsZSB3X2ogXFxsZSAxMDApJDxcL3A+XHJcblxyXG48cD5cdWQ1NWMgXHVjNzA0XHVjZTU4XHVjNWQwXHViMjk0IFx1YmUxNFx1Yjc5OVx1ZDY0MFx1YjljYyBcdWQ1NThcdWIwOTggXHVjODc0XHVjN2FjXHVkNTU4XHVhYzcwXHViMDk4IFx1YzE4Y1x1ZDU4OVx1YzEzMVx1YjljYyBcdWQ1NThcdWIwOTggXHVjODc0XHVjN2FjXHVkNTYwIFx1YzIxOCBcdWM3ODhcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHViYWE4XHViNGUwIFx1YzE4Y1x1ZDU4OVx1YzEzMVx1Yzc0NCBcdWJlMTRcdWI3OTlcdWQ2NDBcdWM3NzQgXHViZTY4XHVjNTQ0XHViNGU0XHVjNzc0XHVhZTMwIFx1YzcwNFx1ZDU3NCBcdWQ1NDRcdWM2OTRcdWQ1NWMgXHVjODE1XHVjMjE4ICRQJFx1Yzc1OCBcdWNkNWNcdWMxOWZcdWFjMTJcdWM3NDQgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiI8cD4kfHh8JFx1YjI5NCAkeCRcdWM3NTggXHVjODA4XHViMzEzXHVhYzEyXHVjNzQ0IFx1Yzc1OFx1YmJmOFx1ZDU1OFx1YmE3MCwgJHggXFxnZSAwJFx1Yzc3NFx1YmE3NCAkXFx2ZXJ0IHggXFx2ZXJ0ID0geCRcdWM3NzRcdWFjZTAsICR4ICZsdDsgMCRcdWM3NzRcdWJhNzQgJFxcdmVydCB4IFxcdmVydCA9IC14JFx1YjJlNC48XC9wPlxyXG4iLCJvcmlnaW5hbCI6IjEiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ190Y29kZSI6IktvcmVhbiJ9LHsicHJvYmxlbV9pZCI6IjI5NzU1IiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiQmxhY2sgSG9sZXMgYW5kIEFzdGVyb2lkcyIsImRlc2NyaXB0aW9uIjoiPHA+SW4gdGhlIGN1cnJlbnQgc2ltdWxhdGVkIHVuaXZlcnNlLCAkTiQgYmxhY2sgaG9sZXMgYW5kICRNJCBhc3Rlcm9pZHMgYXJlIGxvY2F0ZWQgb24gYSB2ZXJ0aWNhbCBsaW5lLiBUaGUgZ3Jhdml0YXRpb25hbCBmb3JjZSBleGVydGVkIGJ5IGFsbCAkTiQgYmxhY2sgaG9sZXMgaXMgdGhlIHNhbWUgYW5kIGlzIGRlbm90ZWQgYXMgJFAkLjxcL3A+XHJcblxyXG48cD5HaXZlbiB0aGF0IHRoZSBwb3NpdGlvbiBvZiB0aGUmbmJzcDskaSQtdGggYmxhY2sgaG9sZSBpcyAkYl9pJFx1MjAwYiBhbmQgdGhlIHBvc2l0aW9uIG9mIHRoZSAkaiQtdGggYXN0ZXJvaWQmbmJzcDtpcyAkYV9qJCZuYnNwO3dpdGggYSBtYXNzICR3X2okLCBpbiB0aGlzIHNpbXVsYXRlZCB1bml2ZXJzZSwgaWYgJFxcdmVydCBiX2kgLSBhX2ogXFx2ZXJ0Jm5ic3A7XFxsZXEgXFxmcmFje1B9e3dfan0kLCZuYnNwO3RoZSAkaSQtdGggYmxhY2sgaG9sZSB3aWxsIHB1bGwgYW5kIGFic29yYiB0aGUgJGokLXRoIGFzdGVyb2lkLiZuYnNwOyQoMSBcXGxlIGkgXFxsZSBOOyQgJDEgXFxsZSBqJm5ic3A7XFxsZSBNKSQ8XC9wPlxyXG5cclxuPHA+QSBzaW5nbGUgYmxhY2sgaG9sZSBjYW4gYWJzb3JiIG11bHRpcGxlIGFzdGVyb2lkcywgYW5kIGluIGNhc2VzIHdoZXJlIG11bHRpcGxlIGJsYWNrIGhvbGVzIGNhbiBwdWxsIGEgc2luZ2xlIGFzdGVyb2lkLCB0aGUgYmxhY2sgaG9sZSBwb3NpdGlvbmVkIGZ1cnRoZXN0IHRvIHRoZSBsZWZ0IHdpbGwgYWJzb3JiIHRoZSBhc3Rlcm9pZC48XC9wPlxyXG5cclxuPHA+V3JpdGUgYSBwcm9ncmFtIHRvIGZpbmQgdGhlIHNtYWxsZXN0IGludGVnZXIgJFAkIHJlcXVpcmVkIGZvciBhbGwgYmxhY2sgaG9sZXMgaW4gYSBzaW11bGF0ZWQgdW5pdmVyc2UgdG8gYWJzb3JiIGluIGFsbCB0aGUgYXN0ZXJvaWRzLjxcL3A+XHJcbiIsImlucHV0IjoiPHA+VGhlIGZpcnN0IGxpbmUgY29udGFpbnMgdHdvIGludGVnZXJzICROJCBhbmQgJE0kLCBzZXBhcmF0ZWQgYnkgYSBzcGFjZSwgcmVwcmVzZW50aW5nIHRoZSBudW1iZXIgb2YgYmxhY2sgaG9sZXMgYW5kIGFzdGVyb2lkcywgcmVzcGVjdGl2ZWx5LiAkKDEgXFxsZSBOLCBNIFxcbGUgMjAwXFwsMDAwKSQ8XC9wPlxyXG5cclxuPHA+VGhlIHNlY29uZCBsaW5lIGNvbnRhaW5zJm5ic3A7JE4kIGludGVnZXJzICRiXzEkLCAkYl8yJCwgJFxcY2RvdHMkLCAkYl9OJCwgc2VwYXJhdGVkIGJ5IHNwYWNlcy4gJCgtMVxcLDAwMFxcLDAwMCZuYnNwO1xcbGUgYl9pIFxcbGUgMVxcLDAwMFxcLDAwMCkkPFwvcD5cclxuXHJcbjxwPkZyb20gdGhlIHRoaXJkIGxpbmUgb253YXJkcywgZm9yIHRoZSBmb2xsb3dpbmcgJE0kIGxpbmVzLCBkZXRhaWxzIGFib3V0IHRoZSBhc3Rlcm9pZHMgYXJlIGdpdmVuLiBPbiB0aGUgJGokLXRoIGxpbmUsIHR3byBpbnRlZ2VycyAkYV9qJFx1MjAwYiBhbmQgJHdfaiRcdTIwMGIgYXJlIGdpdmVuLCBzZXBhcmF0ZWQgYnkgYSBzcGFjZS4gJCgtMVxcLDAwMFxcLDAwMCBcXGxlIGFfaiBcXGxlIDFcXCwwMDBcXCwwMDA7JCAkMSBcXGxlIHdfaiBcXGxlIDEwMCkkPFwvcD5cclxuXHJcbjxwPlRoZXJlIGNhbiBiZSBhIHNpbmdsZSBibGFjayBob2xlIG9yIGEgc2luZ2xlIGFzdGVyb2lkIGF0IG9uZSBwb3NpdGlvbiwgYnV0IG5vdCBib3RoLjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlByaW50IHRoZSBtaW5pbXVtIGludGVnZXIgdmFsdWUgb2YgJFAkIG5lZWRlZCBmb3IgYWxsIGJsYWNrIGhvbGVzIHRvIGFic29yYiBhbGwgdGhlIGFzdGVyb2lkcy48XC9wPlxyXG4iLCJoaW50IjoiPHA+SGVyZSwgJFxcdmVydCB4IFxcdmVydCQmbmJzcDtkZW5vdGVzIHRoZSBhYnNvbHV0ZSB2YWx1ZSBvZiAkeCQuIElmICR4IFxcZ2UgMCQsIHRoZW4gJFxcdmVydCB4IFxcdmVydCA9IHgkLCBhbmQgaWYgJHggJmx0OyAwJCwmbmJzcDskXFx2ZXJ0IHggXFx2ZXJ0ID0gLXgkLjxcL3A+XHJcbiIsIm9yaWdpbmFsIjoiMCIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiRW5nbGlzaCJ9XQ==