Рик C-137 и его Морти пытаются выследить Рика Прайма, и для этого им приходится много перемещаться между измерениями. Всего есть $$$n$$$ измерений, в которых Рик Прайм может находиться, и $$$i$$$-е измерение на плоской карте измерений находится в точке с координатами $$$(x_i, y_i)$$$. Также у каждого измерения есть свой приоритет $$$p_i$$$ — целое число, задающее, насколько вероятно появление в нем Рика Прайма.
Чтобы попасть из точки на карте с координатами $$$(x, y)$$$ в измерение $$$i$$$, Рику и Морти потребуется $$$\max(|x - x_i|, |y - y_i|)$$$ времени. Поскольку изначально неизвестно, в каком измерении будет обнаружен Рик Прайм, текущая цель — расположиться в такой точке, от которой быстрее всего можно добраться до любого из $$$n$$$ измерений с учетом приоритетов.
Формально, требуется найти такие $$$x$$$ и $$$y$$$, при которых величина $$$$$$\sum\limits_{i=1}^n p_i \cdot \max(|x - x_i|, |y - y_i|)$$$$$$ минимальна.
Помогите Рику и Морти определить такую точку $$$(x, y)$$$. Точка $$$(x, y)$$$ при этом может быть любой точкой на карте с целыми или полуцелыми координатами, не обязательно совпадающей с одним из $$$n$$$ данных измерений.
В первой строке ввода дано целое число $$$n$$$ — количество рассматриваемых измерений ($$$1 \le n \le 2 \cdot 10^5$$$).
Во второй строке через пробел перечислены $$$n$$$ целых чисел $$$p_i$$$ — приоритеты измерений ($$$1 \le p_i \le 10^6$$$).
В $$$i$$$-й из следующих $$$n$$$ строк через пробел даны два целых числа $$$x_i$$$ и $$$y_i$$$ — координаты $$$i$$$-го измерения на карте ($$$|x_i|, |y_i| \le 10^6$$$).
Выведите через пробел два целых числа $$$2x$$$ и $$$2y$$$ — удвоенные координаты точки, в которой следует расположиться Рику и Морти. Если точек, минимизирующих искомую величину, несколько, выведите любую из них.
4 1 1 1 3 -2 -2 -2 2 2 -2 2 2
0 0
5 2 1 1 3 4 0 1 19 6 17 21 17 21 7 10
14 20