동아리 분반하기

ACM(All Can Meet) 동아리는 모든 연령대의 사람들이 함께 모여 삶의 경험을 나누며 서로에게 도움을 주자는 취지로 만들어졌다. 동아리가 큰 인기를 끌면서 모든 회원을 같은 시간, 같은 장소에 모으는 일이 사실상 불가능해졌고, 그래서 동아리는 회원들을 더 작은 분반으로 나누기로 했다. 분반이 한쪽으로 치우치지 않도록, 회장은 다음 세 가지 조건을 정했다.

1. 나이가 같은 회원은 모두 같은 분반에 속해야 한다.
2. 모든 회원은 정확히 하나의 분반에만 속해야 한다.
3. 각 분반에서, 같은 나이를 가진 회원 수의 최댓값은 같은 나이를 가진 회원 수의 최솟값의 $R$배를 넘지 않아야 한다. 여기서 분할 계수라고 부르는 $R$는 $1.0 \le R \le 2.0$인 유리수이다.

세 번째 조건은 어떤 분반 안에 다른 나이 집단보다 지나치게 작은 나이 집단이 들어가 그 회원들이 소외감을 느끼는 일을 막아 준다.

예를 들어, $m$살인 회원이 $n$명 있는 집단을 [n, m]으로 나타내자. 분반 {[10, 50], [6, 45], [70, 12], [43, 23]}에서는 같은 나이 회원 수의 최댓값이 70, 최솟값이 6이므로, $R = 2.0$일 때 $70 / 6 > 2.0$이 되어 세 번째 조건을 만족하지 않는다. 하지만 이 분반을 {[10, 50], [6, 45]}와 {[70, 12], [43, 23]}의 두 분반으로 나누면 세 조건을 모두 만족한다.

분할 계수 $R$와 회원 목록이 주어질 때, 가능한 분반의 최소 개수를 구하여라.

입력은 여러 개의 테스트 케이스로 이루어진다. 각 테스트 케이스의 첫 줄에는 정수 $K$와 유리수 $R$가 주어진다. $K$는 동아리에 존재하는 서로 다른 나이의 수이고($1 \le K \le 120$), $R$는 분할 계수이다($1.0 \le R \le 2.0$). 이어지는 $K$개의 줄에는 각각 두 정수 $N$과 $M$이 주어지며, 이는 동아리에 $M$살인 회원이 $N$명 있음을 뜻한다($1 \le N \le 10000$, $1 \le M \le 120$). 모든 나이는 서로 다르다. 입력의 끝은 $K = 0$, $R = 0.0$인 줄로 표시되며, 이 줄은 처리하지 않는다.

입력 값은 $R$를 이진수로 표현할 때 생기는 오차가 정답에 영향을 주지 않도록 주어진다.

각 테스트 케이스마다, 세 조건을 모두 만족하는 분반의 최소 개수를 한 줄에 출력한다.