2786. [JLOI 2015] 装备购买

【题目描述】

脸哥最近在玩一款神奇的游戏，这个游戏里有 $n$ 件装备，每件装备有 $m $个属性，用向量$z[i]=(a_1,a_2,\cdots,a_m) $表示 $(1 \leq i\leq n)$，每个装备需要花费 $c_i$。

现在脸哥想买一些装备，但是脸哥很穷，所以总是盘算着怎样才能花尽量少的钱买尽量多的装备。

对于脸哥来说，如果一件装备的属性能用购买的其他装备组合出（也就是说脸哥可以利用手上的这些装备组合出这件装备的效果），那么这件装备就没有买的必要了。

严格的定义是，如果脸哥买了$ z[i_1],z[i_2],\cdots,z[i_p]$这 $p $件装备，那么对于任意待决定的$ z[k]$，不存在 $b_1,b_2,\cdots,b_p$ 使得$z[k]=b_1z[i_1]+b_2z[i_2]+\cdots+b_pz[i_p]$，那么脸哥就会买 $z[k]$，否则 $z[k]$对脸哥就是无用的了，自然不必购买。

举个例子,$z[1] =(1; 2; 3);z[2]=(3; 4; 5);z[k] =(2; 3; 4)，b_1 =1/2，b_2 =1/2，$就有 $z[k]=b_1z[1] + b_2z[2]$，如果脸哥买了$ z[1] $和 $z[2]$ 就不会再买$ z[k] $了。

脸哥想要在买下最多数量的装备的情况下花最少的钱，你能帮他算一下吗？

【输入格式】

第一行两个数 $n,m$。

接下来 $n$ 行，每行 $m $个数，其中第 $i $行描述装备$ i $的各项属性值。

接下来一行 $n $个数，其中 $c_i$ 表示购买第$ i $件装备的花费。

【输出格式】

一行两个数，第一个数表示能够购买的最多装备数量，第二个数表示在购买最多数量的装备的情况下的最小花费

【样例输入】

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

【样例输出】

2 2

【提示】

如题目中描述，选择装备 1 装备 2，装备 1 装备 3，装备 2 装备 3 均可，但选择装备 1 和装备 2 的花费最小，为 2。

对于 100% 的数据, $1 <= n,m <= 500; 0 <= a_j <= 1000。$

【来源】

【JLOI 2015】