Enemies and Sabers#10451

Enemies and Sabers

5 seconds

256 megabytes

Easy

Cossack Vus has arrived at the Sich to visit a friend who has begun forging sabers in his workshop. This friend has already crafted $n$ sabers, where the $i$ -th saber is characterized by two parameters: length and sharpness, denoted as $a_{i}$ a_i and $b_{i}$ b_i respectively. The cost of the $i$ -th saber is $cos t_{i}$ cost_i karbovantsiv.

Recently, $m$ enemies have appeared at the Sich. The ataman has offered a reward for capturing each enemy — capturing the $j$ -th enemy provides a reward of $p r o f i t_{j}$ profit_j karbovantsiv. Each enemy has armor with specific parameters: thickness and strength, denoted as $c_{j}$ c_j and $d_{j}$ d_j respectively.

To capture an enemy, their armor must be pierced. This requires a saber whose length is at least as great as the armor's thickness, and whose sharpness is at least as great as the armor's strength. Formally, the $i$ -th saber can capture the $j$ -th enemy if both conditions are satisfied: $a_{i} \geq c_{j}$ a_i \geq c_j and $b_{i} \geq d_{j}$ b_i \geq d_j.

Cossack Vus wants to determine the maximum number of karbovantsiv he can earn to decide if engaging in this risky venture is worthwhile, and he seeks your assistance.

Note that at the Sich, it is possible to take karbovantsiv on credit, meaning Cossack Vus can have a negative balance at some point. Additionally, Cossack Vus can use a single saber to capture multiple enemies.

Input

The first line contains two integers $n$ and $m$ ( $1 \leq n, m \leq 1 0^{6}$ 1 \leq n,m \leq 10^6) — the number of sabers and enemies, respectively.

The next $n$ lines each contain three integers $a_{i}$ a_i, $b_{i}$ b_i, and $cos t_{i}$ cost_i ( $0 \leq a_{i}, b_{i}, cos t_{i} \leq 1 0^{9}$ 0 \leq a_i, b_i, cost_i \leq 10^9) — the length, sharpness, and cost of the $i$ -th saber.

The following $m$ lines each contain three integers $c_{j}$ c_j, $d_{j}$ d_j, and $p r o f i t_{j}$ profit_j ( $0 \leq c_{j}, d_{j}, p r o f i t_{j} \leq 1 0^{9}$ 0 \leq c_j, d_j, profit_j \leq 10^9) — the thickness and strength of the $j$ -th enemy's armor and the reward for capturing them.

Output

Output a single integer — the maximum number of karbovantsiv Cossack Vus can earn.

Examples

Example 1

Scoring

( $13$ points): For any two enemies $(i, j)$ , where $i \neq = j$ i \ne j, either $c_{i} > c_{j}$ c_i > c_j, or $d_{i} > d_{j}$ d_i > d_j, meaning there is no enemy whose both armor parameters are not worse than another; $n, m \leq 5000$ n, m \leq 5\,000;
( $10$ points): For any two enemies $(i, j)$ , where $i \neq = j$ i \ne j, either $c_{i} > c_{j}$ c_i > c_j, or $d_{i} > d_{j}$ d_i > d_j, meaning there is no enemy whose both armor parameters are not worse than another; $n, m \leq 1 0^{5}$ n, m \leq 10^5;
( $13$ points): For any two sabers $(i, j)$ , where $i \neq = j$ i \ne j, either $a_{i} > a_{j}$ a_i > a_j, or $b_{i} > b_{j}$ b_i > b_j, meaning there is no saber whose both attack parameters are not worse than another; $n, m \leq 5000$ n, m \leq 5\,000;
( $10$ points): For any two sabers $(i, j)$ , where $i \neq = j$ i \ne j, either $a_{i} > a_{j}$ a_i > a_j, or $b_{i} > b_{j}$ b_i > b_j, meaning there is no saber whose both attack parameters are not worse than another; $n, m \leq 1 0^{5}$ n, m \leq 10^5;
( $14$ points): $n, m \leq 5000$ n,m \leq 5\,000;
( $23$ points): $n, m \leq 1 0^{5}$ n, m \leq 10^5;
( $17$ points): Without additional constraints.