题目

英语翻译
Currently for the requirement of the sightseers,many cicerones often take them to shopping for some souvenirs in addition to the introduction of the local culture and historic sites.Some souvenir shops give the cicerones who bring sightseers some kickbacks in order to make them bring more.The amount of the kickback is determined by the value of the goods.The shops usually list the values of the goods and the relevant kickbacks for the cicerones to make them clear of the reward they can earn from each kind of goods.
Assume the cicerone has known the maximum amount of money every sightseer intends to spend and the trust of the sightseers on him.The sightseers will buy all souvenirs in any quantity recommended by the cicerone only if their maximum budgets are kept.Before going to the shop,the cicerone starts calculating which goods he should recommend to which sightseer so as to make himself obtain the maximum kickbacks.Unfortunately,this is such a hard problem for him that h

提问时间：2020-11-08

答案

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