인구 이동

경제 수준이 크게 다른 두 나라가 하나로 합쳐지면 가난한 쪽에서 부유한 쪽으로 옮겨 가기가 쉬워진다. 이민 할당도 국경 검문도 사라지고 짐을 싸는 일만 남는다. 누가 떠날 때마다 남은 사람의 처지도 바뀐다. 물건을 팔 이웃이 한 명 줄지만 경쟁자도 한 명 준다. 여기서는 마을 하나를 두고 그 과정을 시뮬레이션한다.

주민은 저마다 한 가지 직종에서 일하고 그 일에 받을 값을 하나로 정해 둔다. 또 주민마다 직종 $m$가지 각각에 대해, 그 일을 남에게 맡길 때 낼 의향이 있는 최대 금액이 정해져 있다.

주민이 직종 $k$의 일을 살 때는 직종 $k$에서 일하는 마을 주민 가운데 자기가 낼 의향이 있는 금액 이하이면서 값을 가장 비싸게 받는 사람에게 맡긴다. 가장 싼 값을 찾는 것이 아니라 감당할 수 있는 범위에서 가장 좋은 일을 산다. 다음 두 경우에는 값을 치르지 않고 혼자 처리한다. 첫째, 그 직종에 낼 의향이 있는 금액이 0이면 언제나 혼자 처리한다. 둘째, 그 직종에서 일하면서 감당할 수 있는 값을 받는 주민이 마을에 없으면 혼자 처리한다.

자기 자신에게 일을 맡길 수 있고, 그 거래도 다른 거래와 똑같이 센다.

주민의 수입은 자기가 받는 값에 자기에게 일을 맡긴 주민 수를 곱한 값이다. 수입이 부유한 쪽에서 벌 수 있는 돈보다 적어지는 날 그 주민은 마을을 떠난다. 생활비는 부유한 쪽에서도 똑같이 드니 따지지 않는다. 같은 날 떠나기로 한 주민이 여럿이면 모두 한꺼번에 떠나고, 남은 주민은 다음 날 남아 있는 이웃만 보고 수입을 다시 계산한다. 한 번 떠난 주민은 예전 수입이 다시 넉넉해져도 돌아오지 않는다.

과정이 더 이상 바뀌지 않을 때 마을에 남은 주민 수를 세어라.

첫째 줄에 데이터 집합의 개수 $K$가 주어진다 ($K \ge 1$). 이어서 데이터 집합 $K$개가 아래 형식으로 주어진다.

각 데이터 집합의 첫째 줄에는 주민 수 $n$과 직종 수 $m$이 주어진다 ($0 \le n \le 1000$, $1 \le m \le 100$). 다음 $n$개 줄에는 주민 한 명을 나타내는 정수 $m + 3$개 $w_i$, $j_i$, $c_i$, $p_{i,1}$, $p_{i,2}$, ..., $p_{i,m}$이 주어진다. $w_i \ge 0$은 주민 $i$가 부유한 쪽에서 벌 수 있는 돈, $1 \le j_i \le m$은 그가 일하는 직종, $c_i \ge 0$은 그가 자기 일에 받는 값이다. $p_{i,k} \ge 0$은 주민 $i$가 직종 $k$의 일을 맡길 때 낼 의향이 있는 최대 금액이고, 이 값이 0이면 주민 $i$는 직종 $k$를 언제나 혼자 처리한다.

같은 직종에서 같은 값을 받는 주민은 없다. 즉 $i \ne i'$이고 $j_i = j_{i'}$이면 $c_i \ne c_{i'}$이다.

데이터 집합마다 먼저 Data Set x:를 한 줄에 출력한다. $x$는 1부터 세는 데이터 집합 번호이다. 다음 줄에 과정이 끝났을 때 마을에 남은 주민 수를 출력한다. 데이터 집합마다 그 뒤에 빈 줄을 하나 출력한다.