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.