게리맨더링

정치인은 당선을 위해서라면 거의 무엇이든 합니다. 특정 후보(당연히 경계를 다시 긋는 바로 그 사람)에게 유리하도록 선거구의 경계를 다시 긋는 것도 그중 하나이며, 이런 행위를 게리맨더링이라고 부릅니다. 이 문제에서는 간단한 형태의 선형 게리맨더링을 다룹니다.

$N$개의 선거구(riding)가 주어집니다($2 \le N \le 100000$). 각 선거구에서는 서로 다른 $p$개 정당($2 \le p \le 10$)의 후보가 경쟁합니다. 선거구들은 일렬로 나란히 놓여 있습니다. 양 끝의 두 선거구는 이웃이 하나뿐이고, 나머지 선거구는 모두 이웃이 둘입니다. 아래는 $N = 4$, $p = 2$인 예시입니다.

여기서 선거구 1과 2, 2와 3, 3과 4가 서로 이웃이며, 그 밖의 어떤 쌍도 이웃이 아닙니다.

경계를 정하는 담당자를 매수할 수 있습니다. 인접한 두 선거구를 하나로 합치는 데에는 정해진 비용이 듭니다. 두 선거구를 합치면 정당별로 득표수가 더해집니다(합쳐진 선거구에서 $i$번 정당의 득표수는 원래 두 선거구의 $i$번 정당 득표수의 합입니다). 합쳐진 선거구는 다시 합칠 수 있으므로, 연속한 선거구들의 어떤 묶음이든 하나의 선거구로 합칠 수 있습니다.

어떤 선거구에서 한 정당이 다른 모든 정당보다 득표수가 엄격히 많으면 그 정당이 그 선거구를 차지합니다(동점이면 아무도 차지하지 못합니다). 모든 합병이 끝난 뒤 선거구가 $Q$개 남았다고 합시다. 1번 정당(여러분의 정당!)이 이 $Q$개 중 적어도 $\lfloor Q/2 \rfloor + 1$개를 차지하면 과반을 확보한 것입니다.

한 번의 합병은 인접한 두 선거구를 하나로 합쳐 선거구 수를 하나 줄입니다. 1번 정당이 남은 선거구의 과반을 차지하도록 만들기 위해 필요한 최소 합병 횟수를 구하세요.

첫째 줄에 정수 $N$이 주어집니다. 둘째 줄에 정수 $p$가 주어집니다. 이어지는 $N$개의 줄에는 각각 공백 하나로 구분된 $p$개의 음이 아닌 정수가 주어집니다. 그중 $i$번째 줄은 $v_1\ v_2\ \dots\ v_p$이며, $v_j$는 $i$번 선거구에서 $j$번 정당이 받는 득표수입니다. 각 득표수는 최대 $10000$이고, 전체 득표수의 합은 $2,000,000,000$ 미만입니다.

정수 하나를 출력합니다. 1번 정당이 남은 선거구의 과반을 차지하기 위해 필요한 최소 합병 횟수입니다. 어떻게 합병하더라도 1번 정당이 과반을 차지할 수 없다면 $-1$을 출력합니다.