Hide

Problem N
King of Spades

“King of Spades” is a two-player card game which is played with an unconventionally large deck composed of standard playing cards. The game is set up by splitting the deck into two arbitrary piles, and then the cards from each pile are laid face-up in a line.

\includegraphics[width=0.4\textwidth ]{image}
Figure 1: Sample Input 1  (Images from Vector Playing Cards Library)

A player’s turn involves choosing a contiguous range of $1$ to $100$ cards from each line, and then removing the two ranges from the game. (If cards are removed from the middle of a line, the remaining two parts of the line are simply merged before the next player’s turn.) Points are scored based on the cards that are removed. The players alternate turns until at least one of the lines run out of cards, at which point the game ends. Whoever finishes with the most points is the winner.

On a given turn, if at least one King of Spades is chosen, then absolutely no points are earned. It must also be the case that the two chosen ranges are ‘similar’, or else no points are earned. Two ranges of cards are defined to be similar if and only if each suit and each rank is found in both ranges the same number of times. If the ranges are similar, then the number of points earned during that turn is equal to the sum of the values of all of the cards chosen. A numbered card is worth its stated value (e.g., $7$ is worth $7$ points), an Ace is worth $1$ point, and a face card (Jack, Queen, King) is worth $10$ points.

Due to the sheer number of possible card selections, it is not always easy for a player to find a high-scoring move, so you have been asked to help automate this process. Given an arrangement of cards in two lines, your task is to determine the maximum number of points that a player can earn on that turn.

For example, in the first sample input, a player can achieve a maximum score of $36$ by choosing the second and third cards in the first line and the third and fourth cards in the second line. These two ranges are similar since each contains one Jack and one $8$ (ranks), and each contains one Club and one Heart (suits).

Input

The first line of input contains two space-separated integers $n$ and $m$ $(1 \leq n, m \leq 100\, 000)$, the number of cards in each of the two piles. The second and third lines contain $n$ and $m$ space-separated cards, respectively, where each card is represented by two characters. The first character of a card denotes its rank and is from the set {$2$, $3$, $4$, $5$, $6$, $7$, $8$, $9$, T, J, Q, K, A}, where the letters T, J, Q, K, and A represent the Ten, Jack, Queen, King, and Ace, respectively. The second character of a card denotes its suit and is from the set {S, H, D, C}, representing Spades, Hearts, Diamonds, and Clubs, respectively.

Output

The output should contain a single number, indicating the maximum score that can be achieved on that turn.

Sample Input 1 Sample Output 1
3 5
5C JC 8H
2H KC 8C JH 8H
36
Sample Input 2 Sample Output 2
1 2
4S
2C AH
0
Sample Input 3 Sample Output 3
7 6
AC 2H 3D 4D 5C KS 6H
7C 8H KH 6S 9D QD
0

Please log in to submit a solution to this problem

Log in