407302: GYM102757 G Locked Out

Memory Limit:256 MB Time Limit:1 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

G. Locked Outtime limit per test1 secondmemory limit per test256 megabytesinputstandard inputoutputstandard output

Gloria is a ravenous reader and has recently been enraptured by Shakespeare's 'Othello'. Lucky for her, this new time travel device provided her the perfect opportunity to go back in time to November 1, 1604, and watch her favorite play in person. Gloria dresses up in her finest Shakespearean-era attire and zooms back in time. To prevent the time travel machine from ending up in the wrong hands, each user is given a specific numeric password and a set of recovery codes in case they forget the password.

Gloria reaches the Whitehall Palace just in time for the show and after an enthralling three and a half hours, she returned to her time travel machine only to realize that she has forgotten her password! Luckily, she had the foresight to bring her tablet with the recovery codes on her. However, the effect of time travel on such electronics was unfortunately still not completely mitigated so some of the bits in the tablet got shifted around. Fortunately, Gloria knows that each of the recovery code numbers was rearranged in the exact same way and that her password is the smallest possible difference between the maximum recovery code and the minimum recovery code. Help Gloria recover her password!

That is, given the list of $$$n$$$ rearranged recovery codes, each of which is exactly $$$k$$$ digits, permute all of the numbers in the exact same way in order to get the minimum possible difference between the maximum and minimum recovery code after the permutation.

Input

The first line of the input will contain two space-separated integers, $$$n$$$ and $$$k$$$ (where $$$2 \leq n \leq 100$$$ and $$$1 \leq k \leq 9$$$).

$$$n$$$ lines of input will then follow, each line containing a single integer $$$x_i$$$ ($$$0 \leq x_i \leq 10^{k} - 1$$$) which will have exactly $$$k$$$ digits (the number can contain leading zeros).

Output

A single integer representing Gloria's password aka the minimum difference between the maximum and minimum recovery code after the permutation.

ExamplesInput
2 2
12
32
Output
2
Input
4 4
1842
0141
5581
1581
Output
1017

加入题单

上一题 下一题 算法标签: