이 도시 저 도시를 여행하고 있다.

n 곳의 도시가 있고 여행자는 m 날 동안 여행한다. 여행자는 모든 도시를 방문할 필요는 없다. 즉 한 도시에서 m 날을 보낼수도 있다.

도시에서 도시로 이동하는 데 드는 비용이 주어지고 특정한 날 어떤 도시에 머무는 경우 예상 수익이 주어진다. 여행은 1 번 도시에서 시작한다.

가장 최대 수입을 올리기 위한 방법을 찾아서 최대 값을 출력하는 게 문제이다.

입력

다음 n 줄 당 n 개의 수가 입력된다. ( i , j ) 는 i 에서 j 도시로 이동하는데 드는 비용이다. i = j 이면 i 도시에 머무는데 드는 비용이다. 빈 줄이 하나 입력된 후에

m 줄에 n 개의 정수가 입력된다. ( i , j ) 는 i 번째 날에 도시 j 에 머무는 경우 수입이다. n ,m 은 100 이하이다.

출력

입출력 예

입력

3 3
3 1 2
2 3 1
1 3 2

2 4 3
4 3 2
3 4 2

출력

8

보충 설명

-1 + 4 - 2 + 4 - 1 + 4 = 8

출처:South Central China 2007 hosted by NUDT