C. When democracy fails

В одной демократической стране приближаются парламентские выборы. Каждый житель отдаёт голос за одну из партий; партия, набравшая максимум голосов, формирует правительство. Если максимум набрали несколько партий, приходится формировать коалицию.

Бизнесмен хочет добиться строгой победы одной из партий. Чтобы один житель сменил политические воззрения, нужно потратить одну условную единицу. Кроме того, чтобы $i$-я партия в случае победы действовала в его интересах, лидеру нужно дать взятку $b_i$. Некоторые партии идеологически устойчивы и не согласны на сотрудничество ни за какие деньги.

Помогите выбрать, какую партию подкупить и сколько граждан переубедить, чтобы потратить как можно меньше.

В первой строке целое число $n$ — количество партий ($1 \le n \le 10^5$). Следующие $n$ строк описывают партии: $r_i$ — сколько жителей собираются голосовать за неё, и $b_i$ — взятка ($1 \le r_i \le 10^6$, $1 \le b_i \le 10^6$ или $b_i = -1$). Если партия идеологически устойчива, то $b_i = -1$. Гарантируется, что хотя бы одно $b_i$ не равно $-1$.

В первой строке минимальная сумма. Во второй — номер партии, лидеру которой следует дать взятку. В третьей — $n$ целых чисел: количество голосов за каждую партию после операции. Если оптимальных решений несколько, выведите любое.