小L打怪兽
时间限制：C/C++/Rust/Pascal 3秒，其他语言6秒
空间限制：C/C++/Rust/Pascal 512 M，其他语言1024 M
64bit IO Format: %lld

题目描述

小 L 和他的朋友们去打怪兽, 他们一共有 k 个人, 每个人的体力都是相同的为 m, 目前他们将面对 n 种怪物, 每种怪物都是打不完的, 但他们的体力是有限的, 每打死某种怪物一次, 会消耗一定的体力, 并获得一定的积分, 小L 和他的朋友们都有强迫症, 所以想要恰好消耗完全部体力, 才离开, 如果不能每个人都离开, 则宣告任务失败输出 -1, 注意, 对于这 k 个人, 他们打怪的情况不能 "相同", 请问每个人都能离开的前提下, 每个人都想获得尽可能多的积分, 请问所有人中获得的积分的最小值是多少?
"相同": 设第 i 个人打第 j 个怪次数为, 那么我们说两个人 x，y 打怪的情况相同，则有
对于任意的 j，都有

输入描述:

第一行包含一个整数 T 
第二行包含三个数 k, m, n 分别表示总人数, 体力, 怪物的种类数 
接下来每行两个数，a, b 表示打死该怪物需要消耗的体力和打死后可以获得的积分

输出描述:

共 T 行, 每行表示所有人中获得的积分的最小值, 或者输出 -1 表示任务失败
示例1

输入

复制 
2
1 10 5
3 12
7 20
2 4
5 6
1 1
2 10 5
3 12
7 20
2 4
5 6
1 1

输出

复制 
37
32

说明

对于样例1: 能够获得最多积分的情况是 12 * 3 + 1 = 37
对于样例2: 能够获得最多积分的情况是 12 * 3 + 1 = 37, 12 + 20 = 32, 所以答案为 min(32, 37) = 32