题目描述

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

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

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

严格的定义是，如果脸哥买了 $z[i_1],z[i_2],...,z[i_p]$ 这 $p$ 件装备，并且不存在实数 $b_1,b_2,...,b_p$ 使得 $z[k]=b_1 z[i_1]+b_2 z[i_2]+...+b_p z[i_p]$，那么脸哥就会买 $z[k]$，否则 $z[k]$ 对脸哥就是无用的了，自然不必购买。

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

输入格式

第一行包含两个整数 $n$ 和 $m$。

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

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

输出格式

输出占一行，包含两个整数，第一个整数表示能够购买的最多装备数量，第二个整数表示在购买最多数量的装备的情况下的最小花费。

样例

输入样例：

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

输出样例：

2 2

样例解释

三件装备的属性向量：

1. (1,2,3) 花费 1
2. (3,4,5) 花费 1
3. (2,3,4) 花费 2

可以验证，第 3 个装备可以由前两个装备线性表示：
(2,3,4) = (1,2,3) + (1,1,1)
但 (1,1,1) 并不是第 2 个装备，实际上 (2,3,4) = 1×(1,2,3) + 1×(1,1,1)，而 (1,1,1) 无法由前两个装备表示，所以这个例子可能不太直观。

更准确地说，向量空间维度 $m=3$，最多能选出 3 个线性无关的向量。
但这里三件装备可能线性相关。
经过计算，最多可以买 2 件装备（线性无关），并且在所有选 2 件装备的方案中，最小总花费为 2（例如选第 1 和第 2 件，花费 1+1=2）。

数据范围

• $1 \le n, m \le 500$
• $0 \le a_{i,j} \le 1000$

时空限制

• 时间限制：1 秒
• 空间限制：64 MB