가짜 뉴스 추적

가짜 뉴스는 소셜 네트워크를 타고 퍼진다. 누군가 내가 원래 믿던 생각과 들어맞는 이야기를 올리면, 나는 마음에 들지 않는 이야기를 볼 때보다 훨씬 덜 따져 보고 그대로 받아들인다. 그리고 그 이야기를 다시 올리면 내 친구들이 그것을 보게 된다. 입맛에 딱 맞는 이야기는 이렇게 순식간에 네트워크 전체로 번진다. 이 문제에서는 네트워크 구조와 각 사람의 성향, 이야기가 처음 올라온 위치를 알고 있을 때 가짜 뉴스가 퍼지는 과정을 시뮬레이션한다.

모형은 조금 비현실적이지만 단순하다. 사람들이 신경 쓰는 항목이 $r$개 있다. 이야기가 어느 정치 진영에 유리한지, 선정적인 내용이 얼마나 들어 있는지, 폭력적인 내용이 얼마나 들어 있는지 같은 항목이다. 사람 $j$에게는 항목 $i$마다 정수 가중치 $w_{j,i}$가 있고, 이 값은 양수일 수도 음수일 수도 있다. 또 전체 내용에 대한 정수 목표치 $t_j$가 있다. 이야기에도 항목마다 정수 내용값 $c_i$가 있다. 사람 $j$는 $\sum_{i=1}^{r} w_{j,i} c_i = t_j$일 때만 그 이야기를 마음에 들어 한다. 조건은 까다롭지만 계산은 쉽다. 마음에 들면 그 사람은 이야기를 다시 올리고, 그렇지 않으면 올리지 않는다. 모든 사람은 친구가 올린 이야기를 전부 보고, 친구가 아닌 사람이 올린 이야기는 친구가 다시 올리지 않는 한 보지 못한다.

가짜 뉴스는 언제나 1번 사람에게서 시작한다. 다만 1번 사람도 마음에 들지 않으면 올리지 않는다.

첫 줄에 입력에 들어 있는 데이터 집합의 개수 $K \ge 1$이 주어진다. 이어서 아래 형식의 데이터 집합이 $K$개 주어진다.

데이터 집합의 첫 줄에는 정수 $n$과 $r$이 주어진다. $1 \le n \le 1000$은 소셜 네트워크에 있는 사람 수이고, $1 \le r \le 100$은 이야기를 평가할 때 쓰는 항목 수이다.

다음 줄에는 정수 $c_1$부터 $c_r$까지 정확히 $r$개가 주어지며, 각 값은 $-100$ 이상 $100$ 이하이다.

그다음 $n$개의 줄에는 1번부터 $n$번까지 사람 $j$의 정보가 차례대로 주어진다. 한 줄의 처음 $r$개 수는 $w_{j,1}$부터 $w_{j,r}$까지이고, 각 값은 $-10$ 이상 $10$ 이하의 정수이다. 그다음 수는 $-1000000$ 이상 $1000000$ 이하의 정수 $t_j$이다. 그다음 수는 $j$의 친구 수 $d_j$이며 $0 \le d_j \le n - 1$이다. 이어서 $j$의 친구 번호가 $d_j$개 주어진다. 이 번호는 모두 서로 다르고, 1 이상 $n$ 이하이며, $j$와 같지 않다. 친구 관계는 언제나 양쪽이 같다. $j'$이 $j$의 친구이면 $j$도 $j'$의 친구이다.

가짜 뉴스는 언제나 1번 사람에게서 시작한다.

각 데이터 집합마다 먼저 "Data Set x:"를 한 줄에 출력한다. 여기서 x는 1부터 세는 데이터 집합 번호이다. 그다음 줄에는 더 이상 새로 올리는 사람이 없을 때까지 가짜 뉴스를 올린 사람의 총수를 출력한다. 각 데이터 집합 뒤에는 빈 줄을 하나 출력한다.