개회식

시간 제한2초메모리 제한512 MB

요약

각 데이터 세트에서 나라별로 행진한 선수 수를 세고, 등록 인원과의 차이가 가장 큰 나라의 결석자 수를 출력한다.

난이도: 쉬움10점 중 2점
유형: 배열, 구현, 시뮬레이션
정답자: 아직 제출이 없습니다

문제

올림픽은 개회식으로 시작한다. 개회식에서는 참가국 선수단이 주경기장을 행진한다. 보통은 나라별로 한 덩어리를 이루어 행진하기 때문에, 어느 나라에 빠진 선수가 많은지 주최 측이 한눈에 알아본다. 등록만 해 놓고 개회식에 나오지 않고 훈련을 택한 선수를 불참 선수라고 하자.

이번 개회식에서는 선수가 나라와 상관없이 뒤섞여 행진했다. 그래서 유니폼을 보고 나라별로 일일이 세어야 한다.

나라별 등록 선수 수와 개회식에서 행진한 선수의 소속 국가가 순서대로 주어진다. 불참 선수가 가장 많은 나라의 불참 선수 수를 구하라.

입력

첫 줄에 데이터 세트의 개수 $K$ 가 주어진다. $K \ge 1$ 이다. 이어서 $K$ 개의 데이터 세트가 다음 형식으로 주어진다.

각 데이터 세트의 첫 줄에는 두 정수 $c$ 와 $n$ 이 주어진다. $c$ 는 참가국 수로 $1 \le c \le 1000$ 이고, $n$ 은 개회식에서 행진한 선수 수로 $0 \le n \le 10000$ 이다.

다음 줄에는 정수 $c$ 개 $m_1, m_2, \dots, m_c$ 가 주어진다. $m_i$ 는 $i$ 번 나라에 등록된 선수 수이고 $m_i \ge 0$ 이다.

그다음 줄에는 정수 $n$ 개 $b_1, b_2, \dots, b_n$ 이 주어진다. $b_j$ 는 개회식에서 $j$ 번째로 행진한 선수의 소속 국가이고 $1 \le b_j \le c$ 이다. $n$ 이 0이면 이 줄은 비어 있다. 어떤 나라 $i$ 에 대해서도 행진한 선수가 $m_i$ 명을 넘지 않는다.

출력

각 데이터 세트마다 먼저 Data Set x:를 한 줄에 출력한다. $x$ 는 데이터 세트의 번호이고 1부터 센다. 다음 줄에 그 데이터 세트에서 불참 선수가 가장 많은 나라의 불참 선수 수를 출력한다.

각 데이터 세트 뒤에 빈 줄을 하나 출력한다.

예제1

예제 1

입력

2
3 8
5 5 2
1 2 1 2 1 2 1 2
5 6
10 10 10 10 10
1 2 4 5 3 1

예상 출력

Data Set 1:
2

Data Set 2:
9