402218: GYM100703 A Tea-drinking

Castles Valley was lit by the noonday sun. One could descry two figures on a balcony of one of Castles — a big and a small ones. Dragon and Princess were drinking tea. Dragon was fond of preparing tea compositions, and he was very glad that Princess was drinking tea with great pleasure and listened with interest to his narrations on how one or another tea was composed.

Dragon always puts into a teapot m teaspoons of ingredients, which he calls portions. If it is written "put two portions of Black Ceylon Tea, add one portion of currant leaves, one portion of cornflowers, and after put another portion of Black Ceylon Tea and a portion of calendula petals" in a recipe, Dragon puts the portions to the teapot exactly in the described order: he is absolutely sure that the taste of a tea depends on the order in which ingredients are put.

Dragon told Princess that once upon a time his friend Knight imparted to him a recipe of a delicious tea, and since then he, Dragon, got into making tea compositions. He experimented with replacing some ingredients with some another ones in this recipe, and when he liked the taste of a brand new tea, he wrote down the resulting recipe. And he has done it so many times, choosing one of the written recipes as a basic one for a new recipe each time.

Dragon has an original system of composing teas and writing their recipes. He denotes all of used ingredients by lowercase Latin letters (each letter corresponds to some ingredient, the same ingredients denoted by the same letters, and different ingredients denoted by different letters). So, a tea description is a string of m letters in the same order of ingredients as in the recipe.

When Dragon was inventing the notation, he supposed that more similar (in his viewpoint) ingredients should be denoted by more closely spaced (in alphabetical order) symbols. Indeed, it is much less radical solution to replace currant leaves with blackberry leaves, than to replace calendula petals with a cinnamon. For this reason, Dragon defined the distance between recipes as a maximum absolute value of a distances between ingredients at the corresponding positions in the recipes.

Dragon writes down each recipe on a separate sheet of paper and keeps all these sheets in a special box. Since that, we cannot know the maximum amongst all of the distances between the recipes. However, Dragon assures that maximum distance is the minimum possible.

You are given n descriptions of teas composed by Dragon. Your task is to calculate the minimum value of maximal distance between the recipes.

The first line contains integers n and m (2 ≤ n ≤ 1000, 1 ≤ m ≤ 30) — the number of recipes and the number of ingredients in each recipe.

Each of next n lines contains one recipe — the string of m lowercase latin letters. It is guaranteed that all recipes are different.

Print the single integer — minimum value of maximal distance between the recipes.

5 2
fb
ga
ef
dc
fd

2

Let us explain the sample above.

Suppose the first recipe (fb) is the recipe of the delicious tea. Easy to see that the distance between the first recipe and the second recipe (ga) is 1. Obviously, this distance is the minimum distance between any pair of recipes, and we can assume that the second recipe was prepared from the first.

The distance between the fourth recipe (dc) and the first recipe is 2; the distance between the fourth and the fifth recipes is the same. We can assume that Dragon prepared the fourth tea from the first tea, and then prepared the fifth tea from the fourth tea.

At last, the third recipe (ef) can be prepared from the fifth (fd); distance between these recipes is 2, too.

So, Dragon can compose all the recipes of tea, and when he prepares some recipe from another recipe, the distance does not exceed 2.