주차 빌딩

시간 제한1초메모리 제한128 MB

요약

엘리베이터와 회전하는 컨베이어 벨트를 시뮬레이션해서 고객 순서대로 차를 찾는 데 걸리는 총 시간을 구합니다.

난이도: 보통10점 중 4점
유형: 시뮬레이션, 구현, 수학
정답자: 아직 제출이 없습니다

문제

주차 빌딩의 작동 원리는 간단하다. 운전자는 주차 타워 입구의 엘리베이터에 차를 세우고 내린다. 그러면 엘리베이터와 컨베이어 벨트가 빈 주차 공간을 찾아 차를 그곳으로 옮긴다. 운전자가 다시 찾으러 올 때까지 차는 그 자리에 머무른다. 운전자가 오면 엘리베이터와 컨베이어 벨트가 그 차를 찾아 입구로 되돌려 준다.

빌딩의 구조도 간단하다. 건물 중앙에는 엘리베이터가 있어 차는 이 엘리베이터로 층 사이를 오르내린다. 각 층에는 커다란 원형 컨베이어 벨트가 하나 있고, 차들은 이 벨트 위에 놓여 있다. 벨트는 시계 방향으로도, 반시계 방향으로도 돌 수 있다. 엘리베이터가 어떤 층에 도착하면 그 층 벨트의 한 칸이 되어, 차가 엘리베이터가 있는 칸을 지나 이동할 수 있다.

하루가 끝날 무렵이면 많은 사람이 차를 찾으러 온다. 손님들은 도착한 순서대로 차를 찾아간다. 엘리베이터는 차가 있는 층으로 올라가고, 벨트가 그 차를 엘리베이터 칸까지 옮겨 실은 뒤, 엘리베이터가 1층으로 내려와 손님에게 차를 건네준다. 모든 손님이 자신의 차를 찾는 데 걸리는 전체 시간을 구하는 프로그램을 작성하시오. 엘리베이터가 한 층을 오르내리는 데는 10초가 걸리고, 벨트가 차 한 칸만큼 시계 방향 또는 반시계 방향으로 도는 데는 5초가 걸린다.

입력

첫째 줄에 테스트 케이스의 개수가 주어진다. 테스트 케이스는 최대 100개이다. 각 테스트 케이스의 첫째 줄에는 주차 빌딩의 높이 $h$ 와 컨베이어 벨트의 길이 $l$ 이 주어진다 ( $1 \le h \le 50$ , $2 \le l \le 50$ ). 이어지는 $h$ 개의 줄에는 각각 $l$ 개의 정수가 주어지며, 이는 주차 빌딩에 들어 있는 차의 정보이다. $i$ 번째 줄의 $j$ 번째 수는 $i$ 번 층 $j$ 번 위치에 있는 차를 나타낸다. 값이 $-1$ 이면 그 칸은 비어 있고, 그 밖의 값 $r$ 이면 $r$ 번째 손님이 찾아가는 차라는 뜻이다. 손님은 1층에서 차를 건네받으며, 엘리베이터는 처음에 1층의 첫 번째 위치에 있고 비어 있다. 입력은 참조되는 차가 모두 실제로 존재하는 경우만 주어진다.

출력

각 테스트 케이스마다 모든 손님이 차를 찾는 데 걸리는 전체 시간을 한 줄에 출력한다.

예제7

예제 1

입력

2
1 5
-1 2 1 -1 3
3 6
-1 5 6 -1 -1 3
-1 -1 7 -1 2 9
-1 10 4 1 8 -1

예상 출력

25
320

예제 2
입력
```
1
1 2
-1 1
```
예상 출력
```
5
```
예제 3
입력
```
1
1 2
1 -1
```
예상 출력
```
0
```
예제 4
입력
```
1
3 3
-1 -1 3
-1 2 -1
1 -1 -1
```
예상 출력
```
70
```
예제 5
입력
```
1
1 4
-1 -1 1 -1
```
예상 출력
```
10
```
예제 6
입력
```
2
1 2
-1 1
1 2
1 -1
```
예상 출력
```
5
0
```
예제 7
입력
```
1
1 6
3 1 2 -1 -1 -1
```
예상 출력
```
20
```