시간 제한 메모리 제한 제출 횟수 정답 횟수 (비율) 정답자 수
1.0 초 512 MB 829 84 (10%) 65
문제
강원도 산골짜기에 사이 좋기로 소문난 지역이 있다. 하지만 어찌나 외부와 교류를 하지 않는지, 이 소문을 듣기까지 30년이 걸렸다. 이를 딱하게 여긴 정우는 이 마을에 외부와 통하는 버스정류장을 놓기로 했다. 버스정류장이 가까우면 조금만 걸어도 되기 때문에, 사람들은 가까운 곳에 버스정류장이 있었으면 한다. 그래서 이를 두고 사람들이 싸우기 시작했다. 정우는 굉장히 합리적인 사람이기 때문에, 합리적으로 버스정류장의 위치를 정하고자 했다. 이 지역은 일직선으로 되어있고, $N$개의 마을이 살고 있다. $i$번 마을의 위치는 $X[i]$이고, 이 마을에는 $A[i]$명의 사람이 살고있다. 또한 버스 정류장도 이 일직선 상에 놓이게 된다(꼭 마을에 버스 정류장이 세워질 필요는 없다). 정우가 정한 합리적인 방법은 각 사람들이 버스 정류장까지 가는 거리의 합을 최소화하는 것이다. 정우는 논리적인 사람이기 때문에, 정우의 설명에 반박하는 사람은 없었다. 마을의 개수 $N$과 각 마을의 위치와 마을에 사는 사람의 수가 주어졌을 때, 어디에 버스정류장을 세워야 하는지 구해주세요.
입력
첫 번째 줄에 마을의 개수 $N$이 주어진다. $(1 \le N \le 100,000)$. 두 번째 줄부터 $N$개의 줄에 걸쳐 각 마을의 정보 $X[i], A[i]$가 공백으로 분리되어 주어진다. $(-1,000,000,000 \le X[i] \le 1,000,000,000,$ $0 \le A[i] \le 1,000,000,000)$
출력
첫 번째 줄에 정우의 합리적 방법에 의해 세워지는 버스정류장의 위치를 출력한다. 이런 정류장의 위치가 여러 개인 경우, 위치의 크기가 가장 작은 것을 출력한다.
힌트
#### 예제 입력 ``` 3 1 3 2 5 3 3 ``` #### 예제 출력 ``` 2 ```