선형 온난화

이미지 출처

리눌란드의 주민들은 최근 이 나라에 대학교가 세워질 것이라는 소식을 들었다. 이들은 이에 매우 기뻐하고 있다. 학교에서 선형대수학, 선형 최적화, 선형 함수해석학 등을 가르칠 예정이기 때문이다.

온실 효과는 다른 나라들과 마찬가지로 리눌란드에도 악영향을 미쳤고, 이로 인해 심각한 선형 온난화가 발생했다. 당국은 새 대학교의 학생들이 자동차로 통학하기 시작하면 이산화탄소 오염이 증가하여 상황이 악화될 수 있다고 우려한다. 따라서 오염을 최소화하도록 학교의 위치를 선정하는 일을 돕기 위해 여러분을 고용했다.

이름에서 알 수 있듯이 리눌란드의 사람들은 하나의 직선 위에 산다. 이 나라의 집 번호는 양의 정수이며, 번호가 $a$인 집과 번호가 $b$인 집 사이의 거리는 $|a-b|$킬로미터이다.

대학교 학생들의 목록과 각 학생이 사는 곳, 그리고 각 학생의 자동차가 킬로미터당 배출하는 이산화탄소의 양이 주어질 때, 학생들이 매일 아침 자동차로 통학하면서 발생시키는 전체 이산화탄소 오염을 최소화하려면 어느 집 번호에 대학교를 세우는 것이 가장 좋은지 구한다.

여러 학생이 같은 집 번호에 살 수도 있음에 유의한다. 학생들이 이미 사는 집에 대학교를 세워도 되며, 그 경우 그 학생들은 그저 대학교에서 살게 된다. (와, 운도 좋지!)

채점

그룹 | 점수 | 제한

1 | 25 | $n \leq 10^3$, $x_i \leq 10^3$

2 | 25 | $x_i \leq 10^3$

3 | 20 | $c_i = 1$

4 | 30 | 추가 제한 없음

입력의 첫 줄에는 새 대학교의 학생 수를 나타내는 하나의 정수 $n$ ($1 \leq n \leq 2\cdot10^5$)이 주어진다.

이어서 각 학생에 대해 한 줄씩, $n$개의 줄이 주어진다. $i$번째 줄에는 두 정수 $x_i$ ($1 \leq x_i \leq 10^9$)와 $c_i$ ($1 \leq c_i \leq 10^3$)가 주어진다. 전자는 학생 $i$가 사는 집의 번호이고, 후자는 학생 $i$의 자동차가 킬로미터당 배출하는 이산화탄소의 양이다.

학생들이 매일 아침 자동차로 통학하면서 발생시키는 전체 이산화탄소 오염을 최소화하려면 대학교를 어느 집 번호에 세우는 것이 가장 좋은지 출력한다. 가능한 집 번호가 여러 개라면, 그중 가장 작은 집 번호를 출력한다.