성벽 방어 서브태스크 2초 512MB
문제
정올국 요새의 성벽이 포위되었습니다.
포위된 성벽에는 1부터 n까지의 번호가 붙은 n개의 구역이 있습니다.
정보에 따르면, 다음 공격에 적이 i구역에 ai명의 병사를 공격하도록 보낼 것입니다.
요새의 방어를 위해 총 s명의 수비병이 각 구역으로 보내질 것입니다.
성벽의 각 구역은 강도가 전부 다르기 때문에 방어의 효율성이 다릅니다.
정확히는, i번째 구역의 한 명의 수비병은 ki명의 공격을 무찌를 수 있습니다.
예를 들어, i번 성벽에 xi명의 수비병이 보내졌다고 합시다.
공격병의 수가 xi*ki를 초과하지 않으면 0명의 공격병이 성벽 안으로 칩입합니다.
이외의 경우, ai - xi*ki명의 공격병이 성벽 안으로 칩입합니다.
수비병이 총 s명 있을 때, 구역 간에 수비병을 분배하여 최대한 적은 공격병이 성벽 안으로 칩입하도록 하세요.
입력
첫 번째 줄에는 n과 s가 공백으로 구분되어 주어집니다.
다음의 n개의 줄에 걸쳐, ai와 ki가 공백으로 구분되어 주어집니다.
부분문제
#1(61점) : 1 <= n <= 100, 1 <= s <= 10000, 1 <= ai <= 100
#2(39점) : 1 <= n <= 100000, 1 <= s <= 1000000000, 1 <= ai <= 1000000000, 1 <= ki <= 1000000000
출력
첫 번째 줄에 성벽 안으로 칩입한 공격병의 최소 수를 출력하세요.
예제 #1
1 10
8 1
0
예제 #2
3 3
4 2
1 1
10 8
3
로그인해야 코드를 작성할 수 있어요.