시간 제한메모리 제한제출정답맞힌 사람정답 비율
1.5 초 (추가 시간 없음) 1024 MB (추가 메모리 없음)185312217.742%

문제

빛의 흐름은 점점 어긋나기 시작했고, 사람들은 멀어진 흐름을 잇기 위해 다리를 세웠다. 섬의 여러 끝을 다시 하나로 묶기 위해, 그들은 중심과 가장자리를 연결하는 구조물을 만들었다.

섬의 중심과 끝을 다시 잇기 위한 마지막 구조물, 그들은 그것을 크로스링크라 불렀다. 하지만 그 다리는 끝내 완성되지 못했다.

그들이 마지막으로 이어가고자 했던 흐름의 흔적을 따라가고, 그 다리를 복원하여라.


섬 위에는 $N\times M$ 크기의 격자가 있으며, 위에서부터 $r$번째 행, 왼쪽에서부터 $c$번째 열의 칸을 $(r,c)$로 표기한다.

$NM$개의 칸 중 일부에는 이미 땅이 존재한다. 사람들은 섬을 다시 잇기 위해 땅을 추가로 배치하여 위, 아래, 왼쪽, 오른쪽 네 방향의 가장자리를 모두 연결할 수 있는 크로스링크를 만들고자 한다.

구체적으로, 다음 조건을 만족하는 격자칸의 집합 $S$를 크로스링크라고 정의한다.

  • $(r,c)\in S$인 모든 격자칸에는 땅이 존재한다.
  • 서로 다른 두 격자칸 $a,b\in S$에 대해, 어떤 경로 $a=p_1\rightarrow p_2\rightarrow\cdots\rightarrow p_k=b$가 존재해, $\{p_1,p_2,\cdots ,p_k\}\subset S$이며, $p_i$와 $p_{i+1}$은 상하좌우로 인접하다. $(1\le i\le k-1)$
  • $(1,c)\in S$인 정수 $c$ $(1\le c\le M)$이 존재한다.
  • $(N,c)\in S$인 정수 $c$ $(1\le c\le M)$이 존재한다.
  • $(r,1)\in S$인 정수 $r$ $(1\le r\le N)$이 존재한다.
  • $(r,M)\in S$인 정수 $r$ $(1\le r\le N)$이 존재한다.

다음은 크로스링크를 포함한 격자의 예시이다. 색칠된 칸은 땅이 존재하는 칸을, 색칠되지 않은 칸은 땅이 없는 칸을 나타낸다. 세 번째 예시와 같이, 현재 존재하는 모든 땅이 크로스링크에 포함될 필요는 없다.

아래의 세 격자는 크로스링크를 포함하지 않는다. 예를 들어, 세 번째 예시의 경우 어떤 땅에서 시작하더라도 왼쪽 모서리와 오른쪽 모서리 모두에 도달할 수 없으므로 크로스링크를 포함하지 않는다.

땅을 새로 배치하는 비용은 위치마다 다를 수 있다. 다음과 같은 예시를 보자.

맨 왼쪽 그림은 초기 상태에서 땅이 있는 칸은 검은색으로 색칠되어 있고, 땅이 없는 칸은 그 칸에 땅을 배치하는 가격이 표시되어 있다.

붉은색과 같이 땅을 추가할 경우 총 비용 $4+4=8$로 크로스링크를 만들 수 있다. 그러나 노란색과 같이 땅을 추가할 경우 총 비용 $1+2+1+2+1=7$로 크로스링크를 만들 수 있고, 이것이 최소 가격이다. 연두색과 같이 땅을 추가할 경우 $4+2=6$의 비용만이 들지만, 크로스링크가 존재하지 않으므로 올바른 복원 방법이 아니다.

섬의 사람들은 땅을 배치하여 크로스링크를 짓는 최소 비용을 알아내려고 한다.

입력

첫 줄에 격자의 크기를 나타내는 두 정수 $N,M$이 주어진다.

이후 $N$개의 줄에 걸쳐, 격자의 상태를 나타내는 문자 $C_{i1},C_{i2},\cdots ,C_{iM}$이 차례대로 주어진다. 문자의 의미는 다음과 같다.

  • $C_{ij}$가 0인 경우, 칸 $(i,j)$에 이미 땅이 있음을 의미한다.
  • $C_{ij}$가 1부터 9까지의 숫자인 경우, 칸 $(i,j)$에 땅이 없고, 땅을 배치하는 비용이 $C_{ij}$임을 의미한다.
  • $C_{ij}$가 A부터 Z 중 하나의 알파벳 대문자인 경우, 칸 $(i,j)$에 땅이 없고, 땅을 배치하는 비용이 각각 $10,11,\cdots ,35$임을 의미한다

출력

크로스링크를 만들기 위해 땅을 배치하는 데 필요한 최소 비용을 출력하여라.

제한

  • $2\le N\le 1000$
  • $2\le M\le 1000$
  • $C_{ij}$는 숫자 또는 알파벳 대문자 $(1\le i\le N,1\le j\le M)$

서브태스크

번호배점제한
18

$N \le 4, M \le 4$

23

$C_{ij} = \text{'1'}$ $(1 \le i \le N, 1 \le j \le M)$

311

$i$가 짝수일 때, $C_{ij} = \text{'0'}$ $(1 \le i \le N, 1 \le j \le M)$

442

$N \le 100, M \le 100$

518

$N \le 700, M \le 700$

618

추가 제한 조건이 없다.

예제 입력 1

5 5
00280
20358
10901
24400
12105

예제 출력 1

7

예제 입력 2

5 7
QTVPU0Z
02X010Y
Y0R2T0X
Z301Y40
W0PUXVZ

예제 출력 2

