박물관의 긴 밤

오스트리아 빈은 도시 안에 100곳이 넘는 박물관이 있어 '문화의 도시'라 불린다. 박물관이 워낙 많아 아무리 오래 머물러도 모든 박물관을 둘러보기는 어렵고 비용도 많이 든다. 다행히 '박물관의 긴 밤(Long Night of Museums)'이라는 특별한 밤이 있어, 이 날에는 오후 6시부터 다음 날 새벽 1시까지 표 한 장으로 여러 박물관을 관람할 수 있다.

그렇지만 이 밤에도 도시의 모든 박물관을 관람할 수는 없다. 첫째, 일부 박물관은 오후 5시에 문을 닫아 이 행사에 참여하지 않는다. 둘째, 주어진 7시간 동안 모든 박물관으로 이동하고 각 박물관 내부를 남김없이 관람한 뒤 다음 박물관으로 이동하기에는 시간이 부족하다.

행사에 참여하는 박물관의 수, 각 박물관 내부를 관람하는 데 걸리는 시간, 그리고 한 박물관에서 다른 박물관으로 이동하는 데 걸리는 시간이 주어진다. '박물관의 긴 밤' 동안 관람할 수 있는 박물관의 수를 최대로 하는 관람 경로를 찾아, 관람할 수 있는 박물관의 최대 개수를 구하라.

관람은 어느 박물관에서 시작해도 좋으며(첫 박물관까지의 이동 시간은 들지 않는다), 서로 다른 박물관들을 차례로 한 번씩 방문하는 경로를 따른다. 사용할 수 있는 총 시간은 오후 6시부터 다음 날 새벽 1시까지, 즉 7시간(420분)이다. 선택한 경로에서 (방문한 각 박물관의 관람 시간의 합) + (연속한 두 박물관 사이의 이동 시간의 합)이 420분을 넘지 않아야 한다.

입력은 여러 개의 테스트 케이스로 이루어진다. 각 테스트 케이스의 첫 줄에는 행사에 참여하는 박물관의 수 $N$이 주어진다($1 \le N \le 20$). 각 박물관은 $1$번부터 $N$번까지의 고유한 번호를 가진다. 둘째 줄에는 $1$번부터 $N$번까지 각 박물관을 관람하는 데 걸리는 시간(분)을 나타내는 $N$개의 정수가 주어진다. 그 다음 $N$개의 줄이 이어지며, $i$번째 줄에는 $N$개의 정수 $M_{i,1}, M_{i,2}, \dots, M_{i,N}$이 주어진다. 여기서 $M_{i,k}$는 $i$번 박물관에서 $k$번 박물관으로 이동하는 데 걸리는 시간(분)이다. 각 줄의 $i$번째 정수, 즉 $M_{i,i}$는 항상 $0$이다. 입력의 끝은 $N = 0$으로 나타낸다.

각 테스트 케이스마다 '박물관의 긴 밤' 동안 관람할 수 있는 박물관의 최대 개수를 한 줄에 하나씩 출력한다.