땅부자 피에로는 운석이 많이 떨어지는 혹성 피에로에서 거주한다.
그는 N*N 크기의 땅을 가지고 있는데, 하늘에서 운석들이 그의 땅에 떨어졌다. 운석의 무게는 각각 Wij로, 동그란 구의 모양을 하고 있다. 다행히도 한겨울인 관계로 농작물을 기르지 않아 피해는 전혀 없다고 한다.
피에로는 운석들을 연구 재료로 보낼 생각은 추호도 없다. 그저 운석들을 그의 땅 밖으로 굴러버리려 한다. 운석은 동그란 형태의 구이기 때문에, 인접한 다른 땅으로 이동시키는데 Wij의 비용만이 든다.
힘이 많이드는 것을 싫어하는 피에로는 떨어진 위치와 운석의 무게를 그려와 당신에게 최소한의 비용으로 운석들을 치워주기를 요청했다.
3 1 2 4 4 7 6 2 5 2 3 1 9 6 4 8다음은 하나의 예제이다. 가운데의 7,6은 위쪽으로 2번씩 굴리면 되고 2,3은 아래쪽으로 2번씩 굴리면 된다. 그 외 나머지 데이터는 인접한 면으로 굴리면 되므로 위 예제의 최소비용은 85가 된다.
피에로를 도와 운석을 모두 치우는데 드는 최소비용을 구해주자.
입력 4 3 1 2 4 4 7 6 2 5 2 3 1 9 6 4 8 출력 85
출처: pl0892029