Problem D
Double Deck
Languages
en
is
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 |