용돈 1초 32MB

문제

정올이의 형은 N개의 서로 다른 단위의 동전을 갖고 있으며, 더 단위가 작은 동전을 이용하여 큰 동전을 만드는 것이 가능한 단위로만 이루어져 있다. 즉, 각 동전의 단위는 서로 배수 관계가 성립한다.

정올이의 형은 정올이에게 매주 C원 이상의 용돈을 주려고 하는데, 갖고 있는 동전들로 최대 몇 주 동안 용돈을 주는 것이 가능할지 알아보자.

첫 줄에 두 정수 N과 C가 주어진다. (1\le N\le 20; 1\le C\le 10^8)

두 번째 줄부터 N줄에 걸쳐 각 동전의 단위 V와 그 단위 동전의 수 B가 주어진다. (1\le V\le 10^8; 1\le B\le 10^6)

첫 줄에 갖고 있는 동전들로 최대 몇 주 동안 용돈을 줄 수 있는지 출력한다.

입력

3space_bar6keyboard_return
10space_bar1keyboard_return
1space_bar100keyboard_return
5space_bar120

출력

첫 주에 10원 동전을 하나 준다.

다음 10주 동안 두 개의 5원 동전을 준다.

다음 100주 동안 5원 동전 하나와 1원 동전 하나를 준다.

USACO October 2009 Gold 7