问题2479--皇城保卫战

2479: 皇城保卫战

时间限制: 5 Sec  内存限制: 256 MB
提交: 15  解决: 1
[提交] [状态] [讨论版] [命题人:]

题目描述



豺狼人大军还有t天就要来啦!
高地上有n个空地,每个空地最多修建100个防御塔, 精灵王国派遣了m个劳工前来帮助你修建防御塔。因为天气原因,每天都会有一些空地不适合施工,劳工们只能选择合适的空地修建防御塔。同时,劳工们精力有限,每名劳工一天只能在一个空地上修建一座防御塔。
当然,哪怕是一个战争小白都知道,不同地势的空地有不同的战略价值vi.假设在豺狼人到来的那一天,空地i的防御塔数量为xi, 这个空地的安防程度为:
pi = -vi  (xi * xi - 200xi)
那么整个高地的安防程度为:
Σi pi (i = 1... n)
高地安防程度最高为多少?


输入

包含多组数据,第一行一个整数T,表示T组数据。
每组数据的第一行1个整数t,剩余的天数。
第二行2个整数n,m,空地数和劳工数。
第三行n个整数v1, v2, ……, vn,每个空地的战略价值。
接下来t行,每行n个整数.第i行的第j个元素表示第i天能否修建第j个空地,1表示可以,0表示不能。
T ⩽ 10
1 ⩽ t ⩽ 50
1 ⩽ n,m ⩽ 50
1 ⩽ v ⩽ 100

输出

一个整数,最高的安防程度。

样例输入

1
2
3 5
12 21 3
0 0 1
1 0 1

样例输出

14625

提示

第一天5名劳工全在第3个空地修防御塔,第二天5名劳工全在第1个空地修防御塔。

来源/分类


[提交] [状态]