#P18399. Poor Students

Poor Students

Poor Students

学期末到了,学生们的日子很不好过。有 kk 门课程和 nn 名学生,每名学生必须恰好选择一门课程并参加该课程的考试。

如果学生 ii 选择考试 jj,他的挫败感为 ci,jc_{i,j}。所有学生的总挫败感是每人的挫败感之和。

老师要求,对每场考试 jj,选择它的学生人数不能超过 aja_j。求所有学生能够达到的最小总挫败感。

输入格式

第一行包含两个整数 n,kn,k,分别表示学生人数和考试数量:

1≤n≤50000,1≤k≤10.1\le n\le50000,\qquad1\le k\le10.

接下来 nn 行,第 ii 行包含 kk 个整数 ci,1,ci,2,…,ci,kc_{i,1},c_{i,2},\ldots,c_{i,k},表示学生 ii 选择各场考试时的挫败感,1≤ci,j≤1091\le c_{i,j}\le10^9。

最后一行包含 kk 个整数 a1,a2,…,aka_1,a_2,\ldots,a_k,表示每场考试允许的最多人数,0≤aj≤n0\le a_j\le n。

保证 ∑j=1kaj≥n\sum_{j=1}^k a_j\ge n。

输出格式

输出一个整数,表示最小总挫败感。

原样例 1

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

原样例 2

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