| 问题描述 |
|---|
在一款名为“MY LITTLE PONY-友谊的魔法”的游戏中，可以派遣彩虹小马到不同的商店里打工挣钱，商店每隔一段时间都能发一笔工钱，如果打工时间未到就中止打工，则不发工钱。假设玩家JP拥有一匹小马，并且固定地安排在某家商店里打工，中途不变更商店。JP只想玩一段时间，时间到了就会让小马停止打工。JP想知道，把小马派到哪家商店才能在这段时间内挣到最多的钱。 |
| 输入描述 |
1个正整数n，表示测试案例的数量。 每组测试案例中，第1行是2个正整数t和m，其中t表示JP玩游戏的时间，m表示商店的数量， 从第2行到第m+1行是这m家商店的信息，每行有两个正整数a和b，表示这家商店每a时间可以挣b元。 |
| 输出描述 |
针对每组案例，输出最多能挣的金额。每组案例输出后都要换行。 |
| 样例输入复制样例 |
2 6 2 1 2 2 3 5 2 2 3 4 4 |
| 样例输出 |
12 6 |
| 提示说明 |
第一组案例中，应当选择在1秒挣2元的商店里打工，在6秒内能挣12元，另一个商店2秒挣3元，在6秒内只能挣9元，故答案是12。 第二组案例中，应当选择在2秒挣3元的商店里打工，在5秒内能挣6元（最后1秒挣不到钱），另一个商店4秒挣4元，在5秒内只能挣到4元（同样，最后1秒不挣钱），故答案是6。 |
| 相关 |