Problem Description
The land price on the MMM island is extremely high. So people on the island all live in a very tall tower with one million floors!! There are N electric service companies (labeled 1 to N) and M power stations on the island. One power station belongs to exactly one company.
At the beginning, the company of each power station is given, and a company can choose one floor to build a power center. Assuming that there are k power stations (on floor a1,a2,...,ak) that belong to a company, and the company chooses floor x to build the power center, the daily cost of this company would be |a1-x|+|a2-x|+...+|ak-x|. MMM, the master of the island, has made a special rule:
x1 <=> x2 <=> x3 <=> ... <=> xn
The operator <=> can be either <= or >=. It means that the power centers chosen by the adjacent companies should follow the specified order. For example, if the rule is x1 <= x2 >= x3, it means that the power center of company 1 should not be higher than that of company 2, and the power center of company 2 should not be lower than that of company 3. Though there is no constraint between company 1 and company 3. If company 1 chooses floor 2 for the power center and company 2 chooses floor 3, the station of company 3 can only be in floor 1, 2 or 3.
Your task is to help the companies calculate their minimum total daily cost.
Input
There are multiple test cases. The first line has an integer T (T ≤ 10), which indicates the number of test cases.
Each test case begins with two integers N and M (1 ≤ N ≤ M ≤ 5*10^5).
There are N - 1 operators on the second line, either '<=' or '>=', separated by spaces, indicating the rules between adjacent companies.
The third line has M pairs of integers. Each pair x_i, y_i describes the i-th power station, where x_i indicates the label of the floor and y_i indicates the label of the company, (1 ≤ x_i ≤ 10^6, 1 ≤ y_i ≤ N). It is guaranteed that each company has at least one power station.
Output
For each test case, output the minimum total daily cost of the island.
Sample Input
3
3 5
<= <=
2 1 3 1 4 2 4 2 5 3
3 8
<= <=
7 3 9 3 3 2 4 2 5 2 6 1 7 1 8 1
4 4
<= >= <=
3 1 1 2 4 3 2 4
Sample Output
1
11
4
