Взвешенная медиана

На прямой стоят $n$ домов: $i$-й в точке $a_i$, и в нём живёт $w_i$ человек. Надо поставить колодец в целой точке $x$ так, чтобы суммарный путь $\sum w_i |a_i - x|$ был наименьшим. Выведите этот наименьший суммарный путь.

В первой строке $n$ ($1 \le n \le 10^5$). В каждой из следующих $n$ строк — целые $a_i$ и $w_i$ ($0 \le a_i \le 10^6$, $1 \le w_i \le 1000$).

Выведите наименьший суммарный путь.