{"raw_statement":[{"iden":"statement","content":"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.\n\nDragon 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.\n\nDragon 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. \n\nDragon 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. \n\nWhen 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. \n\nDragon 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. \n\nYou are given n descriptions of teas composed by Dragon. Your task is to calculate the minimum value of maximal distance between the recipes.\n\nThe 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. \n\nEach of next n lines contains one recipe — the string of m lowercase latin letters. It is guaranteed that all recipes are different.\n\nPrint the single integer — minimum value of maximal distance between the recipes.\n\nLet us explain the sample above. \n\nSuppose 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.\n\nThe 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. \n\nAt last, the third recipe (ef) can be prepared from the fifth (fd); distance between these recipes is 2, too.\n\nSo, Dragon can compose all the recipes of tea, and when he prepares some recipe from another recipe, the distance does not exceed 2. \n\n"},{"iden":"input","content":"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."},{"iden":"output","content":"Print the single integer — minimum value of maximal distance between the recipes."},{"iden":"examples","content":"Input5 2fbgaefdcfdOutput2"},{"iden":"note","content":"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. "}],"translated_statement":null,"sample_group":[],"show_order":[],"formal_statement":"**Definitions**  \nLet $ n, m \\in \\mathbb{Z} $ with $ 2 \\leq n \\leq 1000 $, $ 1 \\leq m \\leq 30 $.  \nLet $ R = \\{r_1, r_2, \\dots, r_n\\} $ be a set of $ n $ distinct recipes, where each $ r_i \\in \\Sigma^m $, $ \\Sigma = \\{a, b, \\dots, z\\} $, is a string of length $ m $ over lowercase Latin letters.\n\nDefine the **distance** between two recipes $ r_i, r_j $ as:  \n$$\nd(r_i, r_j) = \\max_{k=1}^{m} | \\text{ord}(r_{i,k}) - \\text{ord}(r_{j,k}) |\n$$  \nwhere $ \\text{ord}(c) $ is the alphabetical position of letter $ c $ (e.g., $ \\text{ord}(a) = 0, \\text{ord}(b) = 1, \\dots, \\text{ord}(z) = 25 $).\n\nDefine a **labeling** as a bijection $ f: \\Sigma \\to \\{0, 1, \\dots, 25\\} $ assigning distinct integer labels to letters (i.e., a permutation of $ \\{0,1,\\dots,25\\} $).\n\nFor a labeling $ f $, define the distance between recipes under $ f $:  \n$$\nd_f(r_i, r_j) = \\max_{k=1}^{m} |f(r_{i,k}) - f(r_{j,k})|\n$$\n\n**Constraints**  \n1. All recipes in $ R $ are distinct.  \n2. The labeling $ f $ must be a bijection from the set of letters appearing in $ R $ to a subset of $ \\{0,1,\\dots,25\\} $ of size equal to the number of distinct letters in $ R $, extendable to a full bijection on $ \\Sigma $.\n\n**Objective**  \nFind the minimum possible value of the maximum pairwise distance over all labelings:  \n$$\n\\min_{f} \\left( \\max_{1 \\leq i < j \\leq n} d_f(r_i, r_j) \\right)\n$$","simple_statement":"You are given n strings, each of length m, representing tea recipes using lowercase letters. Each letter represents a different ingredient. The distance between two recipes is the maximum absolute difference between the positions of corresponding letters in the alphabet (e.g., |'f' - 'b'| = 4). \n\nDragon created all recipes by starting from one and making small changes — each new recipe differs from a previous one by changing some letters, and the distance between any two consecutive recipes is at most some value D. You want to find the smallest possible D such that all recipes can be connected in a sequence where each step has distance ≤ D.\n\nFind the minimum possible value of the maximum distance between any two consecutive recipes in such a sequence.","has_page_source":false}