2144. 抗震机械制造

单点时限: 2.0 sec

内存限制: 256 MB

为了应付可能到来的地震,ECNU 国国王 CS 决定花大量资金开发几种矿藏来制造各种救援机械。矿藏一旦被开发就可以无限使用。为了使自己的救援队能应付尽可能多的境况,CS 决定让自己的救援队的机械组成尽量多元化。CS 数学太弱,面对复杂的机械制造数据,他只好求助于你。

如果 CS 给你关于机械制造的具体数据,你能帮他计算出他最多能制造多少种救援机械吗?

输入格式

测试数据以一个整数 T(1<=T<=20) 开头,表示有 T 组测试数据。

每组测试数据都以三个整数 n(1<=n<=100),m(1<=m<=16),p(1<=p<=16000) 开始,n 表示可以制造的机械的种数,m 表示矿藏的种数,p 表示 CS 最多能花费的资金。

接下来一行有 m 个整数,第 i 个整数表示开发第 i 种矿藏需要的资金。

然后有 n 行,每行 m 个数(1 或 0),第 i 行第 j 个数为 “1” 表示制造第 i 种机械需要第 j 种矿藏,若为 “0” 则表示不需要。

输出格式

对于每组测试数据,输出 CS 最多能制造的机械的种数。

样例

Input
2
3 4 1719
409 626 785 108
0 0 0 0
1 0 1 1
1 0 0 0
3 4 1612
268 223 480 947
1 1 1 0
1 1 1 1
0 0 1 0
Output
3
2
Hint:
Case1:开发1,3,4号矿藏即可制造所有的机械,总开销为409+785+108=1302
Case2:开发1,2,3号矿藏即可制造第一种和第三种机械,总开销为268+223+480=971,因为制造第二种机械需要开发第四种矿藏,需要再花费947,超出上限,所以无法达到。

47 人解决,76 人已尝试。

83 份提交通过,共有 299 份提交。

4.7 EMB 奖励。

创建: 14 年,3 月前.

修改: 5 年,1 月前.

最后提交: 5 月,1 周前.

来源: 第一届程序设计竞赛

题目标签