Pencil Crayons

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

요약
각 상자에 K개의 크레용이 담긴 N개의 상자가 있을 때, 빼낸 크레용을 다시 나눠 모든 상자가 K가지 색을 모두 갖추도록 하는 최소 제거 개수를 구한다.
난이도

보통10점 중 5점

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

문제

Mr. Daniels bought a set of NN identical boxes of pencil crayons for his classroom, each containing the same set of KK distinct colours of pencils. Over the course of the year, the pencil crayons got mixed up between the boxes. Surprisingly, none of them have been lost (yet). But some boxes may not have KK distinct colours any more.

Mr. Daniels has a gap in his schedule and the break room is currently undergoing maintenance. He might as well rearrange the pencil crayons so each box again has exactly KK distinct colours. To do this, he will first remove a number of pencil crayons from each box (perhaps 00) and then place the removed pencil crayons back in boxes.

Help Mr. Daniels figure out the minimum number of pencil crayons that need to be removed so that he can place them back in boxes to ensure each box again has KK distinct colours of pencil crayons. The order the pencil crayons are arranged in a box does not matter, just that all KK colours are now present in each box.

입력

The first line of input contains two integers NN (2≤N≤1002≤N≤100) and KK (2≤K≤1002≤K≤100). Then NN lines follow. Each line describes the contents of a box by listing KK strings describing the pencil crayons that are currently found in that box.

Each string describing a colour will have a length between 11 and 1010 and will only contain lowercase letters. There will be exactly KK distinct strings appearing among all rows describing the boxes and each such string will appear exactly NN times.

출력

Output a single number indicating the fewest pencil crayons that need to be removed from all boxes so that Mr. Daniels can place them back in the boxes while ensuring each box has exactly KK distinct colours.

예제4

  1. 예제 1

    입력
    2 3
    red blue red
    green green blue
    
    예상 출력
    2
    
  2. 예제 2

    입력
    3 2
    orange white
    orange orange
    white white
    
    예상 출력
    2
    
  3. 예제 3

    입력
    2 2
    aubergine chartreuse
    chartreuse aubergine
    
    예상 출력
    0
    
  4. 예제 4

    입력
    4 3
    a a a
    b c c
    c b a
    b b c
    
    예상 출력
    4