Keyboard Game
Masha and Misha are engaged in an intriguing game. Each of them writes down a set of words, marking the conclusion of the first stage of the game. In the second stage, they take turns removing keys from a keyboard, each key corresponding to a Latin letter, with a total of l keys being removed. Afterward, they count how many of their words can still be typed using the remaining keys. The player with fewer words that can be typed loses and must give the opponent a number of candies equal to the difference in the number of typeable words.
The first stage of the game is complete, and Masha has the first move, either by chance or due to Misha's courtesy. Determine how many candies Masha can ensure for herself with optimal play from both sides.
Input
The first line of the input contains the number l - the number of keys that will be removed during the game (1 ≤ l ≤ 26). Following this, the sets of words for Masha and Misha are provided in the following format: one line contains the number of words, and the next line lists the words themselves, separated by spaces.
All words consist of lowercase Latin letters. Each player has written no more than 15 non-empty words, each word being no longer than 30 letters.
Output
Output a single integer representing Masha's gain with optimal play. If Masha is forced to lose, output her minimum loss with a minus sign.