描述

周幽王想卖出房子来挣钱。现在他有\(m\)两银子，有\(d\)栋房子供他挑选，每栋房子有一个购买值。当周幽王买下这栋房子之后，他可以每年收房客钱。\(m\)是\(1000\)的倍数，问：周幽王在\(n\)年之后能从房客手里榨多少钱？

格式

输入格式

第一个为一个整数\(t\)，表示有\(t\)组数据。
每组数据第一行有两个整数，表示初始资金\(s\)和年数\(n\)。
每组数据第二行为一个整数\(d\)，表示房子个数。
随后\(d\)行每行有两个整数，表示该房子的收购值和房租。一年的房子不会超过房子价值的\(10\)%。

输出格式

每组数据，输出\(n\)年后获得的最大房租。

样例1

输入样例1

1
10000 4
2
4000 400
3000 250

输出样例1

14050

限制

对于\(100\)%的数据，\(t≤5,s≤50000,d≤10\)

来源

地址：\(vijos\)，芜湖\(OI\)团队
作者：黑暗路西法\(08\)
模拟赛\(T4\)