Óscar and his battle
本题没有可用的提交语言。
Description
Óscar is playing a video game. His goal is to collect as many coins as possible. To do this, he has to choose one of the $n$ available characters. The $i$-th character has an attack power of $a_i$ points and a defense power of $b_i$ points. To collect the coins, he must defeat monsters (there are $m$ monsters). The $j$-th monster has an attack power of $c_j$ points, a defense power of $d_j$ points, and rewards $e_j$ coins when defeated.
In order to defeat a monster, Óscar needs his character's attack power to be greater than or equal to the monster's defense power, and his character's defense power to be greater than or equal to the monster's attack power. In other words, character $i$ can defeat monster $j$ if and only if $a_i \geq d_j$ and $b_i \geq c_j$.
Óscar can only choose one character, but he can defeat as many monsters as he wants. Once a monster is defeated, it cannot be defeated again. What is the maximum number of coins that Óscar can collect?
The first line of the input contains an integer $t$, the number of test cases. ($1 \le t \le 100$).
The first line of each test case contains two integers $n$ and $m$ ($1 \le n, m \le 2 \cdot 10^5$).
The next $n$ lines contain two integers each, $a_i$ and $b_i$; the attack and defense power of each character, respectively. ($1 \le a_i, b_i \le 10^9$).
The next $m$ lines contain three integers each, $c_j$, $d_j$, and $e_j$; the attack power, defense power, and coins rewarded by monster $j$. ($1 \le c_j, d_j, e_j \le 10^9$)
It is guaranteed that the sum of $n$ and $m$ over all test cases is at most $2 \cdot 10^5$.
For each test case, you should print the maximum number of coins that Óscar can collect with a single character.
Input
The first line of the input contains an integer $t$, the number of test cases. ($1 \le t \le 100$).
The first line of each test case contains two integers $n$ and $m$ ($1 \le n, m \le 2 \cdot 10^5$).
The next $n$ lines contain two integers each, $a_i$ and $b_i$; the attack and defense power of each character, respectively. ($1 \le a_i, b_i \le 10^9$).
The next $m$ lines contain three integers each, $c_j$, $d_j$, and $e_j$; the attack power, defense power, and coins rewarded by monster $j$. ($1 \le c_j, d_j, e_j \le 10^9$)
It is guaranteed that the sum of $n$ and $m$ over all test cases is at most $2 \cdot 10^5$.
Output
For each test case, you should print the maximum number of coins that Óscar can collect with a single character.
1
4 5
3 1
4 5
4 2
2 2
3 5 1
2 1 1
1 1 1
4 4 1
3 3 1
1
6 6
2 7
2 5
4 1
7 5
1 2
7 5
6 8 1
4 4 6
8 1 1
3 6 3
7 2 4
8 4 8
4
9
Note
—
Problem idea: Hectorungo18
Problem preparation: Esomer
Ocurrences: Novice 10, Advanced 5