13
W3sicHJvYmxlbV9pZCI6IjM0MTQ0IiwicHJvYmxlbV9sYW5nIjoiMCIsInRpdGxlIjoiXHVkMDZjXHViODVjXHVjMmE0XHViOWMxXHVkMDZjIiwiZGVzY3JpcHRpb24iOiI8cD5cdWJlNWJcdWM3NTggXHVkNzUwXHViOTg0XHVjNzQwIFx1YzgxMFx1YzgxMCBcdWM1YjRcdWFlMGJcdWIwOThcdWFlMzAgXHVjMmRjXHVjNzkxXHVkNTg4XHVhY2UwLCBcdWMwYWNcdWI3OGNcdWI0ZTRcdWM3NDAgXHViYTQwXHVjNWI0XHVjOWM0IFx1ZDc1MFx1Yjk4NFx1Yzc0NCBcdWM3ODdcdWFlMzAgXHVjNzA0XHVkNTc0IFx1YjJlNFx1YjlhY1x1Yjk3YyBcdWMxMzhcdWM2ZTBcdWIyZTQuIFx1YzEyY1x1Yzc1OCBcdWM1ZWNcdWI3ZWMgXHViMDVkXHVjNzQ0IFx1YjJlNFx1YzJkYyBcdWQ1NThcdWIwOThcdWI4NWMgXHViYjM2XHVhZTMwIFx1YzcwNFx1ZDU3NCwgXHVhZGY4XHViNGU0XHVjNzQwIFx1YzkxMVx1YzJlY1x1YWNmYyBcdWFjMDBcdWM3YTVcdWM3OTBcdWI5YWNcdWI5N2MgXHVjNWYwXHVhY2IwXHVkNTU4XHViMjk0IFx1YWQ2Y1x1Yzg3MFx1YmIzY1x1Yzc0NCBcdWI5Y2NcdWI0ZTRcdWM1YzhcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YzEyY1x1Yzc1OCBcdWM5MTFcdWMyZWNcdWFjZmMgXHViMDVkXHVjNzQ0IFx1YjJlNFx1YzJkYyBcdWM3ODdcdWFlMzAgXHVjNzA0XHVkNTVjIFx1YjljOFx1YzljMFx1YjljOSBcdWFkNmNcdWM4NzBcdWJiM2MsIFx1YWRmOFx1YjRlNFx1Yzc0MCBcdWFkZjhcdWFjODNcdWM3NDQgPHN0cm9uZz5cdWQwNmNcdWI4NWNcdWMyYTRcdWI5YzFcdWQwNmM8XC9zdHJvbmc+XHViNzdjIFx1YmQ4OFx1YjgwMFx1YjJlNC4gXHVkNTU4XHVjOWMwXHViOWNjIFx1YWRmOCBcdWIyZTRcdWI5YWNcdWIyOTQgXHViMDVkXHViMGI0IFx1YzY0NFx1YzEzMVx1YjQxOFx1YzljMCBcdWJhYmJcdWQ1ODhcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YWRmOFx1YjRlNFx1Yzc3NCBcdWI5YzhcdWM5YzBcdWI5YzlcdWM3M2NcdWI4NWMgXHVjNzc0XHVjNWI0XHVhYzAwXHVhY2UwXHVjNzkwIFx1ZDU4OFx1YjM1OCBcdWQ3NTBcdWI5ODRcdWM3NTggXHVkNzU0XHVjODAxXHVjNzQ0IFx1YjUzMFx1Yjc3Y1x1YWMwMFx1YWNlMCwgXHVhZGY4IFx1YjJlNFx1YjlhY1x1Yjk3YyBcdWJjZjVcdWM2ZDBcdWQ1NThcdWM1ZWNcdWI3N2MuPFwvcD5cclxuXHJcbjxociBcLz5cclxuPHA+XHVjMTJjIFx1YzcwNFx1YzVkMFx1YjI5NCAkTlxcdGltZXMgTSQgXHVkMDZjXHVhZTMwXHVjNzU4IFx1YWNhOVx1Yzc5MFx1YWMwMCBcdWM3ODhcdWM3M2NcdWJhNzAsIFx1YzcwNFx1YzVkMFx1YzExY1x1YmQ4MFx1ZDEzMCAkciRcdWJjODhcdWM5ZjggXHVkNTg5LCBcdWM2N2NcdWNhYmRcdWM1ZDBcdWMxMWNcdWJkODBcdWQxMzAgJGMkXHViYzg4XHVjOWY4IFx1YzVmNFx1Yzc1OCBcdWNlNzhcdWM3NDQgJChyLGMpJFx1Yjg1YyBcdWQ0NWNcdWFlMzBcdWQ1NWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPiROTSRcdWFjMWNcdWM3NTggXHVjZTc4IFx1YzkxMSBcdWM3N2NcdWJkODBcdWM1ZDBcdWIyOTQgXHVjNzc0XHViYmY4IFx1YjU0NVx1Yzc3NCBcdWM4NzRcdWM3YWNcdWQ1NWNcdWIyZTQuIFx1YzBhY1x1Yjc4Y1x1YjRlNFx1Yzc0MCBcdWMxMmNcdWM3NDQgXHViMmU0XHVjMmRjIFx1Yzc4N1x1YWUzMCBcdWM3MDRcdWQ1NzQgXHViNTQ1XHVjNzQ0IFx1Y2Q5NFx1YWMwMFx1Yjg1YyBcdWJjMzBcdWNlNThcdWQ1NThcdWM1ZWMgXHVjNzA0LCBcdWM1NDRcdWI3OTgsIFx1YzY3Y1x1Y2FiZCwgXHVjNjI0XHViOTc4XHVjYWJkIFx1YjEyNCBcdWJjMjlcdWQ1YTVcdWM3NTggXHVhYzAwXHVjN2E1XHVjNzkwXHViOWFjXHViOTdjIFx1YmFhOFx1YjQ1MCBcdWM1ZjBcdWFjYjBcdWQ1NjAgXHVjMjE4IFx1Yzc4OFx1YjI5NCBcdWQwNmNcdWI4NWNcdWMyYTRcdWI5YzFcdWQwNmNcdWI5N2MgXHViOWNjXHViNGU0XHVhY2UwXHVjNzkwIFx1ZDU1Y1x1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVhZDZjXHVjY2I0XHVjODAxXHVjNzNjXHViODVjLCBcdWIyZTRcdWM3NGMgXHVjODcwXHVhYzc0XHVjNzQ0IFx1YjljY1x1Yzg3MVx1ZDU1OFx1YjI5NCBcdWFjYTlcdWM3OTBcdWNlNzhcdWM3NTggXHVjOWQxXHVkNTY5ICRTJFx1Yjk3YyBcdWQwNmNcdWI4NWNcdWMyYTRcdWI5YzFcdWQwNmNcdWI3N2NcdWFjZTAgXHVjODE1XHVjNzU4XHVkNTVjXHViMmU0LjxcL3A+XHJcblxyXG48dWw+XHJcblx0PGxpPiQocixjKVxcaW4gUyRcdWM3NzggXHViYWE4XHViNGUwIFx1YWNhOVx1Yzc5MFx1Y2U3OFx1YzVkMFx1YjI5NCBcdWI1NDVcdWM3NzQgXHVjODc0XHVjN2FjXHVkNTVjXHViMmU0LjxcL2xpPlxyXG5cdDxsaT5cdWMxMWNcdWI4NWMgXHViMmU0XHViOTc4IFx1YjQ1MCBcdWFjYTlcdWM3OTBcdWNlNzggJGEsYlxcaW4gUyRcdWM1ZDAgXHViMzAwXHVkNTc0LCBcdWM1YjRcdWI1YTQgXHVhY2JkXHViODVjICRhPXBfMVxccmlnaHRhcnJvdyBwXzJcXHJpZ2h0YXJyb3dcXGNkb3RzXFxyaWdodGFycm93IHBfaz1iJFx1YWMwMCBcdWM4NzRcdWM3YWNcdWQ1NzQsICRcXHtwXzEscF8yLFxcY2RvdHMgLHBfa1xcfVxcc3Vic2V0IFMkXHVjNzc0XHViYTcwLCAkcF9pJFx1YzY0MCAkcF97aSsxfSRcdWM3NDAgXHVjMGMxXHVkNTU4XHVjODhjXHVjNmIwXHViODVjIFx1Yzc3OFx1YzgxMVx1ZDU1OFx1YjJlNC4gJCgxXFxsZSBpXFxsZSBrLTEpJDxcL2xpPlxyXG5cdDxsaT4kKDEsYylcXGluIFMkXHVjNzc4IFx1YzgxNVx1YzIxOCAkYyQgJCgxXFxsZSBjXFxsZSBNKSRcdWM3NzQgXHVjODc0XHVjN2FjXHVkNTVjXHViMmU0LjxcL2xpPlxyXG5cdDxsaT4kKE4sYylcXGluIFMkXHVjNzc4IFx1YzgxNVx1YzIxOCAkYyQgJCgxXFxsZSBjXFxsZSBNKSRcdWM3NzQgXHVjODc0XHVjN2FjXHVkNTVjXHViMmU0LjxcL2xpPlxyXG5cdDxsaT4kKHIsMSlcXGluIFMkXHVjNzc4IFx1YzgxNVx1YzIxOCAkciQgJCgxXFxsZSByXFxsZSBOKSRcdWM3NzQgXHVjODc0XHVjN2FjXHVkNTVjXHViMmU0LjxcL2xpPlxyXG5cdDxsaT4kKHIsTSlcXGluIFMkXHVjNzc4IFx1YzgxNVx1YzIxOCAkciQgJCgxXFxsZSByXFxsZSBOKSRcdWM3NzQgXHVjODc0XHVjN2FjXHVkNTVjXHViMmU0LjxcL2xpPlxyXG48XC91bD5cclxuXHJcbjxwPlx1YjJlNFx1Yzc0Y1x1Yzc0MCBcdWQwNmNcdWI4NWNcdWMyYTRcdWI5YzFcdWQwNmNcdWI5N2MgXHVkM2VjXHVkNTY4XHVkNTVjIFx1YWNhOVx1Yzc5MFx1Yzc1OCBcdWM2MDhcdWMyZGNcdWM3NzRcdWIyZTQuIFx1YzBjOVx1Y2U2MFx1YjQxYyBcdWNlNzhcdWM3NDAgXHViNTQ1XHVjNzc0IFx1Yzg3NFx1YzdhY1x1ZDU1OFx1YjI5NCBcdWNlNzhcdWM3NDQsIFx1YzBjOVx1Y2U2MFx1YjQxOFx1YzljMCBcdWM1NGFcdWM3NDAgXHVjZTc4XHVjNzQwIFx1YjU0NVx1Yzc3NCBcdWM1YzZcdWIyOTQgXHVjZTc4XHVjNzQ0IFx1YjA5OFx1ZDBjMFx1YjBiOFx1YjJlNC4gXHVjMTM4IFx1YmM4OFx1YzlmOCBcdWM2MDhcdWMyZGNcdWM2NDAgXHVhYzE5XHVjNzc0LCBcdWQ2MDRcdWM3YWMgXHVjODc0XHVjN2FjXHVkNTU4XHViMjk0IFx1YmFhOFx1YjRlMCBcdWI1NDVcdWM3NzQgXHVkMDZjXHViODVjXHVjMmE0XHViOWMxXHVkMDZjXHVjNWQwIFx1ZDNlY1x1ZDU2OFx1YjQyMCBcdWQ1NDRcdWM2OTRcdWIyOTQgXHVjNWM2XHViMmU0LjxcL3A+XHJcblxyXG48cCBzdHlsZT1cInRleHQtYWxpZ246IGNlbnRlcjtcIj48aW1nIGFsdD1cIlwiIHNyYz1cImh0dHBzOlwvXC91cGxvYWQuYWNtaWNwYy5uZXRcLzU3YmZjM2Y0LTIxZmMtNDNiMS04NzE0LWVhYzcwYmM0Yjk1ZFwvLVwvcHJldmlld1wvXCIgc3R5bGU9XCJ3aWR0aDogNzczcHg7IGhlaWdodDogMjAwcHg7XCIgXC8+PFwvcD5cclxuXHJcbjxwPlx1YzU0NFx1Yjc5OFx1Yzc1OCBcdWMxMzggXHVhY2E5XHVjNzkwXHViMjk0IFx1ZDA2Y1x1Yjg1Y1x1YzJhNFx1YjljMVx1ZDA2Y1x1Yjk3YyBcdWQzZWNcdWQ1NjhcdWQ1NThcdWM5YzAgXHVjNTRhXHViMjk0XHViMmU0LiBcdWM2MDhcdWI5N2MgXHViNGU0XHVjNWI0LCBcdWMxMzggXHViYzg4XHVjOWY4IFx1YzYwOFx1YzJkY1x1Yzc1OCBcdWFjYmRcdWM2YjAgXHVjNWI0XHViNWE0IFx1YjU0NVx1YzVkMFx1YzExYyBcdWMyZGNcdWM3OTFcdWQ1NThcdWIzNTRcdWI3N2NcdWIzYzQgXHVjNjdjXHVjYWJkIFx1YmFhOFx1YzExY1x1YjlhY1x1YzY0MCBcdWM2MjRcdWI5NzhcdWNhYmQgXHViYWE4XHVjMTFjXHViOWFjIFx1YmFhOFx1YjQ1MFx1YzVkMCBcdWIzYzRcdWIyZWNcdWQ1NjAgXHVjMjE4IFx1YzVjNlx1YzczY1x1YmJjMFx1Yjg1YyBcdWQwNmNcdWI4NWNcdWMyYTRcdWI5YzFcdWQwNmNcdWI5N2MgXHVkM2VjXHVkNTY4XHVkNTU4XHVjOWMwIFx1YzU0YVx1YjI5NFx1YjJlNC48XC9wPlxyXG5cclxuPHAgc3R5bGU9XCJ0ZXh0LWFsaWduOiBjZW50ZXI7XCI+PGltZyBhbHQ9XCJcIiBzcmM9XCJodHRwczpcL1wvdXBsb2FkLmFjbWljcGMubmV0XC9kMGNhNzczZC05NDMyLTRlNGQtYjFkYS1mYTI4YzM1NDMxZjVcLy1cL3ByZXZpZXdcL1wiIHN0eWxlPVwid2lkdGg6IDc3M3B4OyBoZWlnaHQ6IDIwMHB4O1wiIFwvPjxcL3A+XHJcblxyXG48cD5cdWI1NDVcdWM3NDQgXHVjMGM4XHViODVjIFx1YmMzMFx1Y2U1OFx1ZDU1OFx1YjI5NCBcdWJlNDRcdWM2YTlcdWM3NDAgXHVjNzA0XHVjZTU4XHViOWM4XHViMmU0IFx1YjJlNFx1Yjk3YyBcdWMyMTggXHVjNzg4XHViMmU0LiBcdWIyZTRcdWM3NGNcdWFjZmMgXHVhYzE5XHVjNzQwIFx1YzYwOFx1YzJkY1x1Yjk3YyBcdWJjZjRcdWM3OTAuPFwvcD5cclxuXHJcbjxwIHN0eWxlPVwidGV4dC1hbGlnbjogY2VudGVyO1wiPjxpbWcgYWx0PVwiXCIgc3JjPVwiaHR0cHM6XC9cL3VwbG9hZC5hY21pY3BjLm5ldFwvNzAwMWU5YTYtYzhkNC00MzJhLTgyNTItNmI3ZmM4MTA3Mjg5XC8tXC9wcmV2aWV3XC9cIiBzdHlsZT1cIndpZHRoOiA5NzNweDsgaGVpZ2h0OiAyMDBweDtcIiBcLz48XC9wPlxyXG5cclxuPHA+XHViOWU4IFx1YzY3Y1x1Y2FiZCBcdWFkZjhcdWI5YmNcdWM3NDAgXHVjZDA4XHVhZTMwIFx1YzBjMVx1ZDBkY1x1YzVkMFx1YzExYyBcdWI1NDVcdWM3NzQgXHVjNzg4XHViMjk0IFx1Y2U3OFx1Yzc0MCBcdWFjODBcdWM3NDBcdWMwYzlcdWM3M2NcdWI4NWMgXHVjMGM5XHVjZTYwXHViNDE4XHVjNWI0IFx1Yzc4OFx1YWNlMCwgXHViNTQ1XHVjNzc0IFx1YzVjNlx1YjI5NCBcdWNlNzhcdWM3NDAgXHVhZGY4IFx1Y2U3OFx1YzVkMCBcdWI1NDVcdWM3NDQgXHViYzMwXHVjZTU4XHVkNTU4XHViMjk0IFx1YWMwMFx1YWNhOVx1Yzc3NCBcdWQ0NWNcdWMyZGNcdWI0MThcdWM1YjQgXHVjNzg4XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWJkODlcdWM3NDBcdWMwYzlcdWFjZmMgXHVhYzE5XHVjNzc0IFx1YjU0NVx1Yzc0NCBcdWNkOTRcdWFjMDBcdWQ1NjAgXHVhY2JkXHVjNmIwIFx1Y2QxZCBcdWJlNDRcdWM2YTkgJDQrND04JFx1Yjg1YyBcdWQwNmNcdWI4NWNcdWMyYTRcdWI5YzFcdWQwNmNcdWI5N2MgXHViOWNjXHViNGU0IFx1YzIxOCBcdWM3ODhcdWIyZTQuIFx1YWRmOFx1YjdlY1x1YjA5OCBcdWIxNzhcdWI3ODBcdWMwYzlcdWFjZmMgXHVhYzE5XHVjNzc0IFx1YjU0NVx1Yzc0NCBcdWNkOTRcdWFjMDBcdWQ1NjAgXHVhY2JkXHVjNmIwIFx1Y2QxZCBcdWJlNDRcdWM2YTkgJDErMisxKzIrMT03JFx1Yjg1YyBcdWQwNmNcdWI4NWNcdWMyYTRcdWI5YzFcdWQwNmNcdWI5N2MgXHViOWNjXHViNGU0IFx1YzIxOCBcdWM3ODhcdWFjZTAsIFx1Yzc3NFx1YWM4M1x1Yzc3NCBcdWNkNWNcdWMxOGMgXHVhYzAwXHVhY2E5XHVjNzc0XHViMmU0LiBcdWM1ZjBcdWI0NTBcdWMwYzlcdWFjZmMgXHVhYzE5XHVjNzc0IFx1YjU0NVx1Yzc0NCBcdWNkOTRcdWFjMDBcdWQ1NjAgXHVhY2JkXHVjNmIwICQ0KzI9NiRcdWM3NTggXHViZTQ0XHVjNmE5XHViOWNjXHVjNzc0IFx1YjRlNFx1YzljMFx1YjljYywgXHVkMDZjXHViODVjXHVjMmE0XHViOWMxXHVkMDZjXHVhYzAwIFx1Yzg3NFx1YzdhY1x1ZDU1OFx1YzljMCBcdWM1NGFcdWM3M2NcdWJiYzBcdWI4NWMgXHVjNjJjXHViYzE0XHViOTc4IFx1YmNmNVx1YzZkMCBcdWJjMjlcdWJjOTVcdWM3NzQgXHVjNTQ0XHViMmM4XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWMxMmNcdWM3NTggXHVjMGFjXHViNzhjXHViNGU0XHVjNzQwIFx1YjU0NVx1Yzc0NCBcdWJjMzBcdWNlNThcdWQ1NThcdWM1ZWMgXHVkMDZjXHViODVjXHVjMmE0XHViOWMxXHVkMDZjXHViOTdjIFx1YzlkM1x1YjI5NCBcdWNkNWNcdWMxOGMgXHViZTQ0XHVjNmE5XHVjNzQ0IFx1YzU0Y1x1YzU0NFx1YjBiNFx1YjgyNFx1YWNlMCBcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWNjYWIgXHVjOTA0XHVjNWQwIFx1YWNhOVx1Yzc5MFx1Yzc1OCBcdWQwNmNcdWFlMzBcdWI5N2MgXHViMDk4XHVkMGMwXHViMGI0XHViMjk0IFx1YjQ1MCBcdWM4MTVcdWMyMTggJE4sTSRcdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWM3NzRcdWQ2YzQgJE4kXHVhYzFjXHVjNzU4IFx1YzkwNFx1YzVkMCBcdWFjNzhcdWNjZDAsIFx1YWNhOVx1Yzc5MFx1Yzc1OCBcdWMwYzFcdWQwZGNcdWI5N2MgXHViMDk4XHVkMGMwXHViMGI0XHViMjk0IFx1YmIzOFx1Yzc5MCAkQ197aTF9LENfe2kyfSxcXGNkb3RzICxDX3tpTX0kXHVjNzc0IFx1Y2MyOFx1Yjg0MFx1YjMwMFx1Yjg1YyBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1YmIzOFx1Yzc5MFx1Yzc1OCBcdWM3NThcdWJiZjhcdWIyOTQgXHViMmU0XHVjNzRjXHVhY2ZjIFx1YWMxOVx1YjJlNC48XC9wPlxyXG5cclxuPHVsPlxyXG5cdDxsaT4kQ197aWp9JFx1YWMwMCA8Y29kZT4wPFwvY29kZT5cdWM3NzggXHVhY2JkXHVjNmIwLCBcdWNlNzggJChpLGopJFx1YzVkMCBcdWM3NzRcdWJiZjggXHViNTQ1XHVjNzc0IFx1Yzc4OFx1Yzc0Y1x1Yzc0NCBcdWM3NThcdWJiZjhcdWQ1NWNcdWIyZTQuPFwvbGk+XHJcblx0PGxpPiRDX3tpan0kXHVhYzAwIDxjb2RlPjE8XC9jb2RlPlx1YmQ4MFx1ZDEzMCA8Y29kZT45PFwvY29kZT5cdWFlNGNcdWM5YzBcdWM3NTggXHVjMjJiXHVjNzkwXHVjNzc4IFx1YWNiZFx1YzZiMCwgXHVjZTc4ICQoaSxqKSRcdWM1ZDAgXHViNTQ1XHVjNzc0IFx1YzVjNlx1YWNlMCwgXHViNTQ1XHVjNzQ0IFx1YmMzMFx1Y2U1OFx1ZDU1OFx1YjI5NCBcdWJlNDRcdWM2YTlcdWM3NzQgJENfe2lqfSRcdWM3ODRcdWM3NDQgXHVjNzU4XHViYmY4XHVkNTVjXHViMmU0LjxcL2xpPlxyXG5cdDxsaT4kQ197aWp9JFx1YWMwMCA8Y29kZT5BPFwvY29kZT5cdWJkODBcdWQxMzAgPGNvZGU+WjxcL2NvZGU+IFx1YzkxMSBcdWQ1NThcdWIwOThcdWM3NTggXHVjNTRjXHVkMzBjXHViY2IzIFx1YjMwMFx1YmIzOFx1Yzc5MFx1Yzc3OCBcdWFjYmRcdWM2YjAsIFx1Y2U3OCAkKGksaikkXHVjNWQwIFx1YjU0NVx1Yzc3NCBcdWM1YzZcdWFjZTAsIFx1YjU0NVx1Yzc0NCBcdWJjMzBcdWNlNThcdWQ1NThcdWIyOTQgXHViZTQ0XHVjNmE5XHVjNzc0IFx1YWMwMVx1YWMwMSAkMTAsMTEsXFxjZG90cyAsMzUkXHVjNzg0XHVjNzQ0IFx1Yzc1OFx1YmJmOFx1ZDU1Y1x1YjJlNDxcL2xpPlxyXG48XC91bD5cclxuIiwib3V0cHV0IjoiPHA+XHVkMDZjXHViODVjXHVjMmE0XHViOWMxXHVkMDZjXHViOTdjIFx1YjljY1x1YjRlNFx1YWUzMCBcdWM3MDRcdWQ1NzQgXHViNTQ1XHVjNzQ0IFx1YmMzMFx1Y2U1OFx1ZDU1OFx1YjI5NCBcdWIzNzAgXHVkNTQ0XHVjNjk0XHVkNTVjIFx1Y2Q1Y1x1YzE4YyBcdWJlNDRcdWM2YTlcdWM3NDQgXHVjZDljXHViODI1XHVkNTU4XHVjNWVjXHViNzdjLjxcL3A+XHJcblxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJLb3JlYW4iLCJsaW1pdCI6Ijx1bD5cclxuXHQ8bGk+JDJcXGxlIE5cXGxlIDEwMDAkPFwvbGk+XHJcblx0PGxpPiQyXFxsZSBNXFxsZSAxMDAwJDxcL2xpPlxyXG5cdDxsaT4kQ197aWp9JFx1YjI5NCBcdWMyMmJcdWM3OTAgXHViNjEwXHViMjk0IFx1YzU0Y1x1ZDMwY1x1YmNiMyBcdWIzMDBcdWJiMzhcdWM3OTAgJCgxXFxsZSBpXFxsZSBOLDFcXGxlIGpcXGxlIE0pJDxcL2xpPlxyXG48XC91bD5cclxuIiwic3VidGFzazEiOiI8cD4kTiBcXGxlIDQsIE0gXFxsZSA0JDxcL3A+XHJcbiIsInN1YnRhc2syIjoiPHA+JENfe2lqfSA9IFxcdGV4dHsmIzM5OzEmIzM5O30kICQoMSBcXGxlIGkgXFxsZSBOLCAxIFxcbGUgaiBcXGxlIE0pJDxcL3A+XHJcbiIsInN1YnRhc2szIjoiPHA+JGkkXHVhYzAwIFx1YzlkZFx1YzIxOFx1Yzc3YyBcdWI1NGMsICRDX3tpan0gPSBcXHRleHR7JiMzOTswJiMzOTt9JCAkKDEgXFxsZSBpIFxcbGUgTiwgMSBcXGxlIGogXFxsZSBNKSQ8XC9wPlxyXG4iLCJzdWJ0YXNrNCI6IjxwPiROIFxcbGUgMTAwLCBNIFxcbGUgMTAwJDxcL3A+XHJcbiIsInN1YnRhc2s1IjoiPHA+JE4gXFxsZSA3MDAsIE0gXFxsZSA3MDAkPFwvcD5cclxuIiwic3VidGFzazYiOiI8cD5cdWNkOTRcdWFjMDAgXHVjODFjXHVkNTVjIFx1Yzg3MFx1YWM3NFx1Yzc3NCBcdWM1YzZcdWIyZTQuPFwvcD5cclxuIn0seyJwcm9ibGVtX2lkIjoiMzQxNDQiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJDcm9zc2xpbmsiLCJkZXNjcmlwdGlvbiI6IjxwPlRoZSBmbG93IG9mIGxpZ2h0IGJlZ2FuIHRvIGRyaWZ0IGFwYXJ0LCBhbmQgaW4gcmVzcG9uc2UsIHBlb3BsZSBidWlsdCBicmlkZ2VzIHRvIHNwYW4gdGhlIHdpZGVuaW5nIGRpc3RhbmNlcy4gVG8gcmV1bml0ZSB0aGUgZnJhY3R1cmVkIGlzbGFuZCwgdGhleSByYWlzZWQgc3RydWN0dXJlcyB0aGF0IHJlYWNoZWQgZnJvbSBpdHMgaGVhcnQgdG8gaXRzIGZhcnRoZXN0IGVkZ2VzLjxcL3A+XHJcblxyXG48cD5UaGUgZmluYWwgc3RydWN0dXJlIG1lYW50IHRvIGNvbXBsZXRlIHRoaXMgcmVjb25uZWN0aW9uIHdhcyBjYWxsZWQgPHN0cm9uZz5Dcm9zc2xpbms8XC9zdHJvbmc+Jm1kYXNoO2J1dCB0aGUgYnJpZGdlIHdhcyBuZXZlciBmaW5pc2hlZC48XC9wPlxyXG5cclxuPHA+Rm9sbG93IHRoZSByZW1uYW50cyBvZiB0aGUgYnJva2VuIGZsb3cgdGhleSBvbmNlIHNvdWdodCB0byB1bml0ZSwgYW5kIHJlc3RvcmUgdGhlIGJyaWRnZSB0aGF0IHdhcyBsZWZ0IGluY29tcGxldGUuPFwvcD5cclxuXHJcbjxociBcLz5cclxuPHA+T24gdGhlIGlzbGFuZCwgdGhlcmUgaXMgYSBncmlkIG9mIHNpemUgJE5cXHRpbWVzIE0kLiBUaGUgY2VsbCBhdCB0aGUgJHIkLXRoIHJvdyBmcm9tIHRoZSB0b3AgYW5kICRjJC10aCBjb2x1bW4gZnJvbSB0aGUgbGVmdCBpcyBkZW5vdGVkIGFzICQocixjKSQuPFwvcD5cclxuXHJcbjxwPlNvbWUgb2YgdGhlICROTSQgY2VsbHMgYWxyZWFkeSBjb250YWluIGxhbmQuIFBlb3BsZSB3YW50IHRvIGFkZCBtb3JlIGxhbmQgdG8gZm9ybSBhIGNyb3NzbGluayZtZGFzaDthIGNvbm5lY3RlZCBncm91cCBvZiBsYW5kIGNlbGxzIHRoYXQgdG91Y2hlcyBhbGwgZm91ciBlZGdlcyBvZiB0aGUgZ3JpZDogdG9wLCBib3R0b20sIGxlZnQsIGFuZCByaWdodC48XC9wPlxyXG5cclxuPHA+Rm9ybWFsbHksIGEgc2V0IG9mIGdyaWQgY2VsbHMgJFMkIGlzIGNvbnNpZGVyZWQgYSBjcm9zc2xpbmsgaWYgaXQgc2F0aXNmaWVzIHRoZSBmb2xsb3dpbmcgY29uZGl0aW9uczo8XC9wPlxyXG5cclxuPHVsPlxyXG5cdDxsaT5FdmVyeSBjZWxsICQocixjKVxcaW4gUyQgY29udGFpbnMgbGFuZC48XC9saT5cclxuXHQ8bGk+Rm9yIGFueSB0d28gZGlzdGluY3QgZ3JpZCBjZWxscyAkYSxiXFxpbiBTJCwgdGhlcmUgZXhpc3RzIGEgcGF0aCAkYT1wXzFcXHJpZ2h0YXJyb3cgcF8yXFxyaWdodGFycm93XFxjZG90c1xccmlnaHRhcnJvdyBwX2s9YiQgc3VjaCB0aGF0ICRcXHtwXzEscF8yLFxcY2RvdHMgLHBfa1xcfVxcc3Vic2V0IFMkIGFuZCAkcF9pJCBhbmQgJHBfe2krMX0kIGFyZSBvcnRob2dvbmFsbHkgYWRqYWNlbnQuICQoMVxcbGUgaVxcbGUgay0xKSQ8XC9saT5cclxuXHQ8bGk+VGhlcmUgZXhpc3RzIGFuIGludGVnZXIgJGMkICQoMVxcbGUgY1xcbGUgTSkkIHN1Y2ggdGhhdCAkKDEsYylcXGluIFMkLjxcL2xpPlxyXG5cdDxsaT5UaGVyZSBleGlzdHMgYW4gaW50ZWdlciAkYyQgJCgxXFxsZSBjXFxsZSBNKSQgc3VjaCB0aGF0ICQoTixjKVxcaW4gUyQuPFwvbGk+XHJcblx0PGxpPlRoZXJlIGV4aXN0cyBhbiBpbnRlZ2VyICRyJCAkKDFcXGxlIHJcXGxlIE4pJCBzdWNoIHRoYXQgJChyLDEpXFxpbiBTJC48XC9saT5cclxuXHQ8bGk+VGhlcmUgZXhpc3RzIGFuIGludGVnZXIgJHIkICQoMVxcbGUgclxcbGUgTikkIHN1Y2ggdGhhdCAkKHIsTSlcXGluIFMkLjxcL2xpPlxyXG48XC91bD5cclxuXHJcbjxwPlRoZSBpbGx1c3RyYXRpb24gYmVsb3cgc2hvd3MgYW4gZXhhbXBsZSBvZiBhIGdyaWQgdGhhdCBjb250YWlucyBhIHZhbGlkIGNyb3NzbGluay4gU2hhZGVkIGNlbGxzIHJlcHJlc2VudCBsYW5kLCB3aGlsZSB1bnNoYWRlZCBjZWxscyByZXByZXNlbnQgZW1wdHkgc3BhY2VzLiBBcyBkZW1vbnN0cmF0ZWQgaW4gdGhlIHRoaXJkIGV4YW1wbGUsIG5vdCBhbGwgbGFuZCBjZWxscyBuZWVkIHRvIGJlIHBhcnQgb2YgdGhlIGNyb3NzbGluay48XC9wPlxyXG5cclxuPHAgc3R5bGU9XCJ0ZXh0LWFsaWduOiBjZW50ZXI7XCI+PGltZyBhbHQ9XCJcIiBzcmM9XCJodHRwczpcL1wvdXBsb2FkLmFjbWljcGMubmV0XC81N2JmYzNmNC0yMWZjLTQzYjEtODcxNC1lYWM3MGJjNGI5NWRcLy1cL3ByZXZpZXdcL1wiIHN0eWxlPVwid2lkdGg6IDc3M3B4OyBoZWlnaHQ6IDIwMHB4O1wiIFwvPjxcL3A+XHJcblxyXG48cD5UaGUgbmV4dCBzZXQgb2YgdGhyZWUgZ3JpZHMgZG9lcyBub3QgY29udGFpbiBhIGNyb3NzbGluay4gRm9yIGV4YW1wbGUsIGluIHRoZSB0aGlyZCBncmlkLCB0aGVyZSBpcyBubyBzdGFydGluZyBwb2ludCBmcm9tIHdoaWNoIGJvdGggdGhlIGxlZnQgYW5kIHJpZ2h0IGVkZ2VzIGNhbiBiZSByZWFjaGVkLCBzbyBpdCBkb2VzIG5vdCBjb250YWluIGEgY3Jvc3NsaW5rLjxcL3A+XHJcblxyXG48cCBzdHlsZT1cInRleHQtYWxpZ246IGNlbnRlcjtcIj48aW1nIGFsdD1cIlwiIHNyYz1cImh0dHBzOlwvXC91cGxvYWQuYWNtaWNwYy5uZXRcL2QwY2E3NzNkLTk0MzItNGU0ZC1iMWRhLWZhMjhjMzU0MzFmNVwvLVwvcHJldmlld1wvXCIgc3R5bGU9XCJ3aWR0aDogNzczcHg7IGhlaWdodDogMjAwcHg7XCIgXC8+PFwvcD5cclxuXHJcbjxwPlRoZSBjb3N0IG9mIHBsYWNpbmcgbmV3IGxhbmQgbWF5IHZhcnkgZGVwZW5kaW5nIG9uIHRoZSBsb2NhdGlvbi4gQ29uc2lkZXIgdGhlIGZvbGxvd2luZyBleGFtcGxlOjxcL3A+XHJcblxyXG48cCBzdHlsZT1cInRleHQtYWxpZ246IGNlbnRlcjtcIj48aW1nIGFsdD1cIlwiIHNyYz1cImh0dHBzOlwvXC91cGxvYWQuYWNtaWNwYy5uZXRcLzcwMDFlOWE2LWM4ZDQtNDMyYS04MjUyLTZiN2ZjODEwNzI4OVwvLVwvcHJldmlld1wvXCIgc3R5bGU9XCJ3aWR0aDogOTczcHg7IGhlaWdodDogMjAwcHg7XCIgXC8+PFwvcD5cclxuXHJcbjxwPkluIHRoZSBsZWZ0bW9zdCBpbWFnZSwgYmxhY2sgY2VsbHMgcmVwcmVzZW50IGV4aXN0aW5nIGxhbmQsIHdoaWxlIHRoZSBudW1iZXJzIGluIHRoZSB1bnNoYWRlZCBjZWxscyBpbmRpY2F0ZSB0aGUgY29zdCBvZiBwbGFjaW5nIG5ldyBsYW5kIGluIHRob3NlIHBvc2l0aW9ucy48XC9wPlxyXG5cclxuPHA+QnkgYWRkaW5nIGxhbmQgYXMgc2hvd24gaW4gcmVkLCBhIGNyb3NzbGluayBjYW4gYmUgZm9ybWVkIGF0IGEgdG90YWwgY29zdCBvZiAkNCs0PTgkLiBIb3dldmVyLCBwbGFjaW5nIGxhbmQgYXMgc2hvd24gaW4geWVsbG93IGZvcm1zIGEgdmFsaWQgY3Jvc3NsaW5rIGF0IGEgbG93ZXIgdG90YWwgY29zdCBvZiAkMSsyKzErMisxPTckLCB3aGljaCBpcyB0aGUgbWluaW11bSBjb3N0IGluIHRoaXMgY2FzZS4gT24gdGhlIG90aGVyIGhhbmQsIHBsYWNpbmcgbGFuZCBhcyBzaG93biBpbiBncmVlbiBvbmx5IGNvc3RzICQ0KzI9NiQsIGJ1dCBzaW5jZSBpdCBkb2VzIG5vdCBjb250YWluIGEgY3Jvc3NsaW5rLCBpdCBpcyBub3QgYSB2YWxpZCBzb2x1dGlvbi48XC9wPlxyXG5cclxuPHA+VGhlIGlzbGFuZGVycyB3YW50IHRvIGZpbmQgdGhlIG1pbmltdW0gdG90YWwgY29zdCByZXF1aXJlZCB0byBwbGFjZSBsYW5kIGFuZCBmb3JtIGEgdmFsaWQgY3Jvc3NsaW5rLjxcL3A+XHJcbiIsImlucHV0IjoiPHA+VGhlIGZpcnN0IGxpbmUgY29udGFpbnMgdHdvIGludGVnZXJzICROLE0kIHJlcHJlc2VudGluZyB0aGUgc2l6ZSBvZiB0aGUgZ3JpZC48XC9wPlxyXG5cclxuPHA+Rm9sbG93aW5nIHRoaXMsICROJCBsaW5lcyBhcmUgcHJvdmlkZWQsIGVhY2ggY29udGFpbmluZyBjaGFyYWN0ZXJzICRDX3tpMX0sQ197aTJ9LFxcY2RvdHMgLENfe2lNfSQgcmVwcmVzZW50aW5nIHRoZSBzdGF0ZSBvZiB0aGUgZ3JpZC4gVGhlIG1lYW5pbmdzIG9mIHRoZSBjaGFyYWN0ZXJzIGFyZSBhcyBmb2xsb3dzOjxcL3A+XHJcblxyXG48dWw+XHJcblx0PGxpPklmICRDX3tpan0kIGlzIDxjb2RlPjA8XC9jb2RlPiwgY2VsbCAkKGksaikkIGFscmVhZHkgY29udGFpbnMgbGFuZC48XC9saT5cclxuXHQ8bGk+SWYgJENfe2lqfSQgaXMgYSBkaWdpdCBmcm9tIDxjb2RlPjE8XC9jb2RlPiB0byA8Y29kZT45PFwvY29kZT4sIGNlbGwgJChpLGopJCBpcyBlbXB0eSwgYW5kIHRoZSBjb3N0IG9mIHBsYWNpbmcgbGFuZCBpcyB0aGUgY29ycmVzcG9uZGluZyBkaWdpdC48XC9saT5cclxuXHQ8bGk+SWYgJENfe2lqfSQgaXMgb25lIG9mIHRoZSB1cHBlcmNhc2UgbGV0dGVycyBmcm9tIDxjb2RlPkE8XC9jb2RlPiB0byA8Y29kZT5aPFwvY29kZT4sIGNlbGwgJChpLGopJCBpcyBlbXB0eSwgYW5kIHRoZSBjb3N0IG9mIHBsYWNpbmcgbGFuZCBpcyAkMTAsMTEsXFxjZG90cyAsMzUkLCByZXNwZWN0aXZlbHkuPFwvbGk+XHJcbjxcL3VsPlxyXG4iLCJvdXRwdXQiOiI8cD5PdXRwdXQgdGhlIG1pbmltdW0gY29zdCByZXF1aXJlZCB0byBwbGFjZSBsYW5kIHRvIGNyZWF0ZSBhIGNyb3NzbGluay48XC9wPlxyXG5cclxuXHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ190Y29kZSI6IkVuZ2xpc2giLCJsaW1pdCI6Ijx1bD5cclxuXHQ8bGk+JDJcXGxlIE5cXGxlIDEwMDAkPFwvbGk+XHJcblx0PGxpPiQyXFxsZSBNXFxsZSAxMDAwJDxcL2xpPlxyXG5cdDxsaT4kQ197aWp9JCBpcyBhIGRpZ2l0IG9yIGFuIHVwcGVyY2FzZSBsZXR0ZXIgJCgxXFxsZSBpXFxsZSBOLDFcXGxlIGpcXGxlIE0pJDxcL2xpPlxyXG48XC91bD5cclxuIiwic3VidGFzazEiOiI8cD4kTiBcXGxlIDQsIE0gXFxsZSA0JDxcL3A+XHJcbiIsInN1YnRhc2syIjoiPHA+JENfe2lqfSA9IFxcdGV4dHtgMSYjMzk7fSQgJCgxIFxcbGUgaSBcXGxlIE4sIDEgXFxsZSBqIFxcbGUgTSkkPFwvcD5cclxuIiwic3VidGFzazMiOiI8cD5Gb3IgZXZlbiAkaSQsICRDX3tpan0gPSBcXHRleHR7YDAmIzM5O30kICQoMSBcXGxlIGkgXFxsZSBOLCAxIFxcbGUgaiBcXGxlIE0pJDxcL3A+XHJcbiIsInN1YnRhc2s0IjoiPHA+JE4gXFxsZSAxMDAsIE0gXFxsZSAxMDAkPFwvcD5cclxuIiwic3VidGFzazUiOiI8cD4kTiBcXGxlIDcwMCwgTSBcXGxlIDcwMCQ8XC9wPlxyXG4iLCJzdWJ0YXNrNiI6IjxwPk5vIGFkZGl0aW9uYWwgY29uc3RyYWludHMuPFwvcD5cclxuIn1d

출처

Contest > BOJ User Contest > BCF > BCF 2025 VIII번

채점 및 기타 정보

  • 예제는 채점하지 않는다.