최고의 맛집을 찾아서

면접 대비

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

요약

N명이 M개 식당에 매긴 1점부터 5점까지의 별점이 주어질 때, 각 식당이 최고의 맛집이 되도록 만드는 최소 별점 조작 횟수를 구한다.

문제

진흥이가 사는 동네에는 $1$ 번부터 $M$ 번까지 총 $M$ 개의 식당이 있습니다. 진흥이를 포함한 $N$ 명의 친구들은 각 식당의 음식 맛을 $1$ 점부터 $5$ 점까지의 별점으로 평가했습니다.

이제 이 평가를 바탕으로 최고의 맛집을 정하려고 합니다. 어떤 식당이 최고의 맛집이 되려면 모든 친구에 대해, 그 친구가 해당 식당보다 더 높은 점수를 준 다른 식당이 없어야 합니다.

예를 들어, 어떤 친구가 $1$ 번 식당에는 $4$ 점을, $2$ 번 식당에는 $5$ 점을 줬다면 그 친구의 기준에서 $1$ 번 식당은 최고의 맛집이 될 수 없습니다. 왜냐하면 더 높은 점수를 받은 $2$ 번 식당이 존재하기 때문입니다.

하지만 이러한 조건을 만족하는 식당이 하나도 없을 수도 있습니다. 따라서 진흥이는 친구들이 준 별점을 일부 조작해서라도, 모든 식당이 최고의 맛집이 될 수 있도록 만들고자 합니다.

별점 조작은 한 친구가 어떤 식당에 준 점수를 다른 점수로 바꾸는 것을 의미합니다.

각 식당이 최고의 맛집이 되기 위해 필요한 최소 별점 조작 횟수를 구하세요.

첫 번째 줄에 양의 정수 $N$ 과 $M$ 이 공백으로 구분되어 주어집니다.

다음 $N$ 개의 줄에는 각 사람이 $1$ 번 식당부터 $N$ 번 식당까지 매긴 별점이 공백으로 구분되어 주어집니다. 각 별점은 $1$ 이상 $5$ 이하의 정수입니다.

$M$ 개의 정수를 공백으로 구분하여 한 줄에 출력합니다. 이때 $i$ 번째 정수는 $i$ 번 식당이 최고의 맛집이 되기 위해 필요한 최소 별점 조작 횟수를 의미합니다.