Similar Strings

Time limit1sMemory limit1024 MB

Summary

Given N strings of length K, delete the fewest so that every pair of adjacent remaining strings shares a matching character at some position.

Level: Medium7 of 10
Topics: Dynamic programming, Bit manipulation, Hash map, String
Solved: No attempts yet

Problem

Two strings $S$ and $T$ of the same length are called similar if the following holds.

Among all $i$ with $1 \leq i \leq \vert S \vert$ , there is at least one $i$ such that $S[i] = T[i]$ .

There is an array of $N$ strings, each of length $K$ . You want to delete zero or more elements from this array without changing the order of the remaining elements, so that every pair of adjacent strings in the remaining array is similar. Find the minimum number of elements you must delete.

Input

The first line contains the integers $N$ and $K$ , separated by a space. $(1 \leq N \leq 5 \times 10^5, 1 \leq K \leq 10)$

The next $N$ lines each contain one string of length $K$ .

Every string consists of lowercase English letters only.

Output

Print the answer on the first line.

Examples2

Example 1
Input
```
5 2
ae
cd
aa
za
ce
```
Expected output
```
2
```
Example 2
Input
```
2 3
abc
edc
```
Expected output
```
0
```