Card Trade

Interview

Time limit2sMemory limit512 MB

Summary

Given two sorted card piles, find the largest N such that Alice and Beatriz can each give away N cards of distinct kinds that the other does not own.

Level: Easy3 of 10
Topics: Two pointers, Array, Hash map
Solved: No attempts yet

Problem

Alice and Beatriz collect Pokemon cards. There is a battle game played with these cards, but the two girls are still small, so they do not play it and care only about the cards themselves. Each card carries one integer number, and two cards with the same number count as the same kind.

Each girl owns a pile of cards, and the two want to trade with each other. Two rules apply. A kind of card that both of them already own is never traded. Also, the cards a girl receives in the trade must not contain the same kind twice. The trade happens in a single operation: Alice hands Beatriz $N$ cards of pairwise different kinds, and Beatriz hands Alice $N$ cards of pairwise different kinds.

Write a program that finds the largest $N$ the two girls can trade.

Input

The input holds several test cases. The first line of a test case holds the number of cards Alice owns, $A$ , and the number of cards Beatriz owns, $B$ , separated by one space ( $1 \le A \le 10^4$ , $1 \le B \le 10^4$ ). The second line holds the numbers of Alice's cards, $A$ integers $X_i$ separated by spaces ( $1 \le X_i \le 10^5$ ). The third line holds the numbers of Beatriz's cards, $B$ integers $Y_i$ separated by spaces ( $1 \le Y_i \le 10^5$ ). Each girl's card numbers are given in non-decreasing order.

The last line of the input holds two zeros separated by one space. That line is not a test case.

Output

For each test case print one line with the largest number of cards Alice and Beatriz can trade with each other.

Examples1

Example 1

Input

1 1
1000
1000
3 4
1 3 5
2 4 6 8
10 9
1 1 2 3 5 7 8 8 9 15
2 2 2 3 4 6 10 11 11
0 0

Expected output

0
3
4