Flood-it

Flood-it은 다음과 같은 규칙을 갖는 게임이다. 이 문제를 풀기 전에, 실제로 게임을 해보고 싶다면 https://unixpapa.com/floodit/에서 할 수 있다.

게임의 규칙은 다음과 같다. 가로 $N$ 줄, 세로 $N$ 열 $N \times N$으로 이루어진 격자가 있다. 격자의 각 칸에는 $10$가지 색 중 하나가 칠해져 있다. 색깔이 같고, 위, 아래, 왼쪽, 오른쪽 중 하나로 바로 인접한 두 칸은 한 덩어리로 생각하자. 이런 식으로 생각하면 한 덩어리로 생각할 수 있는 칸은 두 칸 이상이 될 수 있다. 이제 매번 가장 왼쪽 위 칸의 색깔을 바꿀 수 있다. 이 칸의 색깔이 바뀌면, 이 칸과 같은 덩어리에 있는 칸들의 색깔이 모두 바뀐다.

위 그림은 $5 \times 5$ 크기 격자로 주어진 Flood-it 게임의 예이다. 각 칸의 색깔은 숫자로도 표현되어 있다.

• 처음 가장 왼쪽 위 칸의 색은 $1$이며, 바로 아래 칸과 한 덩어리를 이룬다.
• 이제 이 칸의 색을 $1$에서 $2$로 바꾸면, 같은 덩어리에 있는 칸들의 색이 모두 $1$에서 $2$로 바뀐다. 이 과정에서, 색이 원래 $2$이던 칸 하나가 새롭게 덩어리에 추가된다.
• 다시 가장 왼쪽 위 칸의 색을 $3$으로 바꾸면, 같은 덩어리에 있던 칸들의 색이 모두 $2$에서 $3$으로 바뀐다. 이 과정에서 색이 원래 $3$이던 칸 셋이 새롭게 덩어리에 추가된다.
• 마지막으로, 가장 왼쪽 위 칸의 색을 $4$로 바꾸면, 같은 덩어리에 있던 칸들의 색이 모두 $3$에서 $4$로 바뀐다. 이 과정에서 색이 원래 $4$이던 칸 둘이 새롭게 덩어리에 추가된다.

Flood-it 게임의 목적은 색깔을 바꾸는 횟수를 최소화하여 전체 칸들의 색깔을 모두 같게 하는 것이다.

가장 왼쪽 윗 칸의 색깔의 변화 정보가 주어졌을 때, 이 순서대로 색깔을 바꾸고 난 뒤, 가장 왼쪽 위 칸과 한 덩어리인 칸 수를 구하는 프로그램을 작성하시오.

입력 형식

첫째 줄에 격자의 크기를 나타내는 자연수 $N$과 가장 왼쪽 위 칸의 색깔이 바뀌는 횟수 $K$가 주어진다 ($1 \le N \le 1\,000$, $0 \le K \le 1\,000$).

만약 $K$가 $0$이 아니라면, 바로 다음 줄에는 $K$ 개의 $0$ 이상 $9$ 이하의 정수가 주어지는데, 이는 차례대로 가장 왼쪽 위 칸의 색이 이 정수가 나타내는 색깔로 변함을 의미한다. 각 칸에 올 수 있는 색깔이 $10$가지이므로 이렇게 표현할 수 있다. $K$가 $0$이라면 이 줄은 존재하지 않는다.

다음 $N$ 줄에는 격자의 각 칸 색깔 정보가 주어진다. 격자를 위에서 아래로 읽었을 때 차례로, 한 줄에 하나씩 $N$개의 $0$ 이상 $9$ 이하 정수가 주어지는데, 이는 격자의 각 행을 왼쪽부터 오른쪽으로 읽어나갔을 때 각 칸의 색깔을 나타낸다.

출력 형식

출력은 한 줄로 구성된다. 첫 줄에 가장 왼쪽 칸과 같은 덩어리에 속하는 칸 수를 출력한다. 칸 수를 셀 때 가장 왼쪽 윗 칸 자신도 포함됨에 주의하라.

예제

5 3
2 3 4
1 3 2 3 3
1 2 1 5 3
4 3 6 3 1
1 3 4 2 3
1 5 1 3 5

8

채점 방식

입력 케이스들은 다음과 같은 종류로 구별되며, 한 종류의 케이스를 다 맞추어야 그 종류에 배정된 점수를 받을 수 있다.

해설