33367번 - Poor Students 다국어

문제

End of semester is coming, and it is a hard time for students. There are $k$ courses and $n$ students, and every student should pick exactly one course and pass the exam on it.

If student $i$ picks exam $j,ドル the student's frustration will be $c_{i,j}$. The total frustration of students is the sum of their individual frustrations.

The teachers insist that, for each exam $j,ドル no more than $a_j$ students can pick this exam. What is the minimum possible total frustration the students may get?

입력

The first line contains two integers $n$ and $k$: the number of students and the number of exams (1ドル \le n \le 50,000円,ドル 1ドル \le k \le 10$).

Then follow $n$ lines. In $i$-th of these lines, there are $k$ integers $c_{i,1}, c_{i,2}, \ldots, c_{i,k}$: the frustration of student $i$ if they choose the exam 1,ドル 2, \ldots, k$ (1ドル \le c_{i,j} \le 10^9$).

The last line contains $k$ integers $a_1, a_2, \ldots, a_k$: the maximum number of students that can pick exam 1,ドル 2, \ldots, k$ (0ドル \le a_j \le n$). It is guaranteed that $\sum a_j \ge n$.

출력

Print one integer: the minimum possible total frustration.

제한

힌트