배정 최적화

회사 <<QQQ>>에는 $n$명의 직원이 있다. 이 회사의 새 프로젝트는 $m$개의 독립적인 부분으로 이루어져 있다. 관리자는 프로젝트의 각 부분을 수행하는 데 필요한 시간을 측정했다(이 시간은 그 부분을 누가 수행하든 변하지 않는다). 그런 다음 $m$개의 부분을 $n$명의 직원에게 적당히 배정했다. 그 결과 일부 직원은 다른 직원보다 업무를 수행하는 데 더 많은 시간을 써야 한다(더 많은 일을 맡았기 때문이다).

그래서 관리자는 업무 배정을 다음과 같이 개선하기로 했다. 서로 다른 두 직원을 고르고, 첫 번째 직원에게 배정된 프로젝트의 한 부분과 두 번째 직원에게 배정된 한 부분을 고른다. 그런 다음 첫 번째 직원에게 배정된 부분은 두 번째 직원에게, 두 번째 직원에게 배정된 부분은 첫 번째 직원에게 배정한다. 이 작업의 결과로 첫 번째 직원과 두 번째 직원의 업무 수행 시간의 최댓값이 줄어들면, 이 작업을 최적화 작업이라고 부른다.

예를 들어 프로젝트가 수행 시간 $3, 6, 4, 8, 2$인 다섯 부분으로 이루어져 있고 회사에 세 명의 직원이 있다고 하자. 배정이 다음과 같다고 하자. 첫 번째 직원은 부분 $1$과 $2$ (총 시간 $3 + 6 = 9$), 두 번째 직원은 부분 $4$ (총 시간 $8$), 세 번째 직원은 부분 $3$과 $5$ (총 시간 $4 + 2 = 6$). 이때 첫 번째 직원에게 배정된 첫 번째 일을 세 번째 직원에게, 세 번째 직원에게 배정된 다섯 번째 일을 첫 번째 직원에게 배정하면 첫 번째 직원의 총 시간은 $6 + 2 = 8$, 세 번째 직원의 총 시간은 $3 + 4 = 7$이 된다. $\max(9, 6) > \max(8, 7)$이므로 이 작업은 최적화 작업이다.

회사의 직원 수, 프로젝트의 부분 수, 각 부분을 수행하는 데 필요한 시간, 부분의 직원별 배정이 주어진다. 주어진 배정에서 가능한 서로 다른 최적화 작업의 수를 구해야 한다.

첫째 줄에는 두 자연수 $n$과 $m$ ($1 \le n, m \le 10^5$)이 주어진다. $n$은 회사의 직원 수, $m$은 프로젝트의 부분 수다. 둘째 줄에는 $m$개의 자연수가 주어지며, $i$번째 수는 $i$번째 부분을 수행하는 데 필요한 시간이다(부분은 $1$번부터 번호가 매겨진다). 부분의 수행 시간은 $10^9$을 넘지 않는다. 다음 $n$개의 줄에는 부분의 직원별 배정이 주어진다. 각 줄에는 해당 직원이 받은 부분의 수와 그 번호가 주어진다.

최적화 작업의 수를 출력한다.

두 번째 예에서는 어떤 작업이든 최적화 작업이다.