우체국

수직선 위에 N개의 마을이 있다. i번째 마을은 좌표 X[i]에 있고, 그 마을에는 A[i]명이 산다.

이 마을들을 위해 우체국 하나를 세우려고 한다. 우체국의 위치는 모든 사람까지의 거리 합이 최소가 되도록 정한다. 우체국을 세울 위치를 출력하는 프로그램을 작성하라.

마을마다 한 번씩 거리를 더하는 것이 아니라, 각 마을의 인구수만큼 사람까지의 거리를 더한다는 점에 유의하라.

첫째 줄에 N (1 <= N <= 100,000)이 주어진다. 다음 N개의 줄에는 각 마을의 위치 X[i]와 인구 A[i]가 한 줄에 하나씩 주어진다.

모든 입력은 정수이며, |X[i]| <= 1,000,000,000, 1 <= A[i] <= 1,000,000,000 이다.

모든 사람까지의 거리 합이 최소가 되는 우체국의 위치를 첫째 줄에 출력한다. 가능한 위치가 여러 개이면 그중 가장 작은 위치를 출력한다.