2177번 - 급료 계산

한 회사에서 이번에 새로운 소프트웨어를 개발하였다. 개발이 예정 출시일보다 한 달 일찍 완료되었기 때문에, 한 달 동안은 새 소프트웨어를 테스트하는데 주력하기로 하였다. 테스트 과정에서 버그가 발견되면 수정을 해야 하기 때문에, 개발팀 대신 새로운 테스트팀을 조직하기로 하였고, 이를 위해 필요한 인력을 새로 구하기로 하였다.

테스트는 가급적 많은 인력이 동원되면 좋기 때문에, 회사에서는 최대한 많은 인력을 구하기로 하였다. 하지만 회사의 자산은 한정되어 있고, 한 달 동안의 최저임금이 정해져 있기 때문에 구할 수 있는 인력도 한정되게 된다.

게다가 회사에서 보유중인 자산이 현금 자산이기 때문에 구할 수 있는 인력은 더욱 한정되게 된다. 예를 들어 최저임금이 5원이고, 회사에서 1원짜리와 10원짜리로 11원을 보유하고 있다고 하자. 현금 자산이 아니라면 11원을 반으로 나눠 두 명의 인력을 고용할 수 있지만, 현금 자산이기 때문에 고용할 수 있는 인력은 한 명이 된다. 즉, 한 명의 인력에게 10원짜리 하나를 주게 되면 남는 돈이 1원 뿐이기 때문에 더 이상의 인력을 고용할 수 없다.

물론, 큰 단위의 화폐를 작은 단위의 화폐로 바꾸는 경우는 고려하지 않는다. 또, 화폐 단위는 배수적이라고 가정하자. 즉, 화폐의 각 단위가 다음으로 큰 단위를 나눈다고 가정하자. 예를 들어 화폐 단위가 1, 5, 10, 100원인 경우에는 1이 5를 나누고, 5가 10을 나누고, 10이 100을 나누기 때문에 배수적인 화폐 단위가 된다.

회사가 현재 보유중인 자산과 최저 임금에 대한 정보가 주어졌을 때, 고용할 수 있는 최대 인력의 수를 구하는 프로그램을 작성하시오.

첫째 줄에 회사가 보유하고 있는 화폐 종류의 수와 최저임금을 나타내는 두 정수 N(1 ≤ N ≤ 20), C(1 ≤ C ≤ 100,000,000)가 주어진다. 다음 N개의 줄에는 회사가 보유하고 있는 자산에 대한 정보를 나타내는 두 정수 V(1 ≤ V ≤ 100,000,000), B(1 ≤ B ≤ 1,000,000)가 주어진다. 이는 회사가 V원짜리 화폐를 B개 보유하고 있다는 의미이다.

첫째 줄에 고용할 수 있는 최대 인력의 수를 출력한다.