돼지 저금통

ACM이 무언가를 하려면 먼저 예산을 마련하고 필요한 재정 지원을 확보해야 합니다. 이 활동의 주요 수입원은 '되돌릴 수 없이 묶인 돈'(Irreversibly Bound Money, IBM)입니다. 발상은 간단합니다. ACM 회원은 자잘한 돈이 생길 때마다 동전을 모두 돼지 저금통에 넣습니다. 이 과정은 되돌릴 수 없어서, 저금통을 깨뜨리지 않고는 동전을 꺼낼 수 없습니다. 충분히 오랜 시간이 지나면 저금통 안에는 필요한 지출을 모두 감당할 만큼의 현금이 쌓이게 됩니다.

그런데 저금통에는 큰 문제가 있습니다. 안에 돈이 얼마나 들어 있는지 알 수 없다는 점입니다. 그래서 저금통을 깨뜨렸는데 돈이 부족한 상황이 생길 수 있습니다. 당연히 우리는 이런 불상사를 피하고 싶습니다. 유일한 방법은 저금통의 무게를 재서 안에 동전이 몇 개나 들어 있는지 추측하는 것입니다. 저금통의 무게를 정확히 잴 수 있고, 해당 통화의 모든 동전 무게를 알고 있다고 가정합니다. 그러면 저금통 안에 최소한 얼마의 돈이 들어 있다고 보장할 수 있는 값이 존재합니다. 여러분의 임무는 이 최악의 경우를 찾아, 저금통 안에 든 현금의 최솟값을 구하는 것입니다.

입력은 T개의 테스트 케이스로 이루어집니다. 첫 번째 줄에 테스트 케이스의 개수 T가 주어집니다.

각 테스트 케이스의 첫 줄에는 두 정수 E와 F가 주어집니다. 각각 빈 저금통의 무게와 동전이 가득 찬 저금통의 무게이며, 단위는 그램입니다. 어떤 저금통도 10kg을 넘지 않으므로 $1 \le E \le F \le 10000$ 입니다.

각 테스트 케이스의 둘째 줄에는 해당 통화에 쓰이는 동전 종류의 수 N ($1 \le N \le 500$)이 주어집니다. 이어서 정확히 N개의 줄에 동전 종류가 하나씩 주어지며, 각 줄에는 두 정수 P와 W ($1 \le P \le 50000$, $1 \le W \le 10000$)가 있습니다. P는 동전의 화폐 가치, W는 동전의 무게(그램)입니다. 각 종류의 동전은 개수 제한 없이 사용할 수 있습니다.

각 테스트 케이스마다 정확히 한 줄을 출력합니다. 주어진 총 무게를 동전들로 정확히 만들 수 있다면 The minimum amount of money in the piggy-bank is X. 형식으로 출력합니다. 여기서 X는 그 무게를 만들 수 있는 동전 화폐 가치 합의 최솟값입니다. 무게를 정확히 만들 수 없다면 This is impossible. 을 출력합니다.