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

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