| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 2 초 | 512 MB | 77 | 36 | 31 | 55.357% |
Стена осаждённой крепости состоит из $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$).
Выходные данные должны содержать единственное целое число --- минимальное количество прорвавшихся в крепость нападающих.
| 번호 | 배점 | 제한 |
|---|---|---|
| 1 | 17 | 1ドル \le n \le 100,ドル 1ドル \le s \le 10,000円,ドル 1ドル \le a_i \le 100,ドル $k_i = 1$ |
| 2 | 21 | 1ドル \le n \le 100,ドル 1ドル \le s \le 10,000円,ドル 1ドル \le a_i \le 100,ドル $k_i \le 2$ |
| 3 | 23 | 1ドル \le n \le 100,ドル 1ドル \le s \le 10,000円,ドル 1ドル \le a_i \le 100,ドル 1ドル \le k_i \le 100$ |
| 4 | 39 | 1ドル \le n \le 100,000円,ドル 1ドル \le s \le 10^9,ドル 1ドル \le a_i \le 10^9,ドル 1ドル \le k_i \le 10^9$ |
1 10 8 1
0
3 3 4 2 1 1 10 8
3
В первом тесте, если поставить всех 10 защитников на единственный участок, они смогут отбить всех нападающих, и никто не пройдёт в крепость. Во втором примере можно, например, направить двух защитников на первый участок и одного --- на третий.