Problem Description

She walks in beauty, like the night of cloudless climes and starry skies. And all that's best of dark and bright, meet in her aspect and her eyes. Thus mellow'd to that tender light, which heaven to gaudy day denies. Fang Fang says she is afraid of dark.

``Never fear, I will hold your hand," I reply.

Fang Fang says she hates some $8$-digit binary numbers.
I ask Cupid for help. Cupid can sell me some supernatural powers.
Some of them can eliminate all $8$-digit binary numbers in the world with a certain prefix, and some of them can eliminate all $8$-dight binary numbers with a certain suffix.

``..., but you must offer your IQ in exchange for them."

``You have my permission", I say. True, I should minimize my damage, but maybe you can help me.

Input

The input contains several test cases. The first line of the input is a single integer $t~(t\le 10)$ which is the number of test cases.

Then $t$ test cases follow.
Each test case contains several lines.
The first line contains the integer $n~(1\le n\le 256)$ and $m~(1\le m\le 500)$.
Here, $n$ corresponds to the number of $8$-digit binary numbers which Fang Fang hates, and $m$ corresponds to the number of supernatural powers.
The second line contains $n$ integer numbers $a_1,a_2,\cdots,a_n$ where $0\le a_1,\cdots,a_n\le 255$, which are $8$-digit binary numbers written by decimal representation.
The following $m$ lines describe the supernatural powers one per line in two formats.
$\cdot$ $P~s~w$: you can eliminate all $8$-digit binary numbers by prefixing the string $s$, with $w~(1\le w\le 1000)$ units of IQ.
$\cdot$ $S~s~w$: you can eliminate all $8$-digit binary numbers by suffixing the string $s$, with $w~(1\le w\le 1000)$ units of IQ.

Output

For each test case, you should output the minimum cost of IQ as a unit, or ``-1" if Cupid could not help me.

1
8 7
0 1 2 3 4 5 6 7
P 000001 1
P 0000000 1
S 10 1
S 11 1
S 00 1
S 01 1
P 0000001 3

Case #1: 4