问题 F: 我是吃货

问题 F: 我是吃货

时间限制: 1 Sec  内存限制: 128 MB
提交: 262  解决: 130
[状态] [讨论版] [提交] [命题人:]
题目描述

凡是了解小明的同学都知道小明其实是一个隐藏很深的吃货,这么说主要基于以下两点原因:1、小明很贪吃。2、他不胖……
    小明有事儿没事儿就喜欢上淘宝上买一些零食,经验丰富。班上要举办新年茶话会了,理所当然要购买很多糖果了,而购买糖果的任务就非小明莫属了。巧克力当然是大家的最爱,就是太贵了,为了少花钱多办事,小明决定在淘宝上买一些散装(请注意,都是散装的)巧克力。
好了,问题出现了。小明可以支配的钱只有n元,网上特价区有m种不同的散装巧克力,每种最多有w公斤,每公斤价格为c元。现在小明想让你帮忙,购买尽可能多的零食。

输入

首先输入一个整数T,表示接下来有T(0<T<=20)个测试实例。
实例第一行包含两个整数n(0<n<=1000)和m(0<m<=100)。接下来m行,每行两个实数vi,ci。分别表示第i种巧克力最多有vi公斤,每公斤价格为ci元。

输出

输出小明最多能够购买的巧克力的数量。每个输出占一行。

样例输入 Copy
2
3 3
1 1
1 2
1.5 1
3 3
1 2
2 1
1 1
样例输出 Copy
2.75
3.00