물건 사기

바이테아사르는 바이토티아의 한 식당에서 구매 담당자로 일한다. 매일 저녁 그는 지배인에게서 장보기 목록을 받는다. 목록에 적힌 식재료는 다음 날 아침에 사야 하고, 각 식재료를 정확히 하나씩 사야 한다. 지배인은 총비용을 최대한 줄이라고 늘 재촉한다.

바이테아사르는 저녁마다 컴퓨터 앞에 앉아 지역 식자재 도매점마다 필요한 식재료의 가격을 확인한다. 식당에서 각 도매점까지 다녀오는 데 드는 비용도 알고 있다. 이제 어떤 식재료를 어느 도매점에서 살지 정해야 한다.

식재료를 사기로 한 도매점마다 그는 다음과 같이 움직인다. 식당에서 그 도매점으로 가서 장을 본 뒤 산 물건을 곧바로 식당으로 가져온다. 차의 트렁크가 충분히 커서 한 도매점에서 산 물건은 모두 한 번에 실어 올 수 있으므로, 같은 도매점을 두 번 이상 갈 필요는 없다. 식재료는 쉽게 상하기 때문에 한 번 나가서는 도매점 한 곳에서만 장을 볼 수 있다.

바이테아사르가 모든 식재료를 가장 싸게 사는 방법을 계산하는 프로그램을 작성하라.

첫째 줄에 도매점의 수 $n$과 사야 하는 식재료의 수 $m$이 주어진다. ($1 \le n \le 100$, $1 \le m \le 16$)

다음 $n$개 줄에는 도매점마다 가격 정보가 한 줄씩 주어진다. $i$번째 줄의 첫 수 $d_i$는 식당에서 $i$번째 도매점까지 다녀오는 비용이다. ($1 \le d_i \le 1\,000\,000$, 돌아오는 비용 포함) 그 뒤에 $m$개의 정수 $c_{i,1}, c_{i,2}, \dots, c_{i,m}$이 이어지며, $c_{i,j}$는 $i$번째 도매점에서 파는 $j$번째 식재료의 가격이다. ($1 \le c_{i,j} \le 1\,000\,000$)

가장 싼 구매 계획에서 식재료 가격의 합과 선택한 도매점을 다녀오는 비용의 합을 더한 값을 한 줄에 정수 하나로 출력한다.

예제에서 바이테아사르는 2번 식재료를 첫 번째 도매점에서 사고 나머지 식재료를 두 번째 도매점에서 산다. 그러면 세 번째 도매점에는 갈 필요가 없다.