Оборона крепости

Стена осаждённой крепости состоит из $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 защитников на единственный участок, они смогут отбить всех нападающих, и никто не пройдёт в крепость. Во втором примере можно, например, направить двух защитников на первый участок и одного --- на третий.