学期末临近，学生们正处于一段艰难的时期。共有 $k$ 门课程和 $n$ 名学生，每名学生必须恰好选择一门课程并通过该门考试。

如果学生 $i$ 选择考试 $j$，该学生的挫败感为 $c_{i,j}$。所有学生的总挫败感为他们个人挫败感之和。

老师们要求，对于每门考试 $j$，选择该门考试的学生人数不得超过 $a_j$。学生们可能获得的最小总挫败感是多少？

输入格式

第一行包含两个整数 $n$ 和 $k$：学生人数和考试门数（$1 \le n \le 50\,000$，$1 \le k \le 10$）。

接下来 $n$ 行。第 $i$ 行包含 $k$ 个整数 $c_{i,1}, c_{i,2}, \dots, c_{i,k}$：学生 $i$ 选择考试 $1, 2, \dots, k$ 时的挫败感（$1 \le c_{i,j} \le 10^9$）。

最后一行包含 $k$ 个整数 $a_1, a_2, \dots, a_k$：可以选择考试 $1, 2, \dots, k$ 的最大学生人数（$0 \le a_j \le n$）。保证 $\sum a_j \ge n$。

输出格式

输出一个整数：最小可能的总挫败感。

样例

样例输入 1

6 2
1 2
1 3
1 4
1 5
1 6
1 7
3 4

样例输出 1

12

样例输入 2

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

样例输出 2

8