1360 : 我是吃货

时间限制:1 Sec 内存限制:128 MiB
提交:174 答案正确:99

提交 状态 讨论区

题目描述

凡是了解小明的同学都知道小明其实是一个隐藏很深的吃货,这么说主要基于以下两点原因: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元。

输出

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

    具体输出见样例。

样例输入

复制
2
3 3
1 1
1 2
1.5 1
3 3
1 2
2 1
1 1

样例输出

复制
2.75
3.00

提示


			

来源