进入JSOI总部大楼时必须乘坐的电梯,承载量为W公斤。由于这是一个带有一定机密任务的机关,所以在乘坐电梯时,每个人均必须使用总部配发的IC卡由设在电梯门口的智能系统读入识别后才能进入。此卡储存的是持卡人的相关信息(如:姓名、性别、年龄、体重、特征等)。当电梯即将开动时,电梯中的智能系统会对已在电梯中的n个人的总重量进行判断,若大于W公斤将不能启动并立即用铃声报警。此时,电梯中显然必须下去一些人。
由于每次均可能涉及到下去人的问题,在此大楼的一些年青人就开玩笑起来。大家商定,每次均要保证下去人的方案最优。所谓最优是指:剩余人的重量之和0<=W＜＝10000,同时下去人的年龄之和为最小。
例如:当W,n=200,4时:
每人体重分别为:65,50,85,55
每人年龄分别为:46,18,70,21
由于65+50+85+55=255>W,所以必须下去人：
下去第一个人 剩余重量190 下去年龄46
下去第二个人 剩余重量205 下去年龄18
下去第三个人 剩余重量170 下去年龄70
下去第四个人 剩余重量200 下去年龄21
下去第一、二个人 剩余重量140 下去年龄64
…………
最佳方案:下去第4个人,下去年龄为21
输入:输入文件的第一行为二个整数W,n(l<=n<=22):
接下来的二行,每行均有n个整数(用空格分隔,第一行表示每个人的体重,第二行表示每个人的年龄)。
输出:输出文件仅一行包含一个整数(表示下去的人的年龄之和〉。
200 4
65 50 85 55
46 18 70 21
21