Snuke the Phantom Thief

AtCoder

IDagc031_e

Time5000ms

Memory256MB

Difficulty—

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. ## Constraints * $1 \leq N \leq 80$ * $1 \leq x_i, y_i \leq 100$ * $1 \leq v_i \leq 10^{15}$ * $1 \leq M \leq 320$ * $t_i$ is `L`, `R`, `U` or `D`. * $1 \leq a_i \leq 100$ * $0 \leq b_i \leq N - 1$ * $(x_i, y_i)$ are pairwise distinct. * $(t_i, a_i)$ are pairwise distinct. * $(t_i, b_i)$ are pairwise distinct. ## Input 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$ [samples]

Samples

Input #1

Output #1

36

![image](https://img.atcoder.jp/agc031/rghe0iwfjoievjw4epdfmengow.png)
Stealing Jewel $1, 5, 6$ and $7$ results in the total value of $36$.

Input #2

Output #2

Input #3

Output #3

Input #4

10
66 47 71040136000
65 77 74799603000
80 53 91192869000
24 34 24931901000
91 78 49867703000
68 71 46108236000
46 73 74799603000
56 63 93122668000
32 51 71030136000
51 26 70912345000
21
L 51 1
L 7 0
U 47 4
R 92 0
R 91 1
D 53 2
R 65 3
D 13 0
U 63 3
L 68 3
D 47 1
L 91 5
R 32 4
L 66 2
L 80 4
D 77 4
U 73 1
D 78 5
U 26 5
R 80 2
R 24 5

Output #4

305223377000

API Response (JSON)

{
  "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 t...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments