Hide

Problem D
Double Deck

Languages en is
/problems/doubledeck/file/statement/en/img-0001.jpeg
Image taken from wikimedia.org.
You are playing a new card game. In the game you have two decks of cards each consisting of $N \cdot K$ cards labeled with an integer from $1$ to $N$, inclusive. Also, each type of card appears precisely $K$ times in each deck.

The rules of the game are simple. You shuffle both decks and place them face up in front of you, so at each point in time you see the top card in each deck. If the top cards are the same you can take them both and get one point. Otherwise you must discard either card. Your goal is to get as many points as possible.

You have just finished playing a round of this game and you want to know what the maximum score was, knowing the layout of both decks.

Input

The first line of the input contains two integers $N$ and $K$ ($1 \leq N \leq 10^4, 1 \leq K \leq 15$). The second and third line of the input each contain $N \cdot K$ integers $x_i$ ($1 \leq x_i \leq N$), describing the layout of the decks. The first number $x_1$ is the topmost card in the deck, $x_2$ is the second, and so on.

No integer in the second line and third line is repeated more than $K$ times per line.

Output

Print a single integer, the maximum possible score.

Sample Input 1 Sample Output 1
3 2
3 1 2 3 1 2
2 1 3 1 3 2
4
Sample Input 2 Sample Output 2
5 3
2 3 4 5 3 5 2 2 4 3 5 1 1 1 4
5 2 3 2 3 1 4 5 1 4 5 1 4 3 2
8

Please log in to submit a solution to this problem

Log in