Byteasar 是 Byteotian 一家餐厅的采购经理。每天晚上，他都会收到经理开出的购物清单。食品必须在第二天早上采购。Byteasar 需要从清单中为每种产品各购买一件。经理总是要求总成本尽可能低。

Byteasar 晚上坐在电脑前，查看当地食品批发商处所有所需产品的价格。他还知道从餐厅到每个批发商处往返的交通费用。现在，Byteasar 必须决定在每个批发商处购买哪些产品。

对于 Byteasar 决定购买产品的每个批发商，他会执行以下操作：他会从餐厅前往批发商处，进行采购，并立即将购买的产品带回餐厅。幸运的是，他的汽车后备箱足够大，无需多次访问任何批发商，因为所有购买的商品都可以一次性运回。食品极易腐烂，因此在一次行程中，Byteasar 只能在一个批发商处进行采购。

编写一个程序，帮助 Byteasar 计算完成所有采购的最便宜方式。

输入格式

输入的第一行包含两个整数 $n$ 和 $m$ ($1 \le n \le 100, 1 \le m \le 16$)，分别表示批发商的数量和 Byteasar 需要购买的产品数量。接下来的 $n$ 行包含各批发商的价格描述。

这些行中第 $i$ 行的第一个数字 $d_i$ ($1 \le d_i \le 1\,000\,000$) 描述了从餐厅到第 $i$ 个批发商的往返交通费用。随后是 $m$ 个整数 $c_{i,1}, c_{i,2}, \dots, c_{i,m}$ ($1 \le c_{i,j} \le 1\,000\,000$)：数字 $c_{i,j}$ 表示第 $i$ 个批发商处第 $j$ 种产品的价格。

输出格式

程序应输出一行，包含一个整数，表示在最便宜的采购计划中，Byteasar 所选产品的价格总和与前往批发商的交通费用之和。

样例

输入 1

3 4
5 7 3 7 9
2 1 20 3 2
8 1 20 1 1

输出 1

16

说明

Byteasar 在第一个批发商处购买了第 2 号产品，在第二个批发商处购买了所有其他产品。因此，他不必访问第三个批发商。