문제
휘준이는 정올 공부를 언제 어디서나 하기 위해서 이번에 어머니께 노트북을 사달라고 이야기를 하였고, 어머니 역시 휘준이에게 노트북이 필요하다고 생각을 하여 노트북을 사는 것을 허락하였다. 신나는 마음에 근처에 있는 전자제품 매장인 안녕마트에 달려가 가지고 싶은 제품을 결정하고 부모님께 말씀을 드리고자 하려는 도중, 문제가 생겼다.
어머니는 매월 발간되는 어느 컴퓨터 잡지의 애독자인데, 그 잡지에는 여러 가지의 평가 기준을 정해서 최근 판매되고 있는 노트북들의 순위를 매기는 코너가 있다. 각 평가 기준에 대해서 각 제품들은 1점~9점 사이의 점수를 받게 되며, 각 평가 기준에 대해 가중치가 있으며(평가기준의 수와 각 평가기준의 가중치는 매번 달라질 수 있다!), 총 점수는 각 항목의 (가중치) * (평가기준) 들의 합이며, 총 점수가 높을수록 높은 순위를 받게 된다. 이번 달에 그 잡지의 코너엔 다음과 같이 적혀 있었다.
휘준이의 어머니는 그 잡지의 평가를 절대적으로 신뢰하는 사람이기 때문에 이 대로면 "샘송-SELLS" 노트북을 사주려고 할 것이다. 하지만 휘준이는 "엘기-YNOTE"를 가지고 싶어 하지만, 문제는 위의 점수 대로면 살수가 없다. 따라서 휘준이는 어머니가 잡지를 보시기 전에 몰래 잡지의 숫자들을 고쳐서 "엘기-YNOTE"가 가장 좋은 점수를 받고, 이와 동일한 점수가 하나도 없게 하고자 한다. 단, 너무 많은 숫자를 바꿀 경우 쉽게 탄로 날 수 있고 노트북을 사주시지 않을 수 있기 때문에, 숫자를 바꾸는 횟수를 최소화 해야 한다.
잡지의 숫자를 고치는 방법은 다음과 같다. · 각 평가 항목의 가중치에 1을 빼거나 더한다. 각 항목에 대해서 최대 한번 가능하며, 만약 더하고 빼낸 숫자의 결과가 1보다 작거나 9보다 클 수 없다. · 각 제품에 대해 평가항목들에 대한 점수에 1을 빼거나 더한다. 이 역시 각 숫자에 대해 최대 한번만 가능하며, 만약 더하고 빼낸 숫자가 1보다 작거나 9보다 클 수 없다.
다시 위의 표로 돌아가서, "엘기-YNOTE"가 최고점을 받게 바꾸려고 할 때, 가격에 대한 점수를 5에서 6으로 올리고, "샘송-SELLS"의 배터리 효율에 대한 점수를 5에서 4로 내리면, "엘기-YNOTE"의 점수는 33이 되고, "샘송-SELLS"의 점수는 32가 되어 "엘기-YNOTE"가 가장 좋은 점수를 얻게 되고 원하는 노트북을 살 수 있게 된다.
노트북에 대한 평가 항목에 대한 가중치와 각 제품의 평가항목들이 주어지고, 휘준이가 구매하려는 노트북이 어떤 것인지 주어질 때, 바꿔야 하는 최소의 숫자 수를 출력하는 프로그램을 작성하라.
입력
입력의 첫 줄에는 잡지에 기재된 노트북의 숫자 N, 평가 항목의 수 M, 그리고 휘준이가 사고자 하는 제품의 번호 D가 입력된다(2≤N≤10, 2≤M≤10, 0≤D그 다음 줄에는 M개의 평가항목의 가중치가 입력되며, 맨 앞에 입력된 숫자는 0번째 평가 항목의 가중치이고, 맨 뒤에 입력된 숫자는 M-1번째 평가 항목의 가중치이다.
각 숫자는 1 이상 9 이하의 정수이며 숫자 사이에 공백이 존재하지 않음을 유의하라. 그리고 N개의 줄에는 M개의 숫자가 입력된다. 맨 처음은 0번째 노트북의 평가 결과, 다음 줄은 1번째 노트북의 평가 결과, ... , 마지막은 N-1번째 노트북의 평가 결과이다. 휘준이는 여기서 D번째 노트북을 사려고 하는 것이다. 그리고 각 줄마다 맨 앞에 입력된 숫자는 0번째 평가 항목에 평가 결과, 다음은 1번째 평가 항목에 대한 평가 결과, ..., 마지막은 M-1번째 평가 항목에 대한 평과 결과이다. 각 숫자는 1 이상 9 이하의 정수이며, 이 역시 숫자 사이에 공백은 존재하지 않는다.
출력
입력에 대해서 휘준이가 사고자 하는 D번 노트북을 사기 위해 바꿔야 하는 숫자의 최소 수를 출력하라. 만약 그런 경우가 존재하지 않을 경우 -1을 출력한다.
예제
3 4 2
3211
6354
5532
4626
1
로그인해야 코드를 작성할 수 있어요.