题目描述

设某一机器由 n(n<=20)个部件组成，每一种部件都可以从m(m<=20)个不同的供应商处购得。设W[i][j]是从供应商j处购得的部件i的重量，C[i][j] 是相应的价格。

试设计一个算法，给出总价格不超过d的最小重量机器设计。

对于给定的机器部件重量和机器部件价格， 编程计算总价格不超过d(d<=160)的最小重量机器设计。

输入格式

第一行有3 个正整数n，m和d。

接下来的 2n 行，每行n个数。前n行是c，后n行是w。

输出格式

第一行输出计算出的最小重量

第二行输出每个部件的供应商，如果有多组答案，要求输出字典序最小的一种。

样例数据

input

3 3 4
1 2 3
3 2 1
2 2 2
1 2 3
3 2 1
2 2 2

output

4
1 3 1

数据规模与约定

时间限制：$1 \text {s}$

空间限制：$256 \text {MB}$