시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 512 MB 0 0 0 0.000%

문제

Gael has a padlock with a combination lock. Unlike a typical combination lock which has several rotating discs (one for each digit) from left to right, Gael’s combination lock has R × C rotating discs formed in R rows (numbered from 1 to R) and C columns (numbered from 1 to C). For simplicity, the rotating disc in the ith row and jth column is denoted as rotating disc (i, j).

Similar to a typical combination lock, each rotating disc in Gael’s lock has 10 symbols, numbered from 0 to 9. At any point in time, one of the symbols is visible to Gael.

In one operation, Gael can choose one of the R × C rotating discs and rotate it 1/10 turn clockwise. This causes the symbol visible to Gael to be increased by 1 if the previously visible symbol is not equal to 9, or to be changed to 0 otherwise.

In a typical combination lock, to open the lock, each rotating disc has to be rotated by exactly the correct amount so that the rotating disc shows a predetermined symbol. However, Gael’s lock is mechanically magical and behaves differently.

Gael’s lock will open if there exists a symbol m such that the set of rotating discs currently showing the symbol m forms the letter L. Formally, the lock will open if there exists a symbol m and integers x, y, δx, δy (0 ≤ m ≤ 9; 1 ≤ x − δx < x ≤ R; 1 ≤ y < y + δy ≤ C) such that the rotating disc (i, j) is showing symbol m if and only if at least one of the following is true:

  • i = x and y ≤ j ≤ y + δy
  • x − δx ≤ i ≤ x and j = y

Currently, the symbol visible on the rotating disc (i, j) is Si,j. Help Gael to determine the minimum number of operations needed to open his lock.

입력

Input begins with a line containing two integers: R C (2 ≤ R, C ≤ 1000) representing the number of rows and columns in Gael’s combination lock, respectively. The next R lines each contains a string Si containing C characters between 0 and 9 representing the symbol currently visible on the rotating discs. The jth integer on the ith line is the value of Si,j.

출력

Output in a line an integer representing the minimum number of operations needed to open Gael’s lock.

예제 입력 1

3 5
49581
02777
74386

예제 출력 1

3

By doing one operation on the rotating disc (3, 1) and two operations on the rotating disc (1, 3), the rotating discs are showing the following symbols (the operated discs are underlined):

49781
02777
84386

The set of rotating discs currently showing the symbol 7 forms the letter L. In particular, the values m = 7, x = 2, y = 3, δx = 1, δy = 2 satisfy the condition specified in the problem description for Gael’s lock to be opened.

There is no way to open Gael’s lock in less than 3 operations.

예제 입력 2

4 5
01010
10101
01010
10101

예제 출력 2

4

By doing one operation on the rotating disc (1, 2) and (2, 3) and two operations on the rotating disc (2, 2), the set of rotating discs currently showing the symbol 2 forms the letter L. There is no way to open Gael’s lock in less than 4 operations.