시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 256 MB11821517318.342%

문제

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

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

도시는 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

예제 입력 2

2 5
0 0 0 0 0
1 4 2 3 2
4
1 5
2 2
2 5
2 1

예제 출력 2

9

힌트

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

(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+XHJcbiIsImhpbnQiOiI8cD5cdWNjYWIgXHViYzg4XHVjOWY4IFx1YzYwOFx1YzgxY1x1Yzc1OCBcdWFjYmRcdWM2YjBcdWM1ZDBcdWIyOTQgXHVjNTQ0XHViNzk4XHVjNjQwIFx1YWMxOVx1Yzc3NCBcdWM3NzRcdWIzZDlcdWQ1NThcdWJhNzQgXHViNDFjXHViMmU0LjxcL3A+XHJcblxyXG48cD4oMSwgMSksICgyLCAxKSwgKDMsIDEpLCAoMywgMiksICgzLCAzKSwgKDIsIDMpLCA8c3Ryb25nPigxLCAzKTxcL3N0cm9uZz4sICgyLCAzKSwgPHN0cm9uZz4oMywgMyk8XC9zdHJvbmc+LCAoMiwgMyksIDxzdHJvbmc+KDIsIDIpPFwvc3Ryb25nPjxcL3A+XHJcblxyXG48cD5cdWNkMWQgXHViYzMwXHViMmVjIFx1YzJkY1x1YWMwNFx1Yzc0MCAxKzIrMSswKzErMisyKzIrMSsyKzM9MTdcdWFjMDAgXHViNDFjXHViMmU0LjxcL3A+XHJcbiIsIm9yaWdpbmFsIjoiMCIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiS29yZWFuIn0seyJwcm9ibGVtX2lkIjoiMjkzOSIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IkRPU1RBVkEiLCJkZXNjcmlwdGlvbiI6IjxwPkxpdHRsZSBJdmljYSByZWNlbnRseSBnb3QgYSBqb2IgZGVsaXZlcmluZyBwaXp6YXMgZm9yIHRoZSBtb3N0IHBvcHVsYXIgcGl6emVyaWEgaW4gdG93bi4mbmJzcDs8XC9wPlxyXG5cclxuPHA+QXQgdGhlIHN0YXJ0IG9mIGhpcyB3b3JrIGRheSwgaGUgcmVjZWl2ZXMgYSBsaXN0IHdpdGggdGhlIGxvY2F0aW9ucyB0byB3aGljaCBoZSBuZWVkcyB0byBkZWxpdmVyIHBpenphcywgaW4gb3JkZXIgaW4gd2hpY2ggdGhlIGxvY2F0aW9ucyBhcmUgZ2l2ZW4uJm5ic3A7PFwvcD5cclxuXHJcbjxwPlRoZSBjaXR5IGlzIGRpdmlkZWQgaW50byBSJnRpbWVzO0MgY2VsbHMuIFRoZSByb3dzIGFyZSBudW1iZXJlZCAxIHRocm91Z2ggUiwgY29sdW1ucyAxIHRocm91Z2ggQy4mbmJzcDs8XC9wPlxyXG5cclxuPHA+RnJvbSBldmVyeSBjZWxsLCBpdCBpcyBwb3NzaWJsZSB0byBtb3ZlIHRvIG5laWdoYm91cmluZyBjZWxscyB0byB0aGUgbGVmdCBhbmQgcmlnaHQuIE1vdmluZyB1cCBvciBkb3duIGlzIG9ubHkgYWxsb3dlZCBpbiB0aGUgZmlyc3QgYW5kIGxhc3QgY29sdW1ucyAoY29sdW1ucyAxIGFuZCBDKS4mbmJzcDs8XC9wPlxyXG5cclxuPHA+VGhlIHBpenplcmlhIGlzIGluIHRoZSB0b3AgbGVmdCBjb3JuZXIgKDEsIDEpIGFuZCB0aGlzIGlzIHRoZSBsb2NhdGlvbiBJdmljYSBzdGFydHMgZnJvbS4gSXZpY2EgdGFrZXMgd2l0aCBoaW0gYWxsIHRoZSBwaXp6YXMgaGUgd2lsbCBkZWxpdmVyIHRoYXQgZGF5IHNvIGhlIGRvZXMgbm90IGhhdmUgdG8gcmV0dXJuIHRvIHRoZSBwaXp6ZXJpYSBiZXR3ZWVuIGRlbGl2ZXJpZXMgb3IgYWZ0ZXIgdGhlIGxhc3QgZGVsaXZlcnkuJm5ic3A7PFwvcD5cclxuXHJcbjxwPkZvciBlYWNoIGxvY2F0aW9uIGluIHRoZSBjaXR5LCBJdmljYSBrbm93cyBob3cgbXVjaCB0aW1lIGhlIHdpbGwgc3BlbmQgZXZlcnkgdGltZSBoZSBpcyBpbiBpdCAodHJ5aW5nIHRvIGdldCB0aHJvdWdoIHRoZSBpbnRlcnNlY3Rpb24sIGZvciBleGFtcGxlKS4mbmJzcDs8XC9wPlxyXG5cclxuPHA+V3JpdGUgYSBwcm9ncmFtIHRoYXQgY2FsY3VsYXRlcyB0aGUgc21hbGxlc3QgYW1vdW50IG9mIHRpbWUgZm9yIEl2aWNhIHRvIGRlbGl2ZXIgYWxsIHRoZSBwaXp6YXMuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5UaGUgZmlyc3QgbGluZSBjb250YWlucyB0aGUgaW50ZWdlcnMgUiBhbmQgQyAoMSAmbGU7IFIgJmxlOyAyMDAwLCAxICZsZTsgQyAmbGU7IDIwMCksIHRoZSBkaW1lbnNpb25zIG9mIHRoZSBjaXR5LiZuYnNwOzxcL3A+XHJcblxyXG48cD5FYWNoIG9mIHRoZSBmb2xsb3dpbmcgUiBsaW5lcyBjb250YWlucyBDIGludGVnZXJzLiBUaGVzZSBhcmUgdGhlIHRpbWVzIEl2aWNhIHNwZW5kcyBldmVyeSB0aW1lIGhlIGVudGVycyBhIGxvY2F0aW9uLiBUaGUgdGltZXMgd2lsbCBiZSBpbnRlZ2VycyBiZXR3ZWVuIDAgYW5kIDUwMDAsIGluY2x1c2l2ZS4mbmJzcDs8XC9wPlxyXG5cclxuPHA+VGhlIG5leHQgbGluZSBjb250YWlucyBhbiBpbnRlZ2VyIEQgKDEgJmxlOyBEICZsZTsgMjAwMDAwKSwgdGhlIG51bWJlciBvZiBwaXp6YSBkZWxpdmVyaWVzIHRoYXQgZGF5LiAoTm8sIGl0JiMzOTtzIG5vdCB1bnJlYWxpc3RpY2FsbHkgbGFyZ2UgYXQgYWxsLikmbmJzcDs8XC9wPlxyXG5cclxuPHA+RWFjaCBvZiB0aGUgZm9sbG93aW5nIEQgbGluZXMgY29udGFpbnMgdHdvIGludGVnZXJzIEEgYW5kIEIgKDEgJmxlOyBBICZsZTsgUiwgMSAmbGU7IEIgJmxlOyBDKSwgdGhlIGxvY2F0aW9uIHRvIHdoaWNoIGEgcGl6emEgbXVzdCBiZSBkZWxpdmVyZWQuIFRoZSBwaXp6YXMgYXJlIGdpdmVuIGluIHRoZSBvcmRlciBpbiB3aGljaCB0aGV5IG11c3QgYmUgZGVsaXZlcmVkLiBObyBsb2NhdGlvbiB3aWxsIGJlIGdpdmVuIHR3aWNlIGluIGEgcm93LiZuYnNwOzxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPk91dHB1dCB0aGUgc21hbGxlc3QgYW1vdW50IG9mIHRpbWUgZm9yIEl2aWNhIHRvIGRlbGl2ZXIgYWxsIHRoZSBwaXp6YXMuJm5ic3A7PFwvcD5cclxuXHJcbjxwPiZuYnNwOzxcL3A+XHJcbiIsImhpbnQiOiI8cD5JbiB0aGUgZmlyc3QgZXhhbXBsZSwgdGhlIHNob3J0ZXN0IHBhdGggZ29lcyB0aHJvdWdoIHRoZSBmb2xsb3dpbmcgbG9jYXRpb25zOiAoMSwgMSksICgyLCAxKSwgKDMsIDEpLCAoMywgMiksICgzLCAzKSwgKDIsIDMpLCAoMSwgMyksICgyLCAzKSwgKDMsIDMpLCAoMiwgMykgYW5kICgyLCAyKS4mbmJzcDs8XC9wPlxyXG5cclxuPHA+VGhlIGxvY2F0aW9ucyBpbiBib2xkIHNob3cgd2hlcmUgTWlya28gbWFkZSBkZWxpdmVyaWVzLiZuYnNwOzxcL3A+XHJcblxyXG48cD5UaGUgdG90YWwgdGltZSBmb3IgdGhlIGRlbGl2ZXJpZXMgaXMgMSsyKzErMCsxKzIrMisyKzErMiszPTE3LjxcL3A+XHJcbiIsIm9yaWdpbmFsIjoiMSIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiRW5nbGlzaCJ9XQ==

출처

Contest > Croatian Open Competition in Informatics > COCI 2008/2009 > Contest #6 5번