Задача №113217. Оборона крепости
Стена осаждённой крепости состоит из n участков, пронумерованных от 1 до \(n\). Разведка доложила, что противник планирует отправить на штурм участка стены с номером \(i\) отряд из \(a_i\) нападающих. Для обороны крепости на участки стены будут направлены в общей сложности \(s\) защитников.
Участки стены различаются качеством укрепления, что приводит к различной эффективности обороны: на участке стены с номером \(i\) каждый защитник способен отразить атаку \(k_i\) нападающих.
Пусть на участок с номером \(i\) отправлено \(x_i\) защитников. Тогда если количество нападающих не превышает величину \(x_i\) · \(k_i\) , то на этом участке ни один из нападающих не прорвётся в крепость. Иначе в крепость прорвутся (\(a_i − x_i · k_i\)) нападающих.
Требуется написать программу, распределяющую защитников по участкам стены так, чтобы их общее количество было равно \(s\) и в крепость прорвалось наименьшее количество нападающих.
Первая строка входных данных содержит целые числа n — количество участков стены и \(s\) — количество защитников крепости (\(1 \le n \le 100 000; 1 \le s \le 10^9\) ).
Следующие n строк содержат по два целых числа \(a_i , k_i\) — общее количество нападающих на \(i\)-й участок стены и количество нападающих, атаку которых может отразить один защитник этого участка (\(1 \le a_i , k_i \le 10^9\) ).
Выходные данные должны содержать единственное целое число — минимальное количество нападающих, которые прорвутся в крепость.
В первом тесте ни один из нападающих не прорвется в крепость, если поставить всех 10 защитников на единственный участок, так как они смогут отбить всех нападающих. Во втором примере можно, например, направить двух защитников на первый участок и одного — на третий.
1 10 8 1
0
3 3 4 2 1 1 10 8
3