题目描述

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

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

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

严格的定义是，如果脸哥买了 $z[i_1],z[_i2],…,z[i_p]$这 $p$ 件装备，并且不存在实数 $b_1,b_2,…,b_p$ 使得$z[k]=b_1z[i_1]+b_2z[i_2]+…+b_pz[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≤n,m≤500$
• $0≤a_{i,j}≤1000$

来源

• JLOI2015
• BZOJ4004
• 算法竞赛进阶指南