시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
3 초 128 MB 2166 450 238 17.385%

문제

상덕이는 언덕 위에 있는 마을의 우체국에 직업을 얻었다. 마을은 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+XHJcblxyXG48cD5cclxuXHRcdWMwYzFcdWIzNTVcdWM3NzRcdWIyOTQgXHVjNzc0XHViODA3XHVhYzhjIFx1YjllNFx1Yzc3YyBcdWM1NDRcdWNlNjggXHViYzMwXHViMmVjXHVjNzQ0IFx1ZDU1OFx1YjI5NCBcdWFjODNcdWM3NzQgXHVjNWJjXHViOWM4XHViMDk4IFx1ZDc5OFx1YjRlMFx1YzljMCBcdWFkODFcdWFlMDhcdWQ1NzRcdWM4NGNcdWIyZTQuIFx1YzBjMVx1YjM1NVx1Yzc3NFx1YWMwMCBcdWJjMzBcdWIyZWNcdWQ1NThcdWJhNzRcdWMxMWMgXHViYzI5XHViYjM4XHVkNTVjIFx1Y2U3OCBcdWM5MTEgXHVhYzAwXHVjN2E1IFx1YjE5Mlx1Yzc0MCBcdWFjZjNcdWFjZmMgXHViMGFlXHVjNzQwIFx1YWNmM1x1Yzc1OCBcdWFjZTBcdWIzYzQgXHVjYzI4XHVjNzc0XHViOTdjIFx1ZDUzY1x1Yjg1Y1x1YjNjNFx1Yjc3Y1x1YWNlMCBcdWQ1NThcdWM3OTAuIFx1Yzc3NCBcdWI1NGMsIFx1YWMwMFx1YzdhNSBcdWM3OTFcdWM3NDAgXHVkNTNjXHViODVjXHViM2M0XHViODVjIFx1YmFhOFx1YjRlMCBcdWM5ZDFcdWM1ZDAgXHViYzMwXHViMmVjXHVjNzQ0IFx1ZDU1OFx1YjgyNFx1YmE3NCBcdWM1YjRcdWI1YmJcdWFjOGMgXHVkNTc0XHVjNTdjIFx1ZDU1OFx1YjI5NFx1YzljMCBcdWFkNmNcdWQ1NThcdWIyOTQgXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzQ0IFx1Yzc5MVx1YzEzMVx1ZDU1OFx1YzJkY1x1YzYyNC48XC9wPlxyXG4iLCJpbnB1dCI6IlxyXG48cD5cclxuXHRcdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIE5cdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiAoMiAmbGU7IE4gJmxlOyA1MCk8XC9wPlxyXG5cclxuPHA+XHJcblx0XHViMmU0XHVjNzRjIE5cdWFjMWMgXHVjOTA0XHVjNWQwXHViMjk0IFx1YjljOFx1Yzc0NFx1Yzc0NCBcdWIwOThcdWQwYzBcdWIwYjRcdWIyOTQgXHVkNTg5XHViODJjXHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gJiMzOTtQJiMzOTtcdWIyOTQgXHVkNTVjIFx1YmM4OFx1YjljYyBcdWM4ZmNcdWM1YjRcdWM5YzBcdWJhNzAsICYjMzk7SyYjMzk7XHViMjk0IFx1YzgwMVx1YzViNFx1YjNjNCBcdWQ1NWMgXHViYzg4IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHJcblx0XHViMmU0XHVjNzRjIE5cdWFjMWMgXHVjOTA0XHVjNWQwXHViMjk0IFx1ZDU4OVx1YjgyY1x1Yjg1YyBcdWIwOThcdWIyNThcdWM1YjRcdWM5YzQgXHVjOWMwXHVjNWVkXHVjNzU4IFx1YWNlMFx1YjNjNFx1YWMwMCBcdWQ1ODlcdWI4MmMgXHVkNjE1XHVkMGRjXHViODVjIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHVhY2UwXHViM2M0XHViMjk0IDEsMDAwLDAwMFx1YmNmNFx1YjJlNCBcdWM3OTFcdWFjNzBcdWIwOTggXHVhYzE5XHViMmU0LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlxyXG5cdFx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgXHVhYzAwXHVjN2E1IFx1Yzc5MVx1Yzc0MCBcdWQ1M2NcdWI4NWNcdWIzYzRcdWI5N2MgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1ZDU1Y1x1YWQ2ZFx1YzViNCJ9LHsicHJvYmxlbV9pZCI6IjI4NDIiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJQT1x1MDE2MFRBUiIsImRlc2NyaXB0aW9uIjoiPHA+TWlya28gaGFzIGdvdCBhIG1haWxtYW4gam9iIGluIGEgc21hbGwgdG93biBpbiB0aGUgaGlsbHMuIFRoZSB0b3duIGNhbiBiZSByZXByZXNlbnRlZCBieSBhIE4mdGltZXM7TiBtYXRyaXguIEVhY2ggZmllbGQgY29udGFpbnMgb25lIG9mIHRoZSBmb2xsb3dpbmcsIGV4Y2x1c2l2ZWx5OiBhIGhvdXNlIGRlbm90ZWQgYnkgJmxzcXVvO0smcnNxdW87LCB0aGUgcG9zdCBvZmZpY2UgZGVub3RlZCBieSAmbHNxdW87UCZyc3F1bzssIG9yIGEgcGFzdHVyZSBkZW5vdGVkIGJ5ICZsc3F1bzsuJnJzcXVvOy4gQWRkaXRpb25hbGx5LCBlYWNoIGZpZWxkIGlzIGFzc2lnbmVkIGFuIGFsdGl0dWRlLjxcL3A+XHJcblxyXG48cD5FdmVyeSBtb3JuaW5nLCBNaXJrbyBkZWxpdmVycyBtYWlsIHRvIGFsbCBob3VzZXMgaW4gdGhlIHRvd24uIEhlIHN0YXJ0cyBhdCB0aGUgZmllbGQgZGVub3RlZCBieSAmbHNxdW87UCZyc3F1bzssIHdoaWNoIHJlcHJlc2VudHMgYSBzaW5nbGUgcG9zdCBvZmZpY2UgaW4gdGhlIHRvd24uIE1pcmtvIGlzIGFsbG93ZWQgdG8gbW92ZSBob3Jpem9udGFsbHksIHZlcnRpY2FsbHkgYW5kIGRpYWdvbmFsbHksIHRvIGFkamFjZW50IHNxdWFyZXMgb25seS4gT25jZSBoZSBkZWxpdmVycyB0aGUgbGFzdCBwaWVjZSBvZiBtYWlsLCBoZSBtdXN0IHJldHVybiB0byB0aGUgcG9zdCBvZmZpY2UuPFwvcD5cclxuXHJcbjxwPk1pcmtvIGRpZCBub3QgaGF2ZSBhIGNsdWUgYWJvdXQgaG93IHRpcmVzb21lIGhpcyBqb2Igd2lsbCBiZS4gTGV0IHRoZSBkaWZmZXJlbmNlIGJldHdlZW4gdGhlIGhlaWdodHMgb2YgdGhlIGhpZ2hlc3QgYW5kIHRoZSBsb3dlc3QgZmllbGQgTWlya28gdmlzaXRzIHdoaWxlIGRlbGl2ZXJpbmcgdGhlIG1haWwgYmUgZXF1YWwgdG8gaGlzIHRpcmVkbmVzcy4gSGVscCBoaW0gb3V0IGFuZCBkZXRlcm1pbmUgdGhlIGxlYXN0IHRpcmVkbmVzcyBwb3NzaWJsZSBmb3IgTWlya28gdG8gZGVsaXZlciBhbGwgdGhlIG1haWwuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5UaGUgZmlyc3QgbGluZSBvZiBpbnB1dCBjb250YWlucyBhbiBpbnRlZ2VyIE4gKDIgJmxlOyBOICZsZTsgNTApLjxcL3A+XHJcblxyXG48cD5UaGUgZm9sbG93aW5nIE4gbGluZXMgcmVwcmVzZW50IGZpZWxkcyBpbiB0aGUgY29ycmVzcG9uZGluZyBtYXRyaXggcm93LiBUaGUgY2hhcmFjdGVyICZsc3F1bztQJnJzcXVvOyB3aWxsIGFwcGVhciBleGFjdGx5IG9uY2UsIHdoaWxlIHRoZSBjaGFyYWN0ZXIgJmxzcXVvO0smcnNxdW87IHdpbGwgYXBwZWFyIGF0IGxlYXN0IG9uY2UuPFwvcD5cclxuXHJcbjxwPlRoZSBmb2xsb3dpbmcgTiBsaW5lcyBlYWNoIGNvbnRhaW4gTiBwb3NpdGl2ZSBpbnRlZ2VycywgdGhlIGFsdGl0dWRlcyBvZiB0aGUgZmllbGRzIGluIHRoZSBjb3JyZXNwb25kaW5nIG1hdHJpeCByb3cuIFRob3NlIHZhbHVlcyBhcmUgbGVzcyB0aGFuIDEgMDAwIDAwMC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5JbiBhIHNpbmdsZSBsaW5lIG9mIG91dHB1dCBwcmludCBhIHNpbmdsZSBpbnRlZ2VyIHRoYXQgcmVwcmVzZW50cyB0aGUgbWluaW11bSBwb3NzaWJsZSB0aXJlZG5lc3MuPFwvcD5cclxuXHJcbjxwPiZuYnNwOzxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1YzYwMVx1YzViNCJ9XQ==