题目描述

小明的班级要集体包场看电影，他了解到有 \(m\) 家电影院放映这部影片，每家电影院提供的团购方案不一致，第 \(i\) 家电影院的购票方案是买 \(a_i\) 张票，需要 \(b_i\) 元。明明全班有 \(n\) 名同学，编程帮助他求出最优的购票方案。注意，全班同学要在同一家电影院观看电影。

注意：可以买多的票，但必须保证最优（可参见样例）。

格式

输入格式

第一行为正整数 \(t(≤10)\)，表示数据组数；每组数据中，第一行为正整数 \(n(≤ 1000)\) 和 \(m(≤100)\)，接下来 \(m\) 行，每行两个正整数 \(a_i\) 和 \(b_i(a_i,b_i≤1000)\)，数据意义如上所述。

输出格式

对于每组数据，输出最佳（最少）的花费。

样例1

输入样例1

1
3 2
2 20
3 50

输出样例1

40

来源

地址：芜湖市二十七中电脑班刷题课
作者：汪老师
模拟赛\(T1\)

文件IO

freopen("movies.in","r",stdin);
freopen("movies.out","w",stdout);