{"raw_statement":[{"iden":"problem statement","content":"A museum exhibits $N$ jewels, Jewel $1, 2, ..., N$. The coordinates of Jewel $i$ are $(x_i, y_i)$ (the museum can be regarded as a two-dimensional plane), and the value of that jewel is $v_i$.\nSnuke the thief will steal some of these jewels.\nThere are $M$ conditions, Condition $1, 2, ..., M$, that must be met when stealing jewels, or he will be caught by the detective. Each condition has one of the following four forms:\n\n*   ($t_i$ =`L`, $a_i$, $b_i$) : Snuke can only steal at most $b_i$ jewels whose $x$ coordinates are $a_i$ or smaller.\n*   ($t_i$ =`R`, $a_i$, $b_i$) : Snuke can only steal at most $b_i$ jewels whose $x$ coordinates are $a_i$ or larger.\n*   ($t_i$ =`D`, $a_i$, $b_i$) : Snuke can only steal at most $b_i$ jewels whose $y$ coordinates are $a_i$ or smaller.\n*   ($t_i$ =`U`, $a_i$, $b_i$) : Snuke can only steal at most $b_i$ jewels whose $y$ coordinates are $a_i$ or larger.\n\nFind the maximum sum of values of jewels that Snuke the thief can steal."},{"iden":"constraints","content":"*   $1 \\leq N \\leq 80$\n*   $1 \\leq x_i, y_i \\leq 100$\n*   $1 \\leq v_i \\leq 10^{15}$\n*   $1 \\leq M \\leq 320$\n*   $t_i$ is `L`, `R`, `U` or `D`.\n*   $1 \\leq a_i \\leq 100$\n*   $0 \\leq b_i \\leq N - 1$\n*   $(x_i, y_i)$ are pairwise distinct.\n*   $(t_i, a_i)$ are pairwise distinct.\n*   $(t_i, b_i)$ are pairwise distinct."},{"iden":"input","content":"Input is given from Standard Input in the following format:\n\n$N$\n$x_1$ $y_1$ $v_1$\n$x_2$ $y_2$ $v_2$\n$:$\n$x_N$ $y_N$ $v_N$\n$M$\n$t_1$ $a_1$ $b_1$\n$t_2$ $a_2$ $b_2$\n$:$\n$t_M$ $a_M$ $b_M$"},{"iden":"sample input 1","content":"7\n1 3 6\n1 5 9\n3 1 8\n4 3 8\n6 2 9\n5 4 11\n5 7 10\n4\nL 3 1\nR 2 3\nD 5 3\nU 4 2"},{"iden":"sample output 1","content":"36\n\n![image](https://img.atcoder.jp/agc031/rghe0iwfjoievjw4epdfmengow.png)\nStealing Jewel $1, 5, 6$ and $7$ results in the total value of $36$."},{"iden":"sample input 2","content":"3\n1 2 3\n4 5 6\n7 8 9\n1\nL 100 0"},{"iden":"sample output 2","content":"0"},{"iden":"sample input 3","content":"4\n1 1 10\n1 2 11\n2 1 12\n2 2 13\n3\nL 8 3\nL 9 2\nL 10 1"},{"iden":"sample output 3","content":"13"},{"iden":"sample input 4","content":"10\n66 47 71040136000\n65 77 74799603000\n80 53 91192869000\n24 34 24931901000\n91 78 49867703000\n68 71 46108236000\n46 73 74799603000\n56 63 93122668000\n32 51 71030136000\n51 26 70912345000\n21\nL 51 1\nL 7 0\nU 47 4\nR 92 0\nR 91 1\nD 53 2\nR 65 3\nD 13 0\nU 63 3\nL 68 3\nD 47 1\nL 91 5\nR 32 4\nL 66 2\nL 80 4\nD 77 4\nU 73 1\nD 78 5\nU 26 5\nR 80 2\nR 24 5"},{"iden":"sample output 4","content":"305223377000"}],"translated_statement":null,"sample_group":[],"show_order":["default"],"formal_statement":null,"simple_statement":null,"has_page_source":true}