收益 描述

“啥？买这套装备要一百万？”，迪迦瞪大了眼睛

“这只是衣服的价格，还有武器，盾牌啥的”赛罗掰着手指算。

“哎呀，现在奥特曼也很穷啊，没办法，我们还有一点零花钱，想办法用这笔钱在市场上获得最大收益吧。”奥特曼们商量着。

简单来说，就是你有一笔钱，你要将这笔钱去投资债券，现在有d种债券，每种债券都有一个价值和年收益，债券的价值是1000的倍数，问你如何投资在n年后的获得最大收益。

输入 第一个为一个整数M，表示有M组数据。

每组数据第一行有两个整数，表示初始资金(不超过50000)和年数n。

每组数据第二行为一个整数d(1 ≤ d≤10)，表示债券种类。

随后d行每行有两个整数，表示该债券的价值和年收益。年收益不会超过债券价值的10%。

所有数据不超过整型取值范围。

输出 每组数据，输出n年后获得的最大收益。

输入样例 1

1 10000 4 2 4000 400 3000 250 输出样例 1

14050