题目描述

你要购买$m$种物品各一件，一共有$n$家商店，你到第$i$家商店的路费为$d[i]$，在第$i$家商店购买第$j$种物品的费用为$c[i][j]$，求最小总费用。

输入格式

第一行包含两个正整数$n,m$ ($1 \leq n \leq 100, 1 \leq m \leq 16$)，表示商店数和物品数。接下来$n$行，每行第一个正整数$d[i]$ ($1 \leq d[i] \leq 1000000$) 表示到第$i$家商店的路费，接下来$m$个正整数，依次表示$c[i][j]$ ($1 \leq c[i][j] \leq 1000000$)。

输出格式

一个正整数，即最小总费用。

输入数据示例

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

输出数据示例

16

提示

在第一家店买2号物品，在第二家店买剩下的物品。