시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 859 89 54 17.143%

문제

상근이는 데이트 비용을 마련하기 위해 빠름택배에서 택배를 배달하는 직업을 가졌다.

매일 빠름택배에 출근하면, 상근이는 그날 배달해야 하는 위치가 적힌 종이를 받는다. 또, 이 위치에 적혀져있는 순서대로 배달해야 한다.

도시는 R*C칸으로 나누어져 있다. 각 행은 1번부터 R번까지 번호가 매겨져 있고, 열도 1번부터 C번까지 번호가 매겨져 있다.

상근이는 각 칸에서, 왼쪽 또는 오른쪽으로 이동할 수 있다. 하지만, 위나 아래로 이동하려면 꼭 첫 번째나 마지막 열(1과 C)로 가야 한다.

빠름택배는 가장 왼쪽 위 칸인 (1,1)에 있다. 이곳이 상근이가 배달을 시작하는 곳이다. 상근이는 출발할 때 모든 물품을 들고 출발하고, 자신의 오토바이를 이용하여 배달하기 때문에, 배달하는 중 또는 배달을 마치고 다시 빠름택배로 돌아오지 않는다.

각 칸을 통과하는데 드는 시간이 주어진다. 이때, 모든 택배를 배달하는데 걸리는 최소 시간을 계산하는 프로그램을 작성하시오.

입력

첫째 줄에 도시의 크기 R과 C가 주어진다. (1 ≤ R ≤ 2000, 1 ≤ C ≤ 200)

다음 R개 줄에는, 각 칸을 통과하는데 드는 시간이 주어진다. 이 시간은 0보다 크거나 같고, 5000보다 작거나 같은 자연수이다.

다음 줄에는 배달해야 하는 물품의 수 D (1 ≤ D ≤ 200000)가 주어진다. 다음 D개 줄에는 물품을 배달해야 하는 곳의 위치의 좌표가 배달해야 하는 순서대로 주어진다. 같은 곳이 여러 번 주어질 수는 있다. 하지만, 연속해서 같은 곳을 배달해야 하는 경우는 없다. 

출력

모든 택배를 배달하는데 가장 빠른 시간을 출력한다.

예제 입력 1

3 3
1 8 2
2 3 2
1 0 1
3
1 3
3 3
2 2

예제 출력 1

17

힌트

예제의 경우에는 아래와 같이 이동하면 된다.

(1, 1), (2, 1), (3, 1), (3, 2), (3, 3), (2, 3), (1, 3), (2, 3), (3, 3), (2, 3), (2, 2)

총 배달 시간은 1+2+1+0+1+2+2+2+1+2+3=17가 된다.

