Враги и сабли

Простая

Ограничение по времени выполнения 5 секунд

Ограничение по использованию памяти 256 мегабайт

Казак Вус приехал на Сечь, чтобы навестить своего знакомого, который в своей мастерской начал ковать сабли. Знакомый уже успел выковать $n$ сабель, и каждая $i$ -я сабля характеризуется двумя параметрами — длиной $a_{i}$ и остротой $b_{i}$ , а также стоит $cos t_{i}$ карбованцев.

Недавно на Сечи появилось $m$ врагов. Атаман предложил награду за каждого из них — за поимку $j$ -го врага можно получить $p ro f i t_{j}$ карбованцев. Однако у каждого врага есть свои параметры брони — толщина $c_{j}$ и прочность $d_{j}$ .

Чтобы поймать врага, необходимо пробить его броню. Для этого требуется сабля, длина которой не меньше толщины брони, а острота не меньше прочности брони. Формально, $i$ -я сабля может быть использована для поимки $j$ -го врага, если выполняются условия $a_{i} \geq c_{j}$ и $b_{i} \geq d_{j}$ .

Казак Вус хочет узнать, сколько карбованцев он может максимально заработать, чтобы решить, стоит ли ему заниматься таким опасным делом, и просит вас помочь.

Обратите внимание, что на Сечи можно брать карбованцы в кредит, то есть Казак Вус может иметь отрицательное количество карбованцев в какой-то момент времени. Также Казак Вус может использовать одну саблю для поимки нескольких врагов.

Входные данные

Первая строка содержит два целых числа $n$ и $m$ ( $1 \leq n, m \leq 1 0^{6}$ ) — количество сабель и врагов соответственно.

Следующие $n$ строк содержат по три целых числа $a_{i}$ , $b_{i}$ и $cos t_{i}$ ( $0 \leq a_{i}, b_{i}, cos t_{i} \leq 1 0^{9}$ ) — длина, острота и цена $i$ -й сабли.

Следующие $m$ строк содержат по три целых числа $c_{j}$ , $d_{j}$ и $p ro f i t_{j}$ ( $0 \leq c_{j}, d_{j}, p ro f i t_{j} \leq 1 0^{9}$ ) — толщина и прочность брони $j$ -го врага и награда за него.

Выходные данные

Выведите единственное целое число — максимальное количество карбованцев, которое может заработать Казак Вус.

Примеры

Ввод #1

Ответ #1

Оценивание

( $13$ баллов): для любых двух врагов $(i, j)$ , где $i \neq = j$ , либо $c_{i} > c_{j}$ , либо $d_{i} > d_{j}$ , то есть не существует врага, который имеет оба параметра брони не хуже другого; $n, m \leq 5000$ ;
( $10$ баллов): для любых двух врагов $(i, j)$ , где $i \neq = j$ , либо $c_{i} > c_{j}$ , либо $d_{i} > d_{j}$ , то есть не существует врага, который имеет оба параметра брони не хуже другого; $n, m \leq 1 0^{5}$ ;
( $13$ баллов): для любых двух сабель $(i, j)$ , где $i \neq = j$ , либо $a_{i} > a_{j}$ , либо $b_{i} > b_{j}$ , то есть не существует сабли, которая имеет оба параметра атаки не хуже другой; $n, m \leq 5000$ ;
( $10$ баллов): для любых двух сабель $(i, j)$ , где $i \neq = j$ , либо $a_{i} > a_{j}$ , либо $b_{i} > b_{j}$ , то есть не существует сабли, которая имеет оба параметра атаки не хуже другой; $n, m \leq 1 0^{5}$ ;
( $14$ баллов): $n, m \leq 5000$ ;
( $23$ балла): $n, m \leq 1 0^{5}$ ;
( $17$ баллов): без дополнительных ограничений.

Отправки 84

Коэффициент принятия 18 %