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

한국과학영재학교 학생들은 주말마다 배달 음식을 시켜 먹곤 한다. 그런데 요즘 배달비가 너무 비싸져서 같이 시키는 학생들이 점점 많아지고 있다.

총 $N$명의 학생들이 각자 $M$개의 가게 중 정확히 한 가게를 선택해서 주문하는데, 같은 가게를 선택한 학생들끼리는 함께 주문하면 배달비를 균등하게 나눠서 낼 수 있다. $j$번째 가게에서 음식을 주문한다면 총 $c_j$의 배달비가 발생하는데, 그 가게에서 주문한 학생들이 배달비를 균등하게 나눠서 내게 된다. 각자가 낼 배달비가 꼭 정수일 필요는 없다. $i$번째 학생은 $j$번째 가게에서 주문할 때 자신이 내야 할 배달비가 $r_{i,j}$ 이하일 때 $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$