Tools of the Trade

King Theoden pulled his people back into Helm's Deep to meet the raids on his land and the threat from Saruman. The armory does not hold enough weapons of each type to give every soldier the weapon they handle best, so the quartermaster has to hand out the stock in the way that leaves the army fighting as well as it can.

Every soldier has a ranking of all $N$ weapon types, written from the weapon that soldier handles best to the one they handle worst. A soldier who receives the weapon in position $k$ of their own ranking adds $k$ to the total inexperience, where the best weapon sits at position $0$. A soldier whose ranking is ABCD adds $2$ when given C and $1$ when given B. Each soldier receives exactly one weapon, and a weapon type can be handed out at most as many times as the armory holds copies of it. Find the smallest total inexperience.

The first line holds the number of test cases, which is at most $20$.

The first line of each test case holds the number of weapon types $N$ and the number of soldiers $M$ ($1 \le N \le 26$, $1 \le M \le 200$).

The next $N$ lines each hold a character $C$ and an integer $T$. $C$ is the uppercase letter that stands for a weapon type, and $T$ is the number of copies in the armory ($1 \le T \le 1000$). The $N$ letters are distinct.

The next $M$ lines each hold one soldier's ranking, a string of all $N$ weapon letters written from the weapon that soldier handles best to the one they handle worst.

The armory always holds at least $M$ weapons in total, so every soldier can be armed. The sum of $M$ over all test cases is at most $1000$.

For each test case, print the smallest total inexperience on its own line.