AT_agc031_e [AGC031E] Snuke the Phantom Thief

[problemUrl]: https://atcoder.jp/contests/agc031/tasks/agc031_e とある博物館には宝石 $ 1,\ 2,\ ...,\ N $ が展示されています。 宝石 $ i $ の置いてある場所は $ (x_i,\ y_i) $ で、価値は $ v_i $ です (この博物館は二次元平面として解釈できます)。 怪盗すぬけはいくつか宝石を盗みます。 宝石の盗み方には条件 $ 1,\ 2,\ ...,\ M $ があり、すべて満たさないと探偵に捕まってしまいます。 条件はそれぞれ以下の4種類のいずれかです。 - ($ t_i $ =`L`, $ a_i $, $ b_i $) : 盗んだ宝石のうち、$ x $ 座標が $ a_i $ 以下の宝石が $ b_i $ 個以下 - ($ t_i $ =`R`, $ a_i $, $ b_i $) : 盗んだ宝石のうち、$ x $ 座標が $ a_i $ 以上の宝石が $ b_i $ 個以下 - ($ t_i $ =`D`, $ a_i $, $ b_i $) : 盗んだ宝石のうち、$ y $ 座標が $ a_i $ 以下の宝石が $ b_i $ 個以下 - ($ t_i $ =`U`, $ a_i $, $ b_i $) : 盗んだ宝石のうち、$ y $ 座標が $ a_i $ 以上の宝石が $ b_i $ 個以下 怪盗すぬけが盗める宝石の価値の総和の最大値を求めてください。

N/A

N/A

### 制約 - $ 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 $ は `L`, `R`, `U`, `D` のいずれか - $ 1\ \leq\ a_i\ \leq\ 100 $ - $ 0\ \leq\ b_i\ \leq\ N\ -\ 1 $ - $ (x_i,\ y_i) $ は互いに相違なる - $ (t_i,\ a_i) $ は互いに相違なる - $ (t_i,\ b_i) $ は互いに相違なる ### Sample Explanation 1 !\[図\](https://img.atcoder.jp/agc031/rghe0iwfjoievjw4epdfmengow.png) 宝石 $ 1,\ 5,\ 6,\ 7 $ を盗むと価値の総和が $ 36 $ となります。