Problem Description

You are trying to purchase $ N $ types of components, component $1,\ \ldots,\ N$, to make something. While searching an online shopping site, you found $ M $ sets of components for sale.

The information for the $ i $-th set sale $(1\ \leqq\ i\ \leqq\ M)$ is given as a pair of a string $ S_i $ of length $ N $ and an integer $ C_i $. The $ j $-th character of $ S_i $ $(1\ \leqq\ j\ \leqq\ N)$ is Y if this set includes component $ j $, and N if it does not. This set is sold for $ C_i $ yen.

Create a program that determines the amount of money needed to purchase some of these sets to obtain at least one of each of the $ N $ types of components (or reports that it is impossible).

Input Format

The input is given from the standard input in the following format:

$ N $ $ M $ $ S_1 $ $ C_1 $ $ S_2 $ $ C_2 $ $ : $ $ S_M $ $ C_M $

Output Format

If it is possible to obtain all components, output the integer representing the minimum amount of money needed.

Otherwise, output -1.

Sample Input and Output

Sample Input #1

3 4
YYY 100
YYN 20
YNY 10
NYY 25

Sample Output #1

30

Sample Input #2

5 4
YNNNN 10
NYNNN 10
NNYNN 10
NNNYN 10

Sample Output #2

-1

Sample Input #3

10 14
YNNYNNNYYN 774472905
YYNNNNNYYY 75967554
NNNNNNNNNN 829389188
NNNNYYNNNN 157257407
YNNYNNYNNN 233604939
NYYNNNNNYY 40099278
NNNNYNNNNN 599672237
NNNYNNNNYY 511018842
NNNYNNYNYN 883299962
NNNNNNNNYN 883093359
NNNNNYNYNY 54742561
NYNNYYYNNY 386272705
NNNNYYNNNN 565075143
NNYNYNNNYN 123300589

Sample Output #3

451747367

Notes/Hints

Constraints

• $1\ \leqq\ N\ \leqq\ 10$
• $1\ \leqq\ M\ \leqq\ 1,000$
• $ S_i $ is a string of length $ N $.
• Each character of $ S_i $ is either Y or N.
• $1\ \leqq\ C_i\ \leqq\ 1,000,000,000$
• $ C_i $ is an integer.

Sample Explanation 1

By purchasing the 2nd and 3rd sets, you can get all components for $20\ +\ 10\ =\ 30$ yen.

Sample Explanation 2

Component 5 is not included in any set, so it is impossible to get all components.

见题面 Input 部分

见题面 Output 部分