선거 개입

여러분의 대학에는 컴퓨터 과학만을 위한 새 건물이 반드시 필요하다. 학과에는 건물을 지을 돈이 있지만, 시의회가 새 건물의 건축 허가를 승인하지 않으려 한다. 안타까운 일이다!

다행히 시의회 선거가 곧 다가온다. 여러분은 컴퓨터 과학을 위한 이익 의회 정당(ICPC) 소속으로 그 선거에 출마하기로 했다. 시의회에서 과반 의석을 확보하면, 여러분과 같은 정당 동료들이 새 건물을 승인할 수 있다.

시의회 선거는 유권자가 배정된 여러 선거구에서 치러진다. 각 선거구는 의원 한 명을 선출한다. 각 정당은 선거구마다 후보 한 명을 내세우고, 모든 유권자는 한 표만 행사한다. 각 선거구에서 가장 많은 표를 얻은 후보가 의원으로 당선된다.

새 건물은 여러분과 정당 동료들에게 매우 중요하므로, 어떤 위험도 감수하고 싶지 않다. 시의회에서나 선거구 선거에서 동점이 나오면 무슨 일이 일어날지 아무도 모른다. 따라서 여러분의 목표는 시의회에서 완전한 과반, 즉 의원의 절반보다 엄격히 많은 의석을 확보하는 것이다. 또한 여러분이 승리했다고 보는 각 선거구에서 ICPC 후보는 다른 어떤 후보보다 엄격히 많은 표를 받아야 한다.

여러분과 ICPC 동료들은 선거를 정교하게 시뮬레이션했다. 그래서 각 선거구에서 각 후보에게 몇 명의 유권자가 투표할지 정확히 알고 있다. 아쉽게도 이 모델은 ICPC의 승리를 예측하지 못한다. 여기서 까다로운 질문이 나온다. 선거에서 이기려면 최소 몇 명의 유권자에게 매수해야 하는가? 유권자를 매수하면 그 유권자는 이전에 지지하던 정당(정교한 모델링 덕분에 여러분이 알고 있다)을 ICPC로 바꾼다. 투표할 생각이 없던 사람은 매수할 수 없다.

입력은 다음과 같다.

• 첫째 줄에 두 정수 w와 p (2 ≤ w, p ≤ 1 000)가 주어진다. w는 선거구의 수, p는 선거에 참여하는 정당의 수다. 정당은 1번부터 p번까지 번호가 붙고, ICPC는 1번 정당이다.
• w개의 줄이 각각 p개의 정수 v1, . . . , vp (각 i에 대해 0 ≤ vi ≤ 1 000)를 담고 있으며, 한 선거구의 예상 결과를 나타낸다. vi는 정당 i에 투표할 표의 수다.

각 선거구에는 유권자가 최소 한 명 있다. 즉, 선거구마다 모든 vi의 합은 항상 1 이상이다.

ICPC가 시의회에서 과반 의석을 차지하기 위해 매수해야 하는 유권자의 최소 수를 출력한다.