There is an interval initially. For an interval , if , there will be two possible changes:
* Shrinking, changes to or
* Expanding, changes to or
So, when , the interval will be unable to be changed. You don't want to see this, so you may need to ban some changing manners.
Specifically, we use tuple to describe banning. If , you can ban the bidirectional changing between and with cost while you can ban the bidirectional changing between and with cost if .
Determine the minimum total cost to guarantee that will never happen. Print "-1" if it's impossible to make it.

The first line contains two integers , denoting the initial interval and the number of banning tuples respectivly.
Following  lines each contains two integers, one character and one integer  respectivly, denoting a banning tuple.
It's guaranteed that all triples  are pairwise different.

Only one line containing one integer, denoting the answer.

3 4
1 3 L 10
1 3 R 3
1 2 L 1
1 2 R 1

12

2 1
1 2 L 1

-1