В некоторой стране построен радиотелескоп. Антенны телескопа расположены вдоль шоссе. Номер антенны соответствует километровой отметке от начала шоссе. Каждая антенна в сутки принимает определённое количество сигналов. Компьютер антенны формирует из сигналов пакет данных и отправляет его в центр обработки. Количество сигналов в одном пакете не превышает 100. Центр обработки разместили рядом с одной из антенн так, чтобы количество энергии, расходуемой на передачу данных от всех антенн, было минимальным.
Количество энергии, необходимое для передачи всех пакетов с данными, равно произведению расстояния от антенны до центре обработки на количество передаваемых пакетов с данными. Определите номер антенны, рядом с которой следует разместить центр обработки данных. Если таких номеров несколько, укажите наименьший из них.
Входные данные:
Даны два входных файла: файл A (27A.txt) и файл B (27B.txt), каждый из которых содержит в первой строке число: количество антенн N (1 ≤ N ≤ 10 000 000). Каждая из следующих N строк содержит два натуральных числа – номер антенны и количество сигналов, принятых антенной (количество принимаемых сигналов не превышает 1000). Антенны нумеруются в порядке их расположения вдоль шоссе, начиная с нулевой отметки.
В ответе укажите два числа: сначала искомый номер антенны для файла А, затем для файла B.
Пример входного файла:
6
1 100
3 250
8 7
10 4
15 1
31 160
Для данного примера ответ — 8. Для случая, когда центр обработки данных размещён около 8-й антенны, суммарную энергию, необходимую для передачи данных, можно оценить как 7·1 + 5·3 + 2·1 + 7·1 + 23·2 = 77.
