DOJ 연구소에서는 번부터 번까지 번호가 붙은 종류의 미생물을 관리하고 있다.
번 미생물의 일차 개체 수는 이고, 하루가 지날 때마다 개체 수가 만큼 증가한다. 이때 를 성장 계수라고 한다. 예를 들어, 처음 개체 수가 이고 성장 계수가 이면 일차, 일차, 일차의 개체 수는 각각 , , 이다.
연구소장 다다스는 어느 날 몇 종류의 미생물을 골라 연구 표본으로 삼으려고 한다. 단, 고른 미생물들을 다음 두 방법으로 정렬했을 때 번호가 나열되는 순서가 같아야 한다.
두 방법 모두 기준값이 같으면 번호가 작은 종류를 먼저 나열한다. 각 정렬에는 연구 표본으로 고른 종류만 포함한다.
다다스는 위 조건을 만족하는 미생물을 종류 이상 고를 수 있는 일차에 연구를 시작하려고 한다.
연구를 시작할 수 있는 가장 빠른 일차를 구하여라. 일차는 이상의 정수다. 어떤 일차에도 미생물을 종류 이상 고를 수 없다면 -1을 출력하여라.
입력은 다음과 같은 형식으로 주어진다.
각 테스트 케이스마다 조건을 만족하는 미생물을 종류 이상 고를 수 있는 가장 빠른 일차를 한 줄에 출력한다. 그러한 일차가 없다면 -1을 출력한다.
정답이 -1이 아니라면 이상 이하임을 증명할 수 있다.
첫 번째 테스트 케이스의 일차 개체 수는 이다. 어느 두 종류를 고르더라도 성장 계수가 작은 쪽의 개체 수가 더 많으므로 두 정렬의 순서가 다르다. 일차의 개체 수는 이다. 번과 번을 고르면 성장 계수 순서는 이다. 두 종류의 개체 수가 같을 때 번호가 작은 번이 먼저 오므로 개체 수 순서도 이다. 따라서 정답은 이다.
는 테스트 케이스의 개수이다. 각 테스트 케이스는 다음과 같은 형식으로 주어진다.
첫째 줄에 미생물의 종류 수 과 연구에 필요한 최소 종류 수 가 공백으로 구분되어 주어진다.
다음 개의 줄 중 번째 줄에는 번 미생물의 일차 개체 수 와 성장 계수 가 공백으로 구분되어 주어진다.
| 2 | 21 | . |
| 3 | 29 | . |
| 4 | 37 | 추가적인 제약이 없다. |
두 번째 테스트 케이스의 일차에는 최대 종류만 고를 수 있다. 일차에는 개체 수가 모두 이므로 두 정렬의 순서가 으로 같아져 종류를 모두 고를 수 있다. 필요한 종류 수 보다 많이 골라도 괜찮으므로 정답은 이다.
세 번째 테스트 케이스의 일차에 번과 번을 고르면 두 순서가 모두 이다. 처음부터 종류를 고를 수 있으므로 정답은 이다.
네 번째 테스트 케이스에서는 성장 계수가 모두 같으므로 개체 수가 항상 번호 순서로 감소한다. 어느 두 종류를 고르더라도 성장 계수 순서는 번호가 작은 쪽이 먼저이고, 개체 수 순서는 번호가 큰 쪽이 먼저이다. 따라서 아무리 기다려도 종류를 고를 수 없다.
