This page is still under construction.

Parts of this page are still being built. What you see may change.

Opening Ceremony

Time limit2sMemory limit512 MB

Summary
For each data set, count how many athletes from each country marched, then report the largest shortfall against that country's registered total.
Level

Easy2 of 10

Topics
Array, Implementation, Simulation
Solved
No attempts yet

Problem

The Olympic games start with an opening ceremony. The athletes of every participating country march around the main stadium. A country normally marches as one bloc, so the organizers can see at a glance which country has the most athletes missing. Call an athlete who registered but skipped the ceremony to train instead a delinquent.

At this ceremony the athletes marched mixed together, in no country order. Counting now means reading every jersey and keeping a separate tally per country.

You are given how many athletes each country registered, followed by the country of every athlete who marched, in order. Find the largest number of delinquents of any country.

Input

The first line contains the number of data sets KK, with K≥1K \ge 1. Then follow KK data sets in this format.

The first line of a data set contains two integers cc and nn. Here cc is the number of participating countries with 1≤c≤10001 \le c \le 1000, and nn is the number of athletes who marched in the ceremony with 0≤n≤100000 \le n \le 10000.

The next line contains cc integers m1,m2,…,mcm_1, m_2, \dots, m_c. Here mim_i is the number of athletes registered for country ii, with mi≥0m_i \ge 0.

The next line contains nn integers b1,b2,…,bnb_1, b_2, \dots, b_n. Here bjb_j is the country of the jj-th athlete who marched, with 1≤bj≤c1 \le b_j \le c. This line is empty when nn is 0. No country ii ever sends more than mim_i athletes to the ceremony.

Output

For each data set, first print Data Set x: on a line by itself, where xx is the number of the data set counting from 1. On the next line print the largest number of delinquents of any country in that data set.

Print a blank line after each data set.

Examples1

  1. Example 1

    Input
    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
    
    Expected output
    Data Set 1:
    2
    
    Data Set 2:
    9