시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
3 초 128 MB 2347 497 263 17.568%

문제

상덕이는 언덕 위에 있는 마을의 우체국에 직업을 얻었다. 마을은 N×N 행렬로 나타낼 수 있다. 행렬로 나뉘어진 각 지역은 우체국은 'P', 집은 'K', 목초지는 '.' 중 하나로 나타낼 수 있다. 또, 각 지역의 고도도 알고 있다.

매일 아침 상덕이는 마을의 모든 집에 우편을 배달해야 한다. 배달은 마을에 하나밖에 없는 우체국 'P'가 있는 곳에서 시작한다. 상덕이는 현재 있는 칸과 수평, 수직, 대각선으로 인접한 칸으로 이동할 수 있다. 마지막 편지를 배달하고 난 이후에는 다시 우체국으로 돌아와야 한다.

상덕이는 이렇게 매일 아침 배달을 하는 것이 얼마나 힘든지 궁금해졌다. 상덕이가 배달하면서 방문한 칸 중 가장 높은 곳과 낮은 곳의 고도 차이를 피로도라고 하자. 이때, 가장 작은 피로도로 모든 집에 배달을 하려면 어떻게 해야 하는지 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N이 주어진다. (2 ≤ N ≤ 50)

다음 N개 줄에는 마을을 나타내는 행렬이 주어진다. 'P'는 한 번만 주어지며, 'K'는 적어도 한 번 주어진다.

다음 N개 줄에는 행렬로 나뉘어진 지역의 고도가 행렬 형태로 주어진다. 고도는 1,000,000보다 작거나 같다.

출력

첫째 줄에 가장 작은 피로도를 출력한다.

예제 입력 1

3
K.P
...
K.K
3 3 4
9 5 9
8 3 7

예제 출력 1

