배달비가 너무 비싸서 만든 문제

한국과학영재학교 학생들은 주말마다 배달 음식을 시켜 먹곤 한다. 요즘 배달비가 많이 올라서 함께 주문하는 학생들이 점점 늘고 있다.

총 $N$명의 학생이 각자 $M$개의 가게 중 정확히 한 가게를 골라 주문한다. 같은 가게를 고른 학생들은 함께 주문해서 배달비를 균등하게 나눠 낼 수 있다. $j$번째 가게에서 주문하면 배달비 $c_j$가 발생하고, 그 가게에서 주문한 학생들이 이 배달비를 균등하게 나눠 낸다. 각자 내는 배달비가 꼭 정수일 필요는 없다. $i$번째 학생은 $j$번째 가게에서 주문할 때 자신이 내야 할 배달비가 $r_{i,j}$ 이하이면 그 가게에서 음식을 주문할 수 있다.

도영이는 모든 학생이 내는 배달비의 총합이 최소가 되도록 각 학생이 주문할 가게를 정하려고 한다. 학생들이 내야 할 배달비 총합의 최솟값을 구하여라.

첫 번째 줄에 두 정수 $N$과 $M$이 공백으로 구분되어 주어진다.

두 번째 줄에 $M$개의 정수 $c_1, c_2, \cdots, c_M$이 공백으로 구분되어 주어진다.

다음 $N$개의 줄에 $r_{i,j}$가 주어지며, 그중 $i$번째 줄에 $M$개의 정수 $r_{i,1}, r_{i,2}, \cdots, r_{i,M}$이 공백으로 구분되어 주어진다.

배달비 총합의 최솟값을 출력한다. 모든 학생이 빠짐없이 배달 음식을 주문하는 것이 불가능하다면 대신 -1을 출력한다.

• $1 \leq N \leq 15$
• $1 \leq M \leq 1000$
• $1 \leq c_j \leq 10^7$
• $0 \leq r_{i,j} \leq 10^7$