Under construction

Still being built. Things may change

Uniform Maker

Interview

Time limit1sMemory limit1024 MB

Summary
Given N words of equal length, find the total minimum number of character changes needed to make all words identical.
Level

Easy3 of 10

Topics
Greedy, String, Hash map
Solved
No attempts yet

Problem

The International Costumes and Props Company (ICPC) received an order from a client to produce NN pennants that each contain the same word. Because of a miscommunication between the account manager and the client, the pennants do not all show the same word, although every word has the same length. Reproducing the pennants is costly because ICPC only uses a rare type of fabric.

The client did not specify the word. The client is satisfied only if all pennants show the same word.

ICPC can change one character in a word into another character. This is expensive, but cheaper than making a new pennant. ICPC wants to minimize how many times it uses this technique. Find the minimum total number of characters that must be changed so that the client is satisfied.

For example, take the six words calf, palm, book, icpc, ball, and room. Changing all of them to balm needs 14 character changes in total, which is the minimum for this set.

Input

The first line contains two integers NN and MM (2≤N≤1002 \le N \le 100, 1≤M≤1001 \le M \le 100), the number of pennants and the length of each word. Each of the next NN lines contains a string SiS_i with ∣Si∣=M|S_i| = M, the word on the ii-th pennant. Every string contains only lowercase English letters.

Output

Print one integer on a line: the minimum total number of characters that must be changed so that all pennants show the same word.

Examples3

  1. Example 1

    Input
    6 4
    calf
    palm
    book
    icpc
    ball
    room
    
    Expected output
    14
    
  2. Example 2

    Input
    3 11
    goodluckfor
    icpcjakarta
    contestants
    
    Expected output
    19
    
  3. Example 3

    Input
    5 14
    helpiamtrapped
    inanincfactory
    forthreemonths
    withoutfoodand
    drinkandshower
    
    Expected output
    49