output_description: Print the maximum sum of values of jewels that Snuke the thief can steal.
  
  * * *
input_description: Input is given from Standard Input in the following format:
  
      
      
      N
      x_1 y_1 v_1
      x_2 y_2 v_2
      :
      x_N y_N v_N
      M
      t_1 a_1 b_1
      t_2 a_2 b_2
      :
      t_M a_M b_M
attempt: import sys
  
  input = sys.stdin.readline
  sys.setrecursionlimit(10**9)
  from bisect import bisect_left, bisect_right
  
  
  class MinCostFlow:
      def __init__(self, n):
          self.n = n
          self.edges = [[] for i in range(n)]
  
      def add_edge(self, fr, to, cap, cost):
          self.edges[fr].append([to, cap, cost, len(self.edges[to])])
          self.edges[to].append([fr, 0, -cost, len(self.edges[fr]) - 1])
  
      def MinCost(self, source, sink, flow):
          inf = 10**15 + 1
          n, E = self.n, self.edges
          prev_v, prev_e = [0] * n, [0] * n
          mincost = 0
          while flow:
              dist = [inf] * n
              dist[source] = 0
              flag = True
              while flag:
                  flag = False
                  for v in range(n):
                      if dist[v] == inf:
                          continue
                      Ev = E[v]
                      for i in range(len(Ev)):
                          to, cap, cost, rev = Ev[i]
                          if cap > 0 and dist[v] + cost < dist[to]:
                              dist[to] = dist[v] + cost
                              prev_v[to], prev_e[to] = v, i
                              flag = True
              if dist[sink] == inf:
                  return -1
              f = flow
              v = sink
              while v != source:
                  f = min(f, E[prev_v[v]][prev_e[v]][1])
                  v = prev_v[v]
              flow -= f
              mincost += f * dist[sink]
              v = sink
              while v != source:
                  E[prev_v[v]][prev_e[v]][1] -= f
                  rev = E[prev_v[v]][prev_e[v]][3]
                  E[v][rev][1] += f
                  v = prev_v[v]
          return mincost
  
  
  n = int(input())
  J = []
  L_org, D_org = [1] * n, [1] * n
  for _ in range(n):
      x, y, v = map(int, input().split())
      J.append((x, y, v))
  m = int(input())
  T = []
  for _ in range(m):
      t, a, b = input().split()
      a, b = int(a), int(b)
      T.append((t, a, b))
      if t == "L":
          L_org[b] = a + 1
      elif t == "D":
          D_org[b] = a + 1
  for i in range(1, n):
      L_org[i] = max(L_org[i - 1], L_org[i])
      D_org[i] = max(D_org[i - 1], D_org[i])
  
  
  def solve(k):
      L, D = L_org[:k], D_org[:k]
      R, U = [100] * k, [100] * k
      for t, a, b in T:
          if k - b - 1 >= 0:
              if t == "R":
                  R[k - b - 1] = a - 1
              elif t == "U":
                  U[k - b - 1] = a - 1
      for i in range(k - 2, -1, -1):
          R[i] = min(R[i], R[i + 1])
          U[i] = min(U[i], U[i + 1])
      solver = MinCostFlow(2 * n + 2 * k + 2)
      for i in range(1, k + 1):
          solver.add_edge(0, i, 1, 0)
          solver.add_edge(2 * n + k + i, 2 * n + 2 * k + 1, 1, 0)
      for i in range(n):
          v = J[i][2]
          solver.add_edge(k + i + 1, n + k + i + 1, 1, -v)
      for i in range(n):
          x, y = J[i][0], J[i][1]
          l = bisect_right(L, x)
          r = bisect_left(R, x) + 1
          d = bisect_right(D, y)
          u = bisect_left(U, y) + 1
          for j in range(r, l + 1):
              solver.add_edge(j, k + i + 1, 1, 0)
          for j in range(u, d + 1):
              solver.add_edge(n + k + i + 1, 2 * n + k + j, 1, 0)
      return -solver.MinCost(0, 2 * n + 2 * k + 1, k)
  
  
  ans = 0
  k = 1
  while True:
      tmp = solve(k)
      ans = max(ans, tmp)
      if tmp == -1 or k == n:
          break
      k += 1
  print(ans)
  
problem_description: Statement
  
  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 the thief will steal some of these jewels.
  
  There 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:
  
    * (t_i =`L`, a_i, b_i) : Snuke can only steal at most b_i jewels whose x coordinates are a_i or smaller.
    * (t_i =`R`, a_i, b_i) : Snuke can only steal at most b_i jewels whose x coordinates are a_i or larger.
    * (t_i =`D`, a_i, b_i) : Snuke can only steal at most b_i jewels whose y coordinates are a_i or smaller.
    * (t_i =`U`, a_i, b_i) : Snuke can only steal at most b_i jewels whose y coordinates are a_i or larger.
  
  Find the maximum sum of values of jewels that Snuke the thief can steal.
samples: [{"input": "7\n    1 3 6\n    1 5 9\n    3 1 8\n    4 3 8\n    6 2 9\n    5 4 11\n    5 7 10\n    4\n    L 3 1\n    R 2 3\n    D 5 3\n    U 4 2", "output": "36\n    \n\n![Figure](https://img.atcoder.jp/agc031/rghe0iwfjoievjw4epdfmengow.png)\n\nStealing Jewel 1, 5, 6 and 7 results in the total value of 36.\n\n* * *"}, {"input": "3\n    1 2 3\n    4 5 6\n    7 8 9\n    1\n    L 100 0", "output": "0\n    \n\n* * *"}, {"input": "4\n    1 1 10\n    1 2 11\n    2 1 12\n    2 2 13\n    3\n    L 8 3\n    L 9 2\n    L 10 1", "output": "13\n    \n\n* * *"}, {"input": "10\n    66 47 71040136000\n    65 77 74799603000\n    80 53 91192869000\n    24 34 24931901000\n    91 78 49867703000\n    68 71 46108236000\n    46 73 74799603000\n    56 63 93122668000\n    32 51 71030136000\n    51 26 70912345000\n    21\n    L 51 1\n    L 7 0\n    U 47 4\n    R 92 0\n    R 91 1\n    D 53 2\n    R 65 3\n    D 13 0\n    U 63 3\n    L 68 3\n    D 47 1\n    L 91 5\n    R 32 4\n    L 66 2\n    L 80 4\n    D 77 4\n    U 73 1\n    D 78 5\n    U 26 5\n    R 80 2\n    R 24 5", "output": "305223377000"}]