#P12971. [CCO 2025] Shopping Deals

[CCO 2025] Shopping Deals

题目描述

You are shopping from a store that sells a total of MM items. The store layout can be modelled as a two-dimensional plane, where the ii-th item is located at the point (xi,yi)(x_i, y_i) and has a price of pip_i.

The store offers NN shopping deals. The ii-th shopping deal is specified by a point (ai,bi)(a_i, b_i), and for a cost of cic_i, you can obtain one of every item within exactly one of the following four regions of your choice:

  • The region of points (x,y)(x, y) such that xaix \leq a_i and ybiy \leq b_i.
  • The region of points (x,y)(x, y) such that xaix \leq a_i and ybiy \geq b_i.
  • The region of points (x,y)(x, y) such that xaix \geq a_i and ybiy \leq b_i.
  • The region of points (x,y)(x, y) such that xaix \geq a_i and ybiy \geq b_i.

Each shopping deal can only be used at most once. Items can also be purchased individually by paying their respective price pip_i.

You want to obtain at least one of each item in the store. Find the minimum total cost you must pay to do so.

输入格式

The first line of input contains two space-separated integers NN and MM.

The next NN lines of input each contain three space-separated integers, aia_i, bib_i, and cic_i (109ai,bi109-10^9 \leq a_i, b_i \leq 10^9, 1ci1091 \leq c_i \leq 10^9).

The next MM lines of input each contain three space-separated integers, xix_i, yiy_i, and pip_i (109xi,yi109-10^9 \leq x_i, y_i \leq 10^9, 1pi1091 \leq p_i \leq 10^9).

输出格式

On a single line, output the minimum total cost that you must pay to obtain at least one of each item.

2 4
1 1 3
3 3 13
0 0 2
0 2 5
2 0 4
2 2 3
12

提示

Sample 1 Explanation

Use the first shopping deal on the region {(x,y)x1,y1}\{(x, y) \mid x \leq 1, y \geq 1\} to obtain the second item. Then, purchase items 1, 3, and 4 individually. The total cost is 3+(2+4+3)=123 + (2 + 4 + 3) = 12.

The following table shows how the available 2525 marks are distributed:

Marks Awarded Bounds on NN Bounds on MM Additional Constraints
1 mark 1N81 \leq N \leq 8 1M201 \leq M \leq 20 None
3 marks 1N701 \leq N \leq 70
1M701 \leq M \leq 70
4 marks 1<N1001 < N \leq 100 1<M1000001 < M \leq 100000 No two points (ai,bi)(a_i, b_i) or (xj,yj)(x_j, y_j) have the same xx or yy-coordinate.
2 marks 1N1001 \leq N \leq 100 1M1000001 \leq M \leq 100000 None
8 marks 1N10001 \leq N \leq 1000 No two points (ai,bi)(a_i, b_i) or (xj,yj)(x_j, y_j) have the same xx or yy-coordinate.
4 marks None