基于目前游客的需求,许多导游经常带他们去购买一些旅游纪念品以介绍本土文化和历史遗迹.一些旅游纪念品商店会给带游客来采购的导游一些佣金以便他们会带更多旅客来光顾.佣金的数额将取决于商品的价值.为了使导游了解每样商品为他们带来的报酬,这些商店一般上都会列出每样物品的价值以及可获得的佣金.
假设一位导游知道每个游客打算花费的数额以及对他的信任,那么只要不超出本身的预算,游客就会购买所有经过导游推介的商品.在前往商店前,导游会开始计算应该推介哪个商品给哪位游客以便他能获得最多的佣金.不幸的是,对他而言这是一个困难的问题因为他从来未成功计算.
幸运的是,这位导游遇见了精通于规划的你,所以他希望你能帮忙规划使这项任务完成.假设商店里的每样商品都有足够的数量以满足所有游客的购物需求.
载入的文件包含多个测试案例.每个案例的第一行包含一个正整数,n以代表打算购买纪念品的游客数量.第二行包括多个整数n表示每个游客的最大的预算（正整数,小于2000）.在以下行列有一个正整数m（m