{"trustable":true,"prependHtml":"\u003cscript\u003e window.katexOptions \u003d { disable: true }; \u003c/script\u003e\n\u003cscript type\u003d\"text/x-mathjax-config\"\u003e\n MathJax.Hub.Config({\n tex2jax: {\n inlineMath: [[\u0027$$$\u0027,\u0027$$$\u0027], [\u0027$\u0027,\u0027$\u0027]],\n displayMath: [[\u0027$$$$$$\u0027,\u0027$$$$$$\u0027], [\u0027$$\u0027,\u0027$$\u0027]]\n }\n });\n\u003c/script\u003e\n\u003cscript async src\u003d\"https://mathjax.codeforces.org/MathJax.js?config\u003dTeX-AMS-MML_HTMLorMML\" type\u003d\"text/javascript\"\u003e\u003c/script\u003e","sections":[{"title":"","value":{"format":"HTML","content":"\u003cdiv class\u003d\"panel_content\"\u003eThe 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.\u003cbr\u003e\u003cbr\u003eAt 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:\u003cbr\u003e\u003cbr\u003ex1 \u0026lt;\u003d\u0026gt; x2 \u0026lt;\u003d\u0026gt; x3 \u0026lt;\u003d\u0026gt; ... \u0026lt;\u003d\u0026gt; xn\u003cbr\u003e\u003cbr\u003eThe operator \u0026lt;\u003d\u0026gt; can be either \u0026lt;\u003d or \u0026gt;\u003d. It means that the power centers chosen by the adjacent companies should follow the specified order. For example, if the rule is x1 \u0026lt;\u003d x2 \u0026gt;\u003d 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.\u003cbr\u003e\u003cbr\u003eYour task is to help the companies calculate their minimum total daily cost.\u003c/div\u003e"}},{"title":"Input","value":{"format":"HTML","content":"There are multiple test cases. The first line has an integer T (T ≤ 10), which indicates the number of test cases.\u003cbr\u003e\u003cbr\u003eEach test case begins with two integers N and M (1 ≤ N ≤ M ≤ 5*10^5).\u003cbr\u003e\u003cbr\u003eThere are N - 1 operators on the second line, either \u0027\u0026lt;\u003d\u0027 or \u0027\u0026gt;\u003d\u0027, separated by spaces, indicating the rules between adjacent companies.\u003cbr\u003e\u003cbr\u003eThe 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."}},{"title":"Output","value":{"format":"HTML","content":"For each test case, output the minimum total daily cost of the island."}},{"title":"Sample","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e3\r\n3 5\r\n\u0026lt;\u003d \u0026lt;\u003d\r\n2 1 3 1 4 2 4 2 5 3\r\n3 8\r\n\u0026lt;\u003d \u0026lt;\u003d\r\n7 3 9 3 3 2 4 2 5 2 6 1 7 1 8 1\r\n4 4\r\n\u0026lt;\u003d \u0026gt;\u003d \u0026lt;\u003d\r\n3 1 1 2 4 3 2 4\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e1\r\n11\r\n4\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}}]}