#agc031e. [agc031_e]Snuke the Phantom Thief

[agc031_e]Snuke the Phantom Thief

在二维平面上,有 nn 颗珠宝,第ii颗珠宝在 (xi,yi)(x_i,y_i) 的位置,价值为 viv_i

现在有一个盗贼想要偷这些珠宝。

现在给出 mm 个限制约束偷的珠宝,约束有以下四种:

  • 横坐标小于等于 aia_i 的珠宝最多偷 bib_i 颗。
  • 横坐标大于等于 aia_i 的珠宝最多偷 bib_i 颗。
  • 纵坐标小于等于 aia_i 的珠宝最多偷 bib_i 颗。
  • 纵坐标大于等于 aia_i 的珠宝最多偷 bib_i 颗。

这四个限制输入的时候分别用LRDU四个字母来区分。

现在问你在满足这些约束的条件下,盗贼偷的珠宝的最大价值和是多少。