题号：NC19821
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld
题目描述
终于活成了自己讨厌的样子。
充钱能让你变得更强。
在暖婊这个游戏里面，如果你充了x元钱，那么你能获得10x个钻石。同时暖婊也有m档VIP，如果你往暖婊里面充了ai个钻石，那么你能成为第i档贵族用户。当你成为第i档贵族用户之后，那么你可以获得
的优惠。
你需要k件材料合成衣服，其中第i件材料原价为di个钻石，你一共需要ci件这种材料。当你获得p的优惠时，这个材料的真实价格为%5Crceil)
。
请问栗子米最少需要氪多少钱，这里我们规定只能氪整数的钱。
充钱能让你变得更强。
在暖婊这个游戏里面，如果你充了x元钱，那么你能获得10x个钻石。同时暖婊也有m档VIP，如果你往暖婊里面充了ai个钻石，那么你能成为第i档贵族用户。当你成为第i档贵族用户之后，那么你可以获得
你需要k件材料合成衣服，其中第i件材料原价为di个钻石，你一共需要ci件这种材料。当你获得p的优惠时，这个材料的真实价格为
请问栗子米最少需要氪多少钱，这里我们规定只能氪整数的钱。
输入描述:
第一行一个整数T(T≤ 1000)，表示数据组数。
每组数据第一行两个整数m,k(1≤ m,k≤ 15)。
接下来m行每行两个正整数1≤ ai≤ 105, 1≤ pi≤ 100，保证aii+1,pi≤ pi+1。
接下来k行每行两个正整数1≤ ci, di≤ 1000。
输出描述:
对于每组数据，输出一个整数，表示至少要氪多少钱。