오가 가문의 재산

오가(Ohga) 가문은 명망 있는 가문입니다. 가문의 수장인 유명한 부자 네모치 오가(Nemochi Ohga) 씨는 자금을 운용 회사에 예치하여 재산을 불리고자 합니다. 주어진 자금을 정해진 기간 동안 운용하여 오가 씨의 수익이 최대가 되도록 도와주세요.

가능한 운용 방식 목록에서 정확히 하나를 선택하고, 전체 자금을 그 운용에 예치하며, 기간 내내 그 하나의 운용만을 유지합니다. 각 운용은 다음을 지정합니다.

• 연 이자율,
• 이자가 단리인지 복리인지,
• 연 운용 수수료 — 잔액과 무관한 상수.

매년 말에 이자는 현재 운용 중인 자금 잔액에 연 이자율을 곱한 뒤 소수부를 버려(내림하여) 계산합니다.

• 복리의 경우 이자는 운용 잔액에 더해지므로 이후 해에도 이자가 붙습니다.
• 단리의 경우 이자는 별도로 따로 보관되어 운용 잔액에 포함되지 않으므로 이후 해에는 이자가 붙지 않습니다.

이자 계산 후 운용 잔액에서 연 운용 수수료를 뺍니다. 수수료는 항상 지불할 수 있다고 가정합니다(운용 잔액이 수수료보다 작아지는 경우는 없습니다).

정해진 연수만큼 운용한 뒤 얻는 금액을 최종 자금액이라고 하며 다음과 같이 정의됩니다.

• 단리의 경우 마지막 해 말의 운용 잔액에 전체 기간 동안 누적된 이자의 합을 더한 값입니다.
• 복리의 경우 단순히 마지막 해 말의 운용 잔액입니다.

운용 회사들은 이자율에 특히 신경을 씁니다. 이자율은 항상 0.0001220703125의 정수배이며 0.0001220703125 이상 0.125 이하입니다. 0.0001220703125는 1/8192이므로, 이러한 이자율은 배정밀도 이진 부동소수점으로 오차 없이 표현할 수 있습니다.

예를 들어 1000000 JPY를 연 복리 이자율 0.03125(3.125%)와 연 운용 수수료 3000 JPY로 5년간 운용하면 잔액은 다음과 같이 변합니다.

5년 운용 후 최종 자금액은 1150357 JPY입니다.

같은 조건에서 이자가 단리라면 잔액은 다음과 같이 변합니다.

이 경우 최종 자금액은 마지막 운용 잔액 985000 JPY에 누적 이자 155311 JPY를 더한 1140311 JPY입니다.

입력은 여러 개의 데이터셋으로 구성됩니다. 전체 입력의 형식은 다음과 같습니다.

m
데이터셋 1
데이터셋 2
...
데이터셋 m

여기서 m은 데이터셋의 개수이며 100 이하입니다. 각 데이터셋의 형식은 다음과 같습니다.

초기 자금
운용 연수
n
운용 1
운용 2
...
운용 n

• 초기 자금 — 운용할 초기 자금액, 100000000 이하의 양의 정수.
• 운용 연수 — 운용 기간(연 단위), 10 이하의 양의 정수.
• n — 사용 가능한 운용의 개수, 100 이하의 양의 정수.

각 운용은 한 줄에 다음과 같이 주어집니다.

단리-또는-복리 연-이자율 연-운용-수수료

여기서 단리-또는-복리는 한 글자로 0은 단리, 1은 복리를 뜻하고, 연-이자율은 1/8192의 정수배인 소수이며, 연-운용-수수료는 100000을 넘지 않는 정수입니다.

각 데이터셋에 대해, 가장 좋은 운용의 최종 자금액을 나타내는 하나의 십진 정수를 한 줄에 출력하세요. 가장 좋은 운용이란 사용 가능한 운용 중 최종 자금액이 최대가 되는 운용을 말합니다. 그 줄에는 이 숫자 외의 어떤 문자도 있어서는 안 됩니다.

최종 자금액은 1000000000을 절대 넘지 않으며, 적어도 하나의 운용은 최종 자금액이 초기 자금 이상이라고 가정해도 됩니다.