투자

목돈을 여러 해 동안 투자하여 최대한 크게 불리려고 합니다.

투자는 채권(bond) 을 사는 방식으로 합니다. 각 채권 종류에는 고정된 가격이 있고, 매년 말에 소유자에게 고정된 연이자를 지급합니다. 채권에는 만기가 없어 원하는 만큼 계속 보유할 수 있으며, 사고파는 데 드는 수수료도 없습니다. 보유한 채권의 가격 합이 현재 자본을 넘지 않는 한, 각 종류의 채권을 원하는 개수만큼 살 수 있습니다.

매년 말에는 보유한 모든 채권의 이자가 자본에 더해집니다. 자본이 늘어나면 보유하기에 가장 좋은 채권 구성도 달라질 수 있으므로, 매년 포트폴리오를 다시 구성합니다.

예를 들어 다음과 같은 채권을 살 수 있다고 합시다.

자본이 10000이면 가격 4000짜리 채권 두 개를 사서 매년 800의 이자를 받을 수 있습니다. 하지만 가격 3000짜리 두 개와 4000짜리 한 개를 사면 매년 900을 받아 더 낫습니다. 2년 뒤 자본은 11800으로 늘어나고, 이제는 4000짜리 두 개와 3000짜리 한 개를 보유하는 것이 유리해 연이자가 1050으로 올라갑니다. 그다음 해에는 자본이 12850이 되어 4000짜리 세 개를 보유할 수 있고, 매년 1200의 이자를 받습니다.

시작 금액, 햇수, 그리고 각 채권의 가격과 이자가 주어질 때, 사고파는 최적의 계획을 따랐을 때 주어진 기간 동안 자본을 최대 얼마까지 불릴 수 있는지 구하세요.

첫째 줄에 테스트 케이스의 수 $N$(양의 정수)이 주어집니다. 이어서 각 테스트 케이스가 주어집니다.

각 테스트 케이스의 첫째 줄에는 두 양의 정수가 주어집니다: 시작 금액(최대 1000000)과 자본을 불릴 햇수(최대 40)입니다.

다음 줄에는 정수 $d$($1 \le d \le 10$), 즉 살 수 있는 채권 종류의 수가 주어집니다.

이어지는 $d$개의 줄에는 각각 채권 하나가 두 양의 정수로 주어집니다: 채권의 가격과 연이자입니다. 모든 채권의 가격은 1000의 배수이며, 이자는 결코 가격의 10%를 넘지 않습니다.

각 테스트 케이스마다, 최적의 매매 계획을 따랐을 때 기간이 끝난 시점의 자본을 한 줄에 하나씩 출력하세요.