文理学院程序设计在线练习


最小重量机器设计问题

Time Limit: 1 Second(s)    Memory Limit: 32 MB

Total Submission(s): 326   Accepted Submission(s): 102
Problem Description

设某一机器由n个部件组成,每一种部件都可以从m个不同的供应商处购得。设wij是从供应商j处购得的部件i的重量,cij是相应的价格。试设计一个算法,给出总价格不超过cost的最小重量机器设计。

Input

每组测试数据第一行有3 个正整数n,m和cost。接下来的2n行,每行m个数。前n行是cij,后n行是wij。(1<=n,m<=20; 1<=cij <=100; 1<=wij<=100, 1<=cost<=40000)

Output

分2行输出最小重量,以及每个部件的供应商(若存在多个符合条件的供应商,则优先考虑编号小的)。若找不到解决方案,则输出-1。

Sample Input
3 3 4
1 2 3
3 2 1
2 2 2
1 2 3
3 2 1
2 2 2
Sample Output
4
1 3 1