W3sicHJvYmxlbV9pZCI6IjI5MzkiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWQwZGRcdWJjMzAgXHViYzMwXHViMmVjIiwiZGVzY3JpcHRpb24iOiI8cD5cdWMwYzFcdWFkZmNcdWM3NzRcdWIyOTQgXHViMzcwXHVjNzc0XHVkMmI4IFx1YmU0NFx1YzZhOVx1Yzc0NCBcdWI5YzhcdWI4MjhcdWQ1NThcdWFlMzAgXHVjNzA0XHVkNTc0IFx1YmU2MFx1Yjk4NFx1ZDBkZFx1YmMzMFx1YzVkMFx1YzExYyBcdWQwZGRcdWJjMzBcdWI5N2MgXHViYzMwXHViMmVjXHVkNTU4XHViMjk0IFx1YzljMVx1YzVjNVx1Yzc0NCBcdWFjMDBcdWM4NGNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YjllNFx1Yzc3YyBcdWJlNjBcdWI5ODRcdWQwZGRcdWJjMzBcdWM1ZDAgXHVjZDljXHVhZGZjXHVkNTU4XHViYTc0LCBcdWMwYzFcdWFkZmNcdWM3NzRcdWIyOTQgXHVhZGY4XHViMGEwIFx1YmMzMFx1YjJlY1x1ZDU3NFx1YzU3YyBcdWQ1NThcdWIyOTQgXHVjNzA0XHVjZTU4XHVhYzAwIFx1YzgwMVx1ZDc4YyBcdWM4ODVcdWM3NzRcdWI5N2MgXHViYzFiXHViMjk0XHViMmU0LiBcdWI2MTAsIFx1Yzc3NCBcdWM3MDRcdWNlNThcdWM1ZDAgXHVjODAxXHVkNjAwXHVjODM4XHVjNzg4XHViMjk0IFx1YzIxY1x1YzExY1x1YjMwMFx1Yjg1YyBcdWJjMzBcdWIyZWNcdWQ1NzRcdWM1N2MgXHVkNTVjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWIzYzRcdWMyZGNcdWIyOTQgUipDXHVjZTc4XHVjNzNjXHViODVjIFx1YjA5OFx1YjIwNFx1YzViNFx1YzgzOCBcdWM3ODhcdWIyZTQuIFx1YWMwMSBcdWQ1ODlcdWM3NDAgMVx1YmM4OFx1YmQ4MFx1ZDEzMCBSXHViYzg4XHVhZTRjXHVjOWMwIFx1YmM4OFx1ZDYzOFx1YWMwMCBcdWI5ZTRcdWFjYThcdWM4MzggXHVjNzg4XHVhY2UwLCBcdWM1ZjRcdWIzYzQgMVx1YmM4OFx1YmQ4MFx1ZDEzMCBDXHViYzg4XHVhZTRjXHVjOWMwIFx1YmM4OFx1ZDYzOFx1YWMwMCBcdWI5ZTRcdWFjYThcdWM4MzggXHVjNzg4XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWMwYzFcdWFkZmNcdWM3NzRcdWIyOTQgXHVhYzAxIFx1Y2U3OFx1YzVkMFx1YzExYywgXHVjNjdjXHVjYWJkIFx1YjYxMFx1YjI5NCBcdWM2MjRcdWI5NzhcdWNhYmRcdWM3M2NcdWI4NWMgXHVjNzc0XHViM2Q5XHVkNTYwIFx1YzIxOCBcdWM3ODhcdWIyZTQuIFx1ZDU1OFx1YzljMFx1YjljYywgXHVjNzA0XHViMDk4IFx1YzU0NFx1Yjc5OFx1Yjg1YyBcdWM3NzRcdWIzZDlcdWQ1NThcdWI4MjRcdWJhNzQgXHVhZjJkIFx1Y2NhYiBcdWJjODhcdWM5ZjhcdWIwOTggXHViOWM4XHVjOWMwXHViOWM5IFx1YzVmNCgxXHVhY2ZjIEMpXHViODVjIFx1YWMwMFx1YzU3YyBcdWQ1NWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YmU2MFx1Yjk4NFx1ZDBkZFx1YmMzMFx1YjI5NCBcdWFjMDBcdWM3YTUgXHVjNjdjXHVjYWJkIFx1YzcwNCBcdWNlNzhcdWM3NzggKDEsMSlcdWM1ZDAgXHVjNzg4XHViMmU0LiBcdWM3NzRcdWFjZjNcdWM3NzQgXHVjMGMxXHVhZGZjXHVjNzc0XHVhYzAwIFx1YmMzMFx1YjJlY1x1Yzc0NCBcdWMyZGNcdWM3OTFcdWQ1NThcdWIyOTQgXHVhY2YzXHVjNzc0XHViMmU0LiBcdWMwYzFcdWFkZmNcdWM3NzRcdWIyOTQgXHVjZDljXHViYzFjXHVkNTYwIFx1YjU0YyBcdWJhYThcdWI0ZTAgXHViYjNjXHVkNDg4XHVjNzQ0IFx1YjRlNFx1YWNlMCBcdWNkOWNcdWJjMWNcdWQ1NThcdWFjZTAsIFx1Yzc5MFx1YzJlMFx1Yzc1OCBcdWM2MjRcdWQxYTBcdWJjMTRcdWM3NzRcdWI5N2MgXHVjNzc0XHVjNmE5XHVkNTU4XHVjNWVjIFx1YmMzMFx1YjJlY1x1ZDU1OFx1YWUzMCBcdWI1NGNcdWJiMzhcdWM1ZDAsIFx1YmMzMFx1YjJlY1x1ZDU1OFx1YjI5NCBcdWM5MTEgXHViNjEwXHViMjk0IFx1YmMzMFx1YjJlY1x1Yzc0NCBcdWI5YzhcdWNlNThcdWFjZTAgXHViMmU0XHVjMmRjIFx1YmU2MFx1Yjk4NFx1ZDBkZFx1YmMzMFx1Yjg1YyBcdWIzY2NcdWM1NDRcdWM2MjRcdWM5YzAgXHVjNTRhXHViMjk0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWFjMDEgXHVjZTc4XHVjNzQ0IFx1ZDFiNVx1YWNmY1x1ZDU1OFx1YjI5NFx1YjM3MCBcdWI0ZGNcdWIyOTQgXHVjMmRjXHVhYzA0XHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHVjNzc0XHViNTRjLCBcdWJhYThcdWI0ZTAgXHVkMGRkXHViYzMwXHViOTdjIFx1YmMzMFx1YjJlY1x1ZDU1OFx1YjI5NFx1YjM3MCBcdWFjNzhcdWI5YWNcdWIyOTQgXHVjZDVjXHVjMThjIFx1YzJkY1x1YWMwNFx1Yzc0NCBcdWFjYzRcdWMwYjBcdWQ1NThcdWIyOTQgXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzQ0IFx1Yzc5MVx1YzEzMVx1ZDU1OFx1YzJkY1x1YzYyNC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgXHViM2M0XHVjMmRjXHVjNzU4IFx1ZDA2Y1x1YWUzMCBSXHVhY2ZjIENcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiAoMSAmbGU7IFIgJmxlOyAyMDAwLCAxICZsZTsgQyAmbGU7IDIwMCk8XC9wPlxyXG5cclxuPHA+XHViMmU0XHVjNzRjIFJcdWFjMWMgXHVjOTA0XHVjNWQwXHViMjk0LCBcdWFjMDEgXHVjZTc4XHVjNzQ0IFx1ZDFiNVx1YWNmY1x1ZDU1OFx1YjI5NFx1YjM3MCBcdWI0ZGNcdWIyOTQgXHVjMmRjXHVhYzA0XHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHVjNzc0IFx1YzJkY1x1YWMwNFx1Yzc0MCAwXHViY2Y0XHViMmU0IFx1ZDA2Y1x1YWM3MFx1YjA5OCBcdWFjMTlcdWFjZTAsIDUwMDBcdWJjZjRcdWIyZTQgXHVjNzkxXHVhYzcwXHViMDk4IFx1YWMxOVx1Yzc0MCBcdWM3OTBcdWM1ZjBcdWMyMThcdWM3NzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YjJlNFx1Yzc0YyBcdWM5MDRcdWM1ZDBcdWIyOTQgXHViYzMwXHViMmVjXHVkNTc0XHVjNTdjIFx1ZDU1OFx1YjI5NCBcdWJiM2NcdWQ0ODhcdWM3NTggXHVjMjE4IEQgKDEgJmxlOyBEICZsZTsgMjAwMDAwKVx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1YjJlNFx1Yzc0YyBEXHVhYzFjIFx1YzkwNFx1YzVkMFx1YjI5NCBcdWJiM2NcdWQ0ODhcdWM3NDQgXHViYzMwXHViMmVjXHVkNTc0XHVjNTdjIFx1ZDU1OFx1YjI5NCBcdWFjZjNcdWM3NTggXHVjNzA0XHVjZTU4XHVjNzU4IFx1Yzg4Y1x1ZDQ1Y1x1YWMwMCBcdWJjMzBcdWIyZWNcdWQ1NzRcdWM1N2MgXHVkNTU4XHViMjk0IFx1YzIxY1x1YzExY1x1YjMwMFx1Yjg1YyBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1YWMxOVx1Yzc0MCBcdWFjZjNcdWM3NzQgXHVjNWVjXHViN2VjIFx1YmM4OCBcdWM4ZmNcdWM1YjRcdWM5YzggXHVjMjE4XHViMjk0IFx1Yzc4OFx1YjJlNC4gXHVkNTU4XHVjOWMwXHViOWNjLCBcdWM1ZjBcdWMxOGRcdWQ1NzRcdWMxMWMgXHVhYzE5XHVjNzQwIFx1YWNmM1x1Yzc0NCBcdWJjMzBcdWIyZWNcdWQ1NzRcdWM1N2MgXHVkNTU4XHViMjk0IFx1YWNiZFx1YzZiMFx1YjI5NCBcdWM1YzZcdWIyZTQuJm5ic3A7PFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHViYWE4XHViNGUwIFx1ZDBkZFx1YmMzMFx1Yjk3YyBcdWJjMzBcdWIyZWNcdWQ1NThcdWIyOTRcdWIzNzAgXHVhYzAwXHVjN2E1IFx1YmU2MFx1Yjk3OCBcdWMyZGNcdWFjMDRcdWM3NDQgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiI8cD5cdWM2MDhcdWM4MWNcdWM3NTggXHVhY2JkXHVjNmIwXHVjNWQwXHViMjk0IFx1YzU0NFx1Yjc5OFx1YzY0MCBcdWFjMTlcdWM3NzQgXHVjNzc0XHViM2Q5XHVkNTU4XHViYTc0IFx1YjQxY1x1YjJlNC48XC9wPlxyXG5cclxuPHA+KDEsIDEpLCAoMiwgMSksICgzLCAxKSwgKDMsIDIpLCAoMywgMyksICgyLCAzKSwgPHN0cm9uZz4oMSwgMyk8XC9zdHJvbmc+LCAoMiwgMyksIDxzdHJvbmc+KDMsIDMpPFwvc3Ryb25nPiwgKDIsIDMpLCA8c3Ryb25nPigyLCAyKTxcL3N0cm9uZz48XC9wPlxyXG5cclxuPHA+XHVjZDFkIFx1YmMzMFx1YjJlYyBcdWMyZGNcdWFjMDRcdWM3NDAgMSsyKzErMCsxKzIrMisyKzErMiszPTE3XHVhYzAwIFx1YjQxY1x1YjJlNC48XC9wPlxyXG4iLCJvcmlnaW5hbCI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1ZDU1Y1x1YWQ2ZFx1YzViNCJ9LHsicHJvYmxlbV9pZCI6IjI5MzkiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJET1NUQVZBIiwiZGVzY3JpcHRpb24iOiI8cD5MaXR0bGUgSXZpY2EgcmVjZW50bHkgZ290IGEgam9iIGRlbGl2ZXJpbmcgcGl6emFzIGZvciB0aGUgbW9zdCBwb3B1bGFyIHBpenplcmlhIGluIHRvd24uJm5ic3A7PFwvcD5cclxuXHJcbjxwPkF0IHRoZSBzdGFydCBvZiBoaXMgd29yayBkYXksIGhlIHJlY2VpdmVzIGEgbGlzdCB3aXRoIHRoZSBsb2NhdGlvbnMgdG8gd2hpY2ggaGUgbmVlZHMgdG8gZGVsaXZlciBwaXp6YXMsIGluIG9yZGVyIGluIHdoaWNoIHRoZSBsb2NhdGlvbnMgYXJlIGdpdmVuLiZuYnNwOzxcL3A+XHJcblxyXG48cD5UaGUgY2l0eSBpcyBkaXZpZGVkIGludG8gUiZ0aW1lcztDIGNlbGxzLiBUaGUgcm93cyBhcmUgbnVtYmVyZWQgMSB0aHJvdWdoIFIsIGNvbHVtbnMgMSB0aHJvdWdoIEMuJm5ic3A7PFwvcD5cclxuXHJcbjxwPkZyb20gZXZlcnkgY2VsbCwgaXQgaXMgcG9zc2libGUgdG8gbW92ZSB0byBuZWlnaGJvdXJpbmcgY2VsbHMgdG8gdGhlIGxlZnQgYW5kIHJpZ2h0LiBNb3ZpbmcgdXAgb3IgZG93biBpcyBvbmx5IGFsbG93ZWQgaW4gdGhlIGZpcnN0IGFuZCBsYXN0IGNvbHVtbnMgKGNvbHVtbnMgMSBhbmQgQykuJm5ic3A7PFwvcD5cclxuXHJcbjxwPlRoZSBwaXp6ZXJpYSBpcyBpbiB0aGUgdG9wIGxlZnQgY29ybmVyICgxLCAxKSBhbmQgdGhpcyBpcyB0aGUgbG9jYXRpb24gSXZpY2Egc3RhcnRzIGZyb20uIEl2aWNhIHRha2VzIHdpdGggaGltIGFsbCB0aGUgcGl6emFzIGhlIHdpbGwgZGVsaXZlciB0aGF0IGRheSBzbyBoZSBkb2VzIG5vdCBoYXZlIHRvIHJldHVybiB0byB0aGUgcGl6emVyaWEgYmV0d2VlbiBkZWxpdmVyaWVzIG9yIGFmdGVyIHRoZSBsYXN0IGRlbGl2ZXJ5LiZuYnNwOzxcL3A+XHJcblxyXG48cD5Gb3IgZWFjaCBsb2NhdGlvbiBpbiB0aGUgY2l0eSwgSXZpY2Ega25vd3MgaG93IG11Y2ggdGltZSBoZSB3aWxsIHNwZW5kIGV2ZXJ5IHRpbWUgaGUgaXMgaW4gaXQgKHRyeWluZyB0byBnZXQgdGhyb3VnaCB0aGUgaW50ZXJzZWN0aW9uLCBmb3IgZXhhbXBsZSkuJm5ic3A7PFwvcD5cclxuXHJcbjxwPldyaXRlIGEgcHJvZ3JhbSB0aGF0IGNhbGN1bGF0ZXMgdGhlIHNtYWxsZXN0IGFtb3VudCBvZiB0aW1lIGZvciBJdmljYSB0byBkZWxpdmVyIGFsbCB0aGUgcGl6emFzLjxcL3A+XHJcbiIsImlucHV0IjoiPHA+VGhlIGZpcnN0IGxpbmUgY29udGFpbnMgdGhlIGludGVnZXJzIFIgYW5kIEMgKDEgJmxlOyBSICZsZTsgMjAwMCwgMSAmbGU7IEMgJmxlOyAyMDApLCB0aGUgZGltZW5zaW9ucyBvZiB0aGUgY2l0eS4mbmJzcDs8XC9wPlxyXG5cclxuPHA+RWFjaCBvZiB0aGUgZm9sbG93aW5nIFIgbGluZXMgY29udGFpbnMgQyBpbnRlZ2Vycy4gVGhlc2UgYXJlIHRoZSB0aW1lcyBJdmljYSBzcGVuZHMgZXZlcnkgdGltZSBoZSBlbnRlcnMgYSBsb2NhdGlvbi4gVGhlIHRpbWVzIHdpbGwgYmUgaW50ZWdlcnMgYmV0d2VlbiAwIGFuZCA1MDAwLCBpbmNsdXNpdmUuJm5ic3A7PFwvcD5cclxuXHJcbjxwPlRoZSBuZXh0IGxpbmUgY29udGFpbnMgYW4gaW50ZWdlciBEICgxICZsZTsgRCAmbGU7IDIwMDAwMCksIHRoZSBudW1iZXIgb2YgcGl6emEgZGVsaXZlcmllcyB0aGF0IGRheS4gKE5vLCBpdCYjMzk7cyBub3QgdW5yZWFsaXN0aWNhbGx5IGxhcmdlIGF0IGFsbC4pJm5ic3A7PFwvcD5cclxuXHJcbjxwPkVhY2ggb2YgdGhlIGZvbGxvd2luZyBEIGxpbmVzIGNvbnRhaW5zIHR3byBpbnRlZ2VycyBBIGFuZCBCICgxICZsZTsgQSAmbGU7IFIsIDEgJmxlOyBCICZsZTsgQyksIHRoZSBsb2NhdGlvbiB0byB3aGljaCBhIHBpenphIG11c3QgYmUgZGVsaXZlcmVkLiBUaGUgcGl6emFzIGFyZSBnaXZlbiBpbiB0aGUgb3JkZXIgaW4gd2hpY2ggdGhleSBtdXN0IGJlIGRlbGl2ZXJlZC4gTm8gbG9jYXRpb24gd2lsbCBiZSBnaXZlbiB0d2ljZSBpbiBhIHJvdy4mbmJzcDs8XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5PdXRwdXQgdGhlIHNtYWxsZXN0IGFtb3VudCBvZiB0aW1lIGZvciBJdmljYSB0byBkZWxpdmVyIGFsbCB0aGUgcGl6emFzLiZuYnNwOzxcL3A+XHJcblxyXG48cD4mbmJzcDs8XC9wPlxyXG4iLCJoaW50IjoiPHA+SW4gdGhlIGZpcnN0LCB0aGUgc2hvcnRlc3QgcGF0aCBnb2VzIHRocm91Z2ggdGhlIGZvbGxvd2luZyBsb2NhdGlvbnM6ICgxLCAxKSwgKDIsIDEpLCAoMywgMSksICgzLCAyKSwgKDMsIDMpLCAoMiwgMyksICgxLCAzKSwgKDIsIDMpLCAoMywgMyksICgyLCAzKSBhbmQgKDIsIDIpLiZuYnNwOzxcL3A+XHJcblxyXG48cD5UaGUgbG9jYXRpb25zIGluIGJvbGQgc2hvdyB3aGVyZSBNaXJrbyBtYWRlIGRlbGl2ZXJpZXMuJm5ic3A7PFwvcD5cclxuXHJcbjxwPlRoZSB0b3RhbCB0aW1lIGZvciB0aGUgZGVsaXZlcmllcyBpcyAxKzIrMSswKzErMisyKzIrMSsyKzM9MTcuPFwvcD5cclxuIiwib3JpZ2luYWwiOiIxIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWM2MDFcdWM1YjQifV0=