만드는 중입니다

아직 만드는 중이라 바뀔 수 있습니다

균일한 깃발 만들기

면접 대비

시간 제한1초메모리 제한1024 MB

요약
길이가 같은 N개의 단어를 모두 같은 단어로 만들 때 필요한 글자 변경 횟수의 최솟값을 구합니다.
난이도

쉬움10점 중 3점

유형
그리디, 문자열, 해시맵
정답자
아직 제출이 없습니다

문제

국제 의상 및 소품 회사(ICPC)는 같은 단어가 적힌 깃발 NN개를 만들어 달라는 주문을 고객에게 받았다. 담당자와 고객 사이에 착오가 있어서 모든 깃발에 같은 단어가 적혀 있지 않다. 다만 모든 단어의 길이는 같다. ICPC는 희귀한 원단만 쓰기 때문에 깃발을 다시 만드는 데 비용이 많이 든다.

고객은 원하는 단어를 정하지 않았다. 고객은 모든 깃발에 같은 단어가 적혀 있을 때만 만족한다.

ICPC는 단어의 한 글자를 다른 글자로 바꿀 수 있다. 이 작업은 비싸지만 깃발을 새로 만드는 것보다는 싸다. ICPC는 이 작업을 최소한으로 쓰고 싶다. 고객을 만족시키려면 바꿔야 하는 글자 수의 합이 최소가 되도록 구하라.

예를 들어 calf, palm, book, icpc, ball, room 여섯 단어를 모두 balm으로 바꾸면 전체 14글자를 바꾸면 된다. 이 단어 조합에서 이보다 적은 경우는 없다.

입력

첫째 줄에 두 정수 NN과 MM이 주어진다(2≤N≤1002 \le N \le 100, 1≤M≤1001 \le M \le 100). NN은 깃발의 개수이고, MM은 각 단어의 길이다. 다음 NN개 줄에는 ii번째 깃발의 단어 SiS_i가 한 줄에 하나씩 주어진다(∣Si∣=M|S_i| = M). 모든 문자열은 소문자 알파벳으로만 이루어져 있다.

출력

모든 깃발의 단어를 같게 만들기 위해 바꿔야 하는 글자 수의 합의 최솟값을 한 줄에 정수로 출력한다.

예제3

  1. 예제 1

    입력
    6 4
    calf
    palm
    book
    icpc
    ball
    room
    
    예상 출력
    14
    
  2. 예제 2

    입력
    3 11
    goodluckfor
    icpcjakarta
    contestants
    
    예상 출력
    19
    
  3. 예제 3

    입력
    5 14
    helpiamtrapped
    inanincfactory
    forthreemonths
    withoutfoodand
    drinkandshower
    
    예상 출력
    49