5
W3sicHJvYmxlbV9pZCI6IjI4NDIiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWM5ZDFcdWJjMzBcdWM2ZDAgXHVkNTVjXHVjMGMxXHViMzU1IiwiZGVzY3JpcHRpb24iOiJcclxuPHA+XHJcblx0XHVjMGMxXHViMzU1XHVjNzc0XHViMjk0IFx1YzViOFx1YjM1NSBcdWM3MDRcdWM1ZDAgXHVjNzg4XHViMjk0IFx1YjljOFx1Yzc0NFx1Yzc1OCBcdWM2YjBcdWNjYjRcdWFkNmRcdWM1ZDAgXHVjOWMxXHVjNWM1XHVjNzQ0IFx1YzViYlx1YzVjOFx1YjJlNC4gXHViOWM4XHVjNzQ0XHVjNzQwIE4mdGltZXM7TiBcdWQ1ODlcdWI4MmNcdWI4NWMgXHViMDk4XHVkMGMwXHViMGJjIFx1YzIxOCBcdWM3ODhcdWIyZTQuIFx1ZDU4OVx1YjgyY1x1Yjg1YyBcdWIwOThcdWIyNThcdWM1YjRcdWM5YzQgXHVhYzAxIFx1YzljMFx1YzVlZFx1Yzc0MCBcdWM2YjBcdWNjYjRcdWFkNmRcdWM3NDAgJiMzOTtQJiMzOTssIFx1YzlkMVx1Yzc0MCAmIzM5O0smIzM5OywgXHViYWE5XHVjZDA4XHVjOWMwXHViMjk0ICYjMzk7LiYjMzk7IFx1YzkxMSBcdWQ1NThcdWIwOThcdWI4NWMgXHViMDk4XHVkMGMwXHViMGJjIFx1YzIxOCBcdWM3ODhcdWIyZTQuIFx1YjYxMCwgXHVhYzAxIFx1YzljMFx1YzVlZFx1Yzc1OCBcdWFjZTBcdWIzYzRcdWIzYzQgXHVjNTRjXHVhY2UwIFx1Yzc4OFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHJcblx0XHViOWU0XHVjNzdjIFx1YzU0NFx1Y2U2OCBcdWMwYzFcdWIzNTVcdWM3NzRcdWIyOTQgXHViOWM4XHVjNzQ0XHVjNzU4IFx1YmFhOFx1YjRlMCBcdWM5ZDFcdWM1ZDAgXHVjNmIwXHVkM2I4XHVjNzQ0IFx1YmMzMFx1YjJlY1x1ZDU3NFx1YzU3YyBcdWQ1NWNcdWIyZTQuIFx1YmMzMFx1YjJlY1x1Yzc0MCBcdWI5YzhcdWM3NDRcdWM1ZDAgXHVkNTU4XHViMDk4XHViYzE2XHVjNWQwIFx1YzVjNlx1YjI5NCBcdWM2YjBcdWNjYjRcdWFkNmQgJiMzOTtQJiMzOTtcdWFjMDAgXHVjNzg4XHViMjk0IFx1YWNmM1x1YzVkMFx1YzExYyBcdWMyZGNcdWM3OTFcdWQ1NWNcdWIyZTQuIFx1YzBjMVx1YjM1NVx1Yzc3NFx1YjI5NCBcdWQ2MDRcdWM3YWMgXHVjNzg4XHViMjk0IFx1Y2U3OFx1YWNmYyBcdWMyMThcdWQzYzksIFx1YzIxOFx1YzljMSwgXHViMzAwXHVhYzAxXHVjMTIwXHVjNzNjXHViODVjIFx1Yzc3OFx1YzgxMVx1ZDU1YyBcdWNlNzhcdWM3M2NcdWI4NWMgXHVjNzc0XHViM2Q5XHVkNTYwIFx1YzIxOCBcdWM3ODhcdWIyZTQuIFx1YjljOFx1YzljMFx1YjljOSBcdWQzYjhcdWM5YzBcdWI5N2MgXHViYzMwXHViMmVjXHVkNTU4XHVhY2UwIFx1YjA5YyBcdWM3NzRcdWQ2YzRcdWM1ZDBcdWIyOTQgXHViMmU0XHVjMmRjIFx1YzZiMFx1Y2NiNFx1YWQ2ZFx1YzczY1x1Yjg1YyBcdWIzY2NcdWM1NDRcdWM2NDBcdWM1N2MgXHVkNTVjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cclxuXHRcdWMwYzFcdWIzNTVcdWM3NzRcdWIyOTQgXHVjNzc0XHViODA3XHVhYzhjIFx1YjllNFx1Yzc3YyBcdWM1NDRcdWNlNjggXHViYzMwXHViMmVjXHVjNzQ0IFx1ZDU1OFx1YjI5NCBcdWFjODNcdWM3NzQgXHVjNWJjXHViOWM4XHViMDk4IFx1ZDc5OFx1YjRlMFx1YzljMCBcdWFkODFcdWFlMDhcdWQ1NzRcdWM4NGNcdWIyZTQuIFx1YzBjMVx1YjM1NVx1Yzc3NFx1YWMwMCBcdWJjMzBcdWIyZWNcdWQ1NThcdWJhNzRcdWMxMWMgXHViYzI5XHViYjM4XHVkNTVjIFx1Y2U3OCBcdWM5MTEgXHVhYzAwXHVjN2E1IFx1YjE5Mlx1Yzc0MCBcdWFjZjNcdWFjZmMgXHViMGFlXHVjNzQwIFx1YWNmM1x1Yzc1OCBcdWFjZTBcdWIzYzQgXHVjYzI4XHVjNzc0XHViOTdjIFx1ZDUzY1x1Yjg1Y1x1YjNjNFx1Yjc3Y1x1YWNlMCBcdWQ1NThcdWM3OTAuIFx1Yzc3NFx1YjU0YywgXHVhYzAwXHVjN2E1IFx1Yzc5MVx1Yzc0MCBcdWQ1M2NcdWI4NWNcdWIzYzRcdWI4NWMgXHViYWE4XHViNGUwIFx1YzlkMVx1YzVkMCBcdWJjMzBcdWIyZWNcdWM3NDQgXHVkNTU4XHViODI0XHViYTc0IFx1YzViNFx1YjViYlx1YWM4YyBcdWQ1NzRcdWM1N2MgXHVkNTU4XHViMjk0XHVjOWMwIFx1YWQ2Y1x1ZDU1OFx1YjI5NCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NDQgXHVjNzkxXHVjMTMxXHVkNTU4XHVjMmRjXHVjNjI0LjxcL3A+XHJcbiIsImlucHV0IjoiXHJcbjxwPlxyXG5cdFx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgTlx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuICgyICZsZTsgTiAmbGU7IDUwKTxcL3A+XHJcblxyXG48cD5cclxuXHRcdWIyZTRcdWM3NGMgTlx1YWMxYyBcdWM5MDRcdWM1ZDBcdWIyOTQgXHViOWM4XHVjNzQ0XHVjNzQ0IFx1YjA5OFx1ZDBjMFx1YjBiNFx1YjI5NCBcdWQ1ODlcdWI4MmNcdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiAmIzM5O1AmIzM5O1x1YjI5NCBcdWQ1NWMgXHViYzg4XHViOWNjIFx1YzhmY1x1YzViNFx1YzljMFx1YmE3MCwgJiMzOTtLJiMzOTtcdWIyOTQgXHVjODAxXHVjNWI0XHViM2M0IFx1ZDU1YyBcdWJjODggXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cclxuXHRcdWIyZTRcdWM3NGMgTlx1YWMxYyBcdWM5MDRcdWM1ZDBcdWIyOTQgXHVkNTg5XHViODJjXHViODVjIFx1YjA5OFx1YjI1OFx1YzViNFx1YzljNCBcdWM5YzBcdWM1ZWRcdWM3NTggXHVhY2UwXHViM2M0XHVhYzAwIFx1ZDU4OVx1YjgyYyBcdWQ2MTVcdWQwZGNcdWI4NWMgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWFjZTBcdWIzYzRcdWIyOTQgMSwwMDAsMDAwXHViY2Y0XHViMmU0IFx1Yzc5MVx1YWM3MFx1YjA5OCBcdWFjMTlcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHJcblx0XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBcdWFjMDBcdWM3YTUgXHVjNzkxXHVjNzQwIFx1ZDUzY1x1Yjg1Y1x1YjNjNFx1Yjk3YyBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVkNTVjXHVhZDZkXHVjNWI0In0seyJwcm9ibGVtX2lkIjoiMjg0MiIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IlBPXHUwMTYwVEFSIiwiZGVzY3JpcHRpb24iOiI8cD5NaXJrbyBoYXMgZ290IGEgbWFpbG1hbiBqb2IgaW4gYSBzbWFsbCB0b3duIGluIHRoZSBoaWxscy4gVGhlIHRvd24gY2FuIGJlIHJlcHJlc2VudGVkIGJ5IGEgTiZ0aW1lcztOIG1hdHJpeC4gRWFjaCBmaWVsZCBjb250YWlucyBvbmUgb2YgdGhlIGZvbGxvd2luZywgZXhjbHVzaXZlbHk6IGEgaG91c2UgZGVub3RlZCBieSAmbHNxdW87SyZyc3F1bzssIHRoZSBwb3N0IG9mZmljZSBkZW5vdGVkIGJ5ICZsc3F1bztQJnJzcXVvOywgb3IgYSBwYXN0dXJlIGRlbm90ZWQgYnkgJmxzcXVvOy4mcnNxdW87LiBBZGRpdGlvbmFsbHksIGVhY2ggZmllbGQgaXMgYXNzaWduZWQgYW4gYWx0aXR1ZGUuPFwvcD5cclxuXHJcbjxwPkV2ZXJ5IG1vcm5pbmcsIE1pcmtvIGRlbGl2ZXJzIG1haWwgdG8gYWxsIGhvdXNlcyBpbiB0aGUgdG93bi4gSGUgc3RhcnRzIGF0IHRoZSBmaWVsZCBkZW5vdGVkIGJ5ICZsc3F1bztQJnJzcXVvOywgd2hpY2ggcmVwcmVzZW50cyBhIHNpbmdsZSBwb3N0IG9mZmljZSBpbiB0aGUgdG93bi4gTWlya28gaXMgYWxsb3dlZCB0byBtb3ZlIGhvcml6b250YWxseSwgdmVydGljYWxseSBhbmQgZGlhZ29uYWxseSwgdG8gYWRqYWNlbnQgc3F1YXJlcyBvbmx5LiBPbmNlIGhlIGRlbGl2ZXJzIHRoZSBsYXN0IHBpZWNlIG9mIG1haWwsIGhlIG11c3QgcmV0dXJuIHRvIHRoZSBwb3N0IG9mZmljZS48XC9wPlxyXG5cclxuPHA+TWlya28gZGlkIG5vdCBoYXZlIGEgY2x1ZSBhYm91dCBob3cgdGlyZXNvbWUgaGlzIGpvYiB3aWxsIGJlLiBMZXQgdGhlIGRpZmZlcmVuY2UgYmV0d2VlbiB0aGUgaGVpZ2h0cyBvZiB0aGUgaGlnaGVzdCBhbmQgdGhlIGxvd2VzdCBmaWVsZCBNaXJrbyB2aXNpdHMgd2hpbGUgZGVsaXZlcmluZyB0aGUgbWFpbCBiZSBlcXVhbCB0byBoaXMgdGlyZWRuZXNzLiBIZWxwIGhpbSBvdXQgYW5kIGRldGVybWluZSB0aGUgbGVhc3QgdGlyZWRuZXNzIHBvc3NpYmxlIGZvciBNaXJrbyB0byBkZWxpdmVyIGFsbCB0aGUgbWFpbC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlRoZSBmaXJzdCBsaW5lIG9mIGlucHV0IGNvbnRhaW5zIGFuIGludGVnZXIgTiAoMiAmbGU7IE4gJmxlOyA1MCkuPFwvcD5cclxuXHJcbjxwPlRoZSBmb2xsb3dpbmcgTiBsaW5lcyByZXByZXNlbnQgZmllbGRzIGluIHRoZSBjb3JyZXNwb25kaW5nIG1hdHJpeCByb3cuIFRoZSBjaGFyYWN0ZXIgJmxzcXVvO1AmcnNxdW87IHdpbGwgYXBwZWFyIGV4YWN0bHkgb25jZSwgd2hpbGUgdGhlIGNoYXJhY3RlciAmbHNxdW87SyZyc3F1bzsgd2lsbCBhcHBlYXIgYXQgbGVhc3Qgb25jZS48XC9wPlxyXG5cclxuPHA+VGhlIGZvbGxvd2luZyBOIGxpbmVzIGVhY2ggY29udGFpbiBOIHBvc2l0aXZlIGludGVnZXJzLCB0aGUgYWx0aXR1ZGVzIG9mIHRoZSBmaWVsZHMgaW4gdGhlIGNvcnJlc3BvbmRpbmcgbWF0cml4IHJvdy4gVGhvc2UgdmFsdWVzIGFyZSBsZXNzIHRoYW4gMSAwMDAgMDAwLjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPkluIGEgc2luZ2xlIGxpbmUgb2Ygb3V0cHV0IHByaW50IGEgc2luZ2xlIGludGVnZXIgdGhhdCByZXByZXNlbnRzIHRoZSBtaW5pbXVtIHBvc3NpYmxlIHRpcmVkbmVzcy48XC9wPlxyXG5cclxuPHA+Jm5ic3A7PFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVjNjAxXHVjNWI0In1d