问题 4306 --(2007女生赛) 南瓜大选购

4306: (2007女生赛) 南瓜大选购

时间限制: 1 Sec  内存限制: 256 MB
提交: 2  解决: 0
[提交][状态][讨论版][命题人:]

题目描述

万圣节是西方传统的“鬼节”, 而万圣节最广为人知的形象就是南瓜,尤其在万圣节的重头戏——餐桌上,南瓜更能很好地把装饰和美味结合来。   

迎迎是个烹饪专家,无论中国菜,日本菜甚至于法国菜都难不到他。万圣节这天,他就要为一大帮好友们烹饪一顿丰盛的万圣节晚宴。迎迎为好友们制好定了菜谱后,就赶去超级市场选购南瓜和其它晚宴的食物。   

除了是一位“名厨”以外,迎迎也是个精明的消费者。他会根据好友们的数量,定制好每种食物购买的分量,使得不至于浪费金钱和食物。现在,他已经计划好了要买一个多重的南瓜。但是在超级市场里,这一天摆放了太多太多的南瓜了,迎迎对于挑选他心目中重量的南瓜感到很困惑。他需要在不大于他计划重量的南瓜里面,挑选一个最接近要求的南瓜。   

你能帮一帮他吗?

输入

输入有多组数据。输入的第一行输入一整数N,表示有多少组数据。  

接下来输入N组数据,每组数据的第一行输入两个正整数w和m,w表示迎迎想购买多重的南瓜,m( 1<=m<=1000 )表示超市里一共摆放了多少南瓜。接下来m行,每行输入两个整数ID i ,W i,分别表示每个南瓜的ID号,重量。所有南瓜的重量两两不相同,保证不会出现有多解的情况。

输出

每组数据输出一行,一行包含一个整数,为最适合的南瓜的ID号。

样例输入

1<br/>50  5<br/>4  34<br/>5  12<br/>1  45<br/>3  52<br/>2  40<br/>

样例输出

1

来源

[提交][状态]