시간 제한메모리 제한제출정답맞힌 사람정답 비율
5 초 2048 MB0000.000%

문제

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

The store offers $N$ shopping deals. The $i$-th shopping deal is specified by a point $(a_i , b_i)$, and for a cost of $c_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)$ such that $x ≤ a_i$ and $y ≤ b_i$.
  • The region of points $(x, y)$ such that $x ≤ a_i$ and $y ≥ b_i$.
  • The region of points $(x, y)$ such that $x ≥ a_i$ and $y ≤ b_i$.
  • The region of points $(x, y)$ such that $x ≥ a_i$ and $y ≥ b_i$.

Each shopping deal can only be used at most once. Items can also be purchased individually by paying their respective price $p_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 $N$ and $M$.

The next N lines of input each contain three space-separated integers, $a_i$, $b_i$, and $c_i$ ($−10^9 ≤ a_i , b_i ≤ 10^9$, $1 ≤ c_i ≤ 10^9$).

The next M lines of input each contain three space-separated integers, $x_i$ , $y_i$ , and $p_i$ ($−10^9 ≤ x_i , y_i ≤ 10^9$, $1 ≤ p_i ≤ 10^9$).

출력

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

서브태스크

번호배점제한
11

$1 ≤ N ≤ 8$, $1 ≤ M ≤ 20$

23

$1 ≤ N ≤ 70$, $1 ≤ M ≤ 20$

33

$1 ≤ N ≤ 70$, $1 ≤ M ≤ 70$

44

$1 ≤ N ≤ 100$, $1 ≤ M ≤ 100\, 000$ No two points $(a_i , b_i)$ or $(x_j , y_j )$ have the same $x$ or $y$-coordinate.

52

$1 ≤ N ≤ 100$, $1 ≤ M ≤ 100\, 000$

68

$1 ≤ N ≤ 1\, 000$, $1 ≤ M ≤ 100\, 000$ No two points $(a_i , b_i)$ or $(x_j , y_j )$ have the same $x$ or $y$-coordinate.

74

$1 ≤ N ≤ 1\, 000$, $1 ≤ M ≤ 100\, 000$

예제 입력 1

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

예제 출력 1

12

Use the first shopping deal on the region $\{(x, y) | x ≤ 1, y ≥ 1\}$ to obtain the second item. Then, purchase items $1$, $3$, and $4$ individually. The total cost is $3 + (2 + 4 + 3) = 12$.

채점 및 기타 정보

  • 예제는 채점하지 않는다.