题目描述

设某一机器由$\red{n}$个部件组成，每一种部件都可以从$\red{m}$个不同的供应商处购得。设$\red{w_{ij} }$是从供应商$\red{j }$处购得的部件$\red{i}$的重量，$\red{c_{ij} }$是相应的价格。试设计一个算法，给出总价格不超过$\red{c}$的最小重量机器设计。 编程任务：对于给定的机器部件重量和机器部件价格，编程计算总价格不超过$\red{d}$的最小重量机器设计。

输入格式

第一行有$\red{3}$个正整数$\red{n,m}$和$\red{d}$。接下来的$\red{2n}$行，每行$\red{n}$个数。前$\red{n}$行是$\red{c}$，后$\red{n}$行是$\red{w}$。$\red{（1<=n,m<=100）}$

输出格式

第一行输出最小重量。第二行输出每个部件的供应商。

样例

输入样例

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

输出样例

4
1 3 1