급료 계산

한 회사가 새 소프트웨어를 예상보다 한 달 일찍 완성했다. 남은 한 달 동안 테스트에 집중하려고 하며, 테스트 중 발견되는 버그를 처리하기 위해 임시 테스트 인력을 최대한 많이 고용하려고 한다.

각 인력에게는 한 달 동안의 최저임금 C원 이상을 현금으로 지급해야 한다. 회사의 자산은 정해진 화폐 단위별 현금 개수로 주어진다. 현금은 나눌 수 없고, 큰 단위의 화폐를 작은 단위로 바꾸는 경우도 고려하지 않는다. 따라서 총액만 충분하더라도 실제 보유한 화폐 조합에 따라 고용 가능한 인원 수가 줄어들 수 있다.

예를 들어 최저임금이 5원이고 회사가 1원짜리 1개와 10원짜리 1개만 가지고 있다면, 10원짜리 하나로 한 명에게 지급할 수 있지만 남은 1원으로는 다른 사람에게 지급할 수 없다.

화폐 단위는 배수적이다. 즉, 작은 순서로 정렬했을 때 각 단위는 바로 다음으로 큰 단위를 나눈다.

회사가 보유한 화폐와 최저임금이 주어질 때, 고용할 수 있는 최대 인원 수를 구하시오.

첫째 줄에 화폐 종류의 수 N과 최저임금 C가 주어진다. (1 <= N <= 20, 1 <= C <= 100,000,000)

다음 N개의 줄에는 두 정수 V와 B가 주어진다. 이는 V원짜리 화폐를 B개 가지고 있다는 뜻이다. (1 <= V <= 100,000,000, 1 <= B <= 1,000,000)

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