NUMPATH

Let ~S = { x_1, x_2, ... x_N }~ be a set consisting of ~N~ (distinct in pairs) natural numbers, each of which has exactly ~K~ digits. Therefore, for each element ~x_i \in S~, it holds ~0 \le x_i < 10^K~, and let's assume that numbers less than ~10^{K-1}~ have exactly ~K~ digits, with leading zeros.

Suppose we start with any of these numbers and apply the following process: we select a digit and replace it with any smaller decimal digit we want, as long as we obtain a number that belongs to the set ~S~. We repeat this process as many times as we want (and can), let's say ~M~.

Given ~N~, ~K~, and ~S~, find the maximum possible ~M~ that can result from this process.

Input

The input will consist of two lines. The first line will contain two natural numbers ~N~ and ~K~, separated by a single space. The second line will contain the ~N~ integers ~x_1, x_2, ..., x_N~, separated by a single space each. Assume that each of these consists of exactly ~K~ decimal digits.

Output

The output must consist of a single line containing only one natural number: the maximum possible ~M~.

Constraints

~2 \le N \le 100.000~
~1 \le K \le 18~
Execution time limit: 1 sec
Memory limit: 64 MB

Attention: The numbers ~x_1, x_2, ..., x_N~ may be greater than ~2^{32}~.

Examples of Input - Output

1st

STDIN (numpath.in)

9 3
123 991 323 321 329 121 921 125 999

STDOUT (numpath.out)

4

2nd

STDIN (numpath.in)

4 2
17 23 09 42

STDOUT (numpath.out)

0

Explanation of the Examples: In the 1st example, we can start from the number 999 and move as follows: 999 ~\rightarrow~ 991 ~\rightarrow~ 921 ~\rightarrow~ 321 ~\rightarrow~ 121 making a total of four digit replacements (the replaced digits are underlined). There is no other larger sequence of replacements possible. In the 2nd example, no matter which number we start from, no replacements can be made.