음식 축제

도시 CZ는 전국에서 온 학생들을 맞이하려고 큰 음식 축제를 연다. 음식을 좋아하는 작은 M은 새로운 맛을 하나도 놓치고 싶지 않다. 그는 다른 사람의 식탁에 이미 올라간 요리를 기다리는 학생이 없기를 바라며, 학생들의 대기 시간을 최소로 줄이는 조리 순서를 연구한다.

축제에는 $n$가지 음식이 있다. 각 학생은 주문할 때 이 중 하나를 고른다. 요리사는 $m$명이다. 모든 학생의 주문이 끝나면 요리사마다 조리할 음식의 순서가 배정된다. 그 다음 모든 요리사가 동시에 조리를 시작한다. 각 요리사는 배정된 순서대로 조리하며, 한 번에 한 사람분만 만들 수 있다.

요리사마다 같은 음식을 만드는 데 걸리는 시간이 다르다. 요리사 $j$가 음식 $i$를 만드는 데 걸리는 시간을 $t_{i,j}$라고 한다. 음식은 1번부터 $n$번까지, 요리사는 1번부터 $m$번까지 번호가 매겨져 있다.

학생의 대기 시간은 모든 요리사가 조리를 시작한 시점부터 그 학생의 음식이 완성될 때까지 걸린 시간이다. 어떤 요리사가 $k$번째로 만드는 음식이 학생의 음식이라면, 대기 시간은 그 요리사가 만드는 처음 $k$개 음식의 조리 시간을 더한 값이다. 전체 대기 시간은 모든 학생의 대기 시간을 더한 값이다.

음식 $i$를 주문한 학생은 정확히 $p_i$명이다. 가능한 전체 대기 시간의 최솟값을 구하라.

첫 줄에 양의 정수 $n$과 $m$이 주어진다.

둘째 줄에 양의 정수 $p_1, p_2, \ldots, p_n$이 $n$개 주어진다. $p_i$는 음식 $i$를 주문한 학생 수이다.

이후 $n$개의 줄에 각각 0 이상의 정수 $m$개가 주어진다. $i$번째 줄의 $j$번째 정수가 $t_{i,j}$이다. 같은 줄의 인접한 수는 공백 하나로 구분되며, 줄 끝에는 공백이 없다.

가능한 전체 대기 시간의 최솟값을 한 줄에 출력한다.

$n \le 40$, $m \le 100$, $p \le 800$, $t_{i,j} \le 1000$. 여기서 $p = \sum p_i$이며, 주문한 전체 학생 수이다.