{"problem":{"name":"Snuke the Phantom Thief","description":{"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$. Snuke t","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":5000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"agc031_e"},"statements":[{"statement_type":"Markdown","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.\n\n## Constraints\n\n*   $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.\n\n## Input\n\nInput 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$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"agc031_e","tags":[],"sample_group":[["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","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$."],["3\n1 2 3\n4 5 6\n7 8 9\n1\nL 100 0","0"],["4\n1 1 10\n1 2 11\n2 1 12\n2 2 13\n3\nL 8 3\nL 9 2\nL 10 1","13"],["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","305223377000"]],"created_at":"2026-03-03 11:01:14"}}