20520번 - Оборона крепости 서브태스크다국어

Стена осаждённой крепости состоит из $n$ участков, пронумерованных от 1 до $n$. Разведка доложила, что при следующем штурме противник отправит для нападения на участок с номером $i$ отряд из $a_i$ солдат. Для обороны крепости на участки стены будут направлены $s$ защитников.

Участки стены различаются качеством укреплений, что приводит к различной эффективности обороны. Один защитник участка стены с номером $i$ способен отразить атаку $k_i$ нападающих.

Пусть на участок с номером $i$ отправлено $x_i$ защитников. Тогда если количество нападающих не превышает величину $x_i \cdot k_i$, то на этом участке ни один из нападающих не прорвётся в крепость. Иначе в крепость прорвутся $a_i - x_i \cdot k_i$ нападающих.

Требуется написать программу, распределяющую защитников по участкам так, чтобы их общее количество было равно $s$ и в крепость прорвалось как можно меньше нападающих.

Первая строка входных данных содержит целые числа $n$ --- количество участков стены и $s$ --- количество защитников крепости ($1 \leq n \leq 100\,000$; $1 \leq s \leq 10^9$).

Следующие $n$ строк содержат по два целых числа $a_i, k_i$ --- общее количество нападающих на $i$-й участок стены и количество нападающих, которое может отразить один защитник этого участка ($1 \leq a_i, k_i \leq 10^9$).

Выходные данные должны содержать единственное целое число --- минимальное количество прорвавшихся в крепость нападающих.

В первом тесте, если поставить всех 10 защитников на единственный участок, они смогут отбить всех нападающих, и никто не пройдёт в крепость. Во втором примере можно, например, направить двух защитников на первый участок и одного --- на третий.