Based 죽

컴퓨터 과학을 공부하는 학생들은 유치원생들과 마찬가지로 공정한 결과에 매우 신경 쓴다. 이것이 낮은 쪽을 도와서 이루어지는지, 높은 쪽을 억눌러서 이루어지는지는 상관없다. 여러분은 Basen에서 $N$명의 학생을 위한 시트닝을 주최하고 있다. 죽은 K종류가 있으며, $i$번째 종류의 식사를 $a_i$개 준비했다. 물론 모두가 죽을 좋아한다. 하지만 어떤 학생들은 특정 종류를 다른 종류보다 더 선호한다. 실제로 학생 $i$은 $j$번째 종류의 죽을 먹으면 $h_{ij}$의 행복을 얻는다. 좋은 주최자가 되면서 공정성을 최대화하기 위해, 모든 사람에게 식사를 하나씩 제공하되 가장 만족한 학생과 가장 덜 만족한 학생 사이의 행복 차이를 최소화하려 한다. 가능한 차이의 최솟값은 얼마인가?

채점

여러분의 해답은 각각 일정한 점수가 배정된 테스트 그룹들로 평가된다. 한 테스트 그룹의 점수를 얻으려면 그 테스트 그룹에 속한 모든 테스트 케이스를 해결해야 한다. 최종 점수는 단일 제출에서 얻은 점수 중 최댓값이다.

그룹 | 점수 | 제한 조건

$1$ |$50$| $K = 2$

$2$ |$50$| 추가 제한 조건 없음

첫째 줄에 학생 수와 죽 종류의 수를 나타내는 두 정수 $N$와 $K$가 주어진다 ($2 \le K \le N \le 75$). 둘째 줄에는 $K$개의 정수 $a_i$가 주어지며 ($1\le a_i\le N$, $\sum a_i = N$), 이는 $i$번째 종류의 죽으로 제공할 수 있는 식사의 수이다. 마지막으로 $N$개의 줄이 주어지며, 각 줄에는 $K$개의 정수 $h_{ij}$가 주어진다 ($1\le h_{ij}\le 10^9$). 이는 사람 $i$이 $j$번째 종류의 죽에서 얻는 행복이다.

가장 만족한 학생과 가장 덜 만족한 학생 사이에서 가능한 행복 차이의 최솟값을 출력한다.