#include <algorithm>
#include <array>
#include <iostream>
#include <limits>
#include <numeric>
#include <tuple>
#include <utility>
#include <vector>
using namespace std;
using int64 = long long;
struct Deal {
int64 x;
int64 y;
int64 cost;
int xr = -1;
int yr = -1;
};
struct Item {
int64 x;
int64 y;
int64 price;
};
struct Candidate {
int64 value;
int id;
};
static constexpr int64 INF64 = numeric_limits<int64>::max() / 4;
struct Best3 {
array<Candidate, 3> vals;
Best3() {
for (auto& v : vals) {
v = {INF64, -1};
}
}
void add(Candidate cand) {
if (cand.id < 0) {
return;
}
for (auto& v : vals) {
if (v.id == cand.id) {
if (cand.value < v.value) {
v.value = cand.value;
}
sort_vals();
return;
}
}
if (cand.value < vals.back().value) {
vals.back() = cand;
sort_vals();
}
}
void sort_vals() {
sort(vals.begin(), vals.end(), [](const Candidate& lhs, const Candidate& rhs) {
if (lhs.value != rhs.value) {
return lhs.value < rhs.value;
}
return lhs.id < rhs.id;
});
}
};
static Best3 merge_best3(const Best3& lhs, const Best3& rhs) {
Best3 result;
for (const auto& cand : lhs.vals) {
result.add(cand);
}
for (const auto& cand : rhs.vals) {
result.add(cand);
}
return result;
}
class MinSegTree {
public:
explicit MinSegTree(int size) : n(size), tree(4 * size + 5) {}
void clear() {
fill(tree.begin(), tree.end(), Best3());
}
void add_point(int index, int64 value, int id) {
add_point(1, 0, n - 1, index, {value, id});
}
Best3 query(int left, int right) const {
if (left > right) {
return Best3();
}
return query(1, 0, n - 1, left, right);
}
private:
int n;
vector<Best3> tree;
void add_point(int node, int l, int r, int index, Candidate cand) {
if (l == r) {
tree[node].add(cand);
return;
}
int mid = (l + r) / 2;
if (index <= mid) {
add_point(node * 2, l, mid, index, cand);
} else {
add_point(node * 2 + 1, mid + 1, r, index, cand);
}
tree[node] = merge_best3(tree[node * 2], tree[node * 2 + 1]);
}
Best3 query(int node, int l, int r, int ql, int qr) const {
if (ql <= l && r <= qr) {
return tree[node];
}
int mid = (l + r) / 2;
if (qr <= mid) {
return query(node * 2, l, mid, ql, qr);
}
if (ql > mid) {
return query(node * 2 + 1, mid + 1, r, ql, qr);
}
return merge_best3(query(node * 2, l, mid, ql, qr),
query(node * 2 + 1, mid + 1, r, ql, qr));
}
};
class MaxSegTree {
public:
explicit MaxSegTree(int size) : n(size), tree(4 * size + 5, -INF64) {}
void clear() {
fill(tree.begin(), tree.end(), -INF64);
}
void chmax_point(int index, int64 value) {
chmax_point(1, 0, n - 1, index, value);
}
int64 query_suffix_max(int left) const {
if (left >= n) {
return -INF64;
}
return query(1, 0, n - 1, left, n - 1);
}
private:
int n;
vector<int64> tree;
void chmax_point(int node, int l, int r, int index, int64 value) {
if (l == r) {
tree[node] = max(tree[node], value);
return;
}
int mid = (l + r) / 2;
if (index <= mid) {
chmax_point(node * 2, l, mid, index, value);
} else {
chmax_point(node * 2 + 1, mid + 1, r, index, value);
}
tree[node] = max(tree[node * 2], tree[node * 2 + 1]);
}
int64 query(int node, int l, int r, int ql, int qr) const {
if (ql <= l && r <= qr) {
return tree[node];
}
int mid = (l + r) / 2;
if (qr <= mid) {
return query(node * 2, l, mid, ql, qr);
}
if (ql > mid) {
return query(node * 2 + 1, mid + 1, r, ql, qr);
}
return max(query(node * 2, l, mid, ql, qr),
query(node * 2 + 1, mid + 1, r, ql, qr));
}
};
struct Prefix2D {
vector<int64> xs;
vector<int64> ys;
vector<vector<int64>> pref;
int64 total = 0;
int dx = 0;
int dy = 0;
int exact_x_index(int64 value) const {
int rank = int(lower_bound(xs.begin(), xs.end(), value) - xs.begin());
return 2 * rank + 1;
}
int strict_x_index(int64 value) const {
int rank = int(lower_bound(xs.begin(), xs.end(), value) - xs.begin());
return 2 * rank;
}
int exact_y_index(int64 value) const {
int rank = int(lower_bound(ys.begin(), ys.end(), value) - ys.begin());
return 2 * rank + 1;
}
int strict_y_index(int64 value) const {
int rank = int(lower_bound(ys.begin(), ys.end(), value) - ys.begin());
return 2 * rank;
}
int64 sum_prefix_idx(int rx, int ry) const {
return pref[rx + 1][ry + 1];
}
int64 sum_rect_idx(int lx, int rx, int ly, int ry) const {
if (lx > rx || ly > ry) {
return 0;
}
return pref[rx + 1][ry + 1] - pref[lx][ry + 1] - pref[rx + 1][ly] + pref[lx][ly];
}
int64 sum_le_le(int64 x, int64 y) const {
return sum_prefix_idx(exact_x_index(x), exact_y_index(y));
}
int64 sum_le_ge(int64 x, int64 y) const {
int rx = exact_x_index(x);
int ly = exact_y_index(y);
return sum_rect_idx(0, rx, ly, dy - 1);
}
int64 sum_ge_le(int64 x, int64 y) const {
int lx = exact_x_index(x);
int ry = exact_y_index(y);
return sum_rect_idx(lx, dx - 1, 0, ry);
}
int64 sum_ge_ge(int64 x, int64 y) const {
int lx = exact_x_index(x);
int ly = exact_y_index(y);
return sum_rect_idx(lx, dx - 1, ly, dy - 1);
}
int64 strict_tl(int64 x, int64 y) const {
int rx = strict_x_index(x);
int ly = exact_y_index(y) + 1;
return sum_rect_idx(0, rx, ly, dy - 1);
}
int64 strict_bl(int64 x, int64 y) const {
int rx = strict_x_index(x);
int ry = strict_y_index(y);
return sum_rect_idx(0, rx, 0, ry);
}
int64 strict_br(int64 x, int64 y) const {
int lx = exact_x_index(x) + 1;
int ry = strict_y_index(y);
return sum_rect_idx(lx, dx - 1, 0, ry);
}
int64 sum_xle_y_between(int64 x, int64 y_low, int64 y_high) const {
int rx = exact_x_index(x);
int ly = exact_y_index(y_low);
int ry = exact_y_index(y_high);
return sum_rect_idx(0, rx, ly, ry);
}
};
static Prefix2D build_prefix(const vector<Deal>& deals, const vector<Item>& items) {
Prefix2D pref;
for (const auto& deal : deals) {
pref.xs.push_back(deal.x);
pref.ys.push_back(deal.y);
}
sort(pref.xs.begin(), pref.xs.end());
pref.xs.erase(unique(pref.xs.begin(), pref.xs.end()), pref.xs.end());
sort(pref.ys.begin(), pref.ys.end());
pref.ys.erase(unique(pref.ys.begin(), pref.ys.end()), pref.ys.end());
const int nx = (int)pref.xs.size();
const int ny = (int)pref.ys.size();
pref.dx = 2 * nx + 1;
pref.dy = 2 * ny + 1;
vector<vector<int64>> grid(pref.dx, vector<int64>(pref.dy, 0));
for (const auto& item : items) {
int rx_rank = int(lower_bound(pref.xs.begin(), pref.xs.end(), item.x) - pref.xs.begin());
int ry_rank = int(lower_bound(pref.ys.begin(), pref.ys.end(), item.y) - pref.ys.begin());
int rx = (rx_rank < nx && pref.xs[rx_rank] == item.x) ? 2 * rx_rank + 1 : 2 * rx_rank;
int ry = (ry_rank < ny && pref.ys[ry_rank] == item.y) ? 2 * ry_rank + 1 : 2 * ry_rank;
grid[rx][ry] += item.price;
pref.total += item.price;
}
pref.pref.assign(pref.dx + 1, vector<int64>(pref.dy + 1, 0));
for (int i = 0; i < pref.dx; ++i) {
for (int j = 0; j < pref.dy; ++j) {
int64 value = grid[i][j];
value += pref.pref[i][j + 1];
value += pref.pref[i + 1][j];
value -= pref.pref[i][j];
pref.pref[i + 1][j + 1] = value;
}
}
return pref;
}
static vector<Deal> transform_deals(const vector<Deal>& deals, int t) {
vector<Deal> out = deals;
for (auto& deal : out) {
int64 x = deal.x;
int64 y = deal.y;
if (t & 1) {
swap(x, y);
}
if (t & 2) {
x = -x;
}
if (t & 4) {
y = -y;
}
deal.x = x;
deal.y = y;
}
return out;
}
static vector<Item> transform_items(const vector<Item>& items, int t) {
vector<Item> out = items;
for (auto& item : out) {
int64 x = item.x;
int64 y = item.y;
if (t & 1) {
swap(x, y);
}
if (t & 2) {
x = -x;
}
if (t & 4) {
y = -y;
}
item.x = x;
item.y = y;
}
return out;
}
struct SolverContext {
vector<Deal> deals;
Prefix2D pref;
vector<vector<int>> ids_by_x;
int nx = 0;
int ny = 0;
int64 total = 0;
explicit SolverContext(vector<Deal> transformed_deals, const vector<Item>& transformed_items)
: deals(std::move(transformed_deals)), pref(build_prefix(deals, transformed_items)) {
nx = (int)pref.xs.size();
ny = (int)pref.ys.size();
total = pref.total;
ids_by_x.assign(nx, {});
for (int i = 0; i < (int)deals.size(); ++i) {
deals[i].xr = int(lower_bound(pref.xs.begin(), pref.xs.end(), deals[i].x) - pref.xs.begin());
deals[i].yr = int(lower_bound(pref.ys.begin(), pref.ys.end(), deals[i].y) - pref.ys.begin());
ids_by_x[deals[i].xr].push_back(i);
}
}
int64 sum_quadrant(int id, int orient) const {
const auto& d = deals[id];
if (orient == 0) {
return pref.sum_le_le(d.x, d.y);
}
if (orient == 1) {
return pref.sum_ge_le(d.x, d.y);
}
if (orient == 2) {
return pref.sum_le_ge(d.x, d.y);
}
return pref.sum_ge_ge(d.x, d.y);
}
int64 sum_intersection(int id1, int orient1, int id2, int orient2) const {
const auto& a = deals[id1];
const auto& b = deals[id2];
bool has_lx = false, has_hx = false, has_ly = false, has_hy = false;
int64 lx = 0, hx = 0, ly = 0, hy = 0;
auto apply_bounds = [&](const Deal& d, int orient) {
bool low_x = (orient == 1 || orient == 3);
bool high_x = (orient == 0 || orient == 2);
bool low_y = (orient == 2 || orient == 3);
bool high_y = (orient == 0 || orient == 1);
if (low_x) {
if (!has_lx || d.x > lx) {
lx = d.x;
}
has_lx = true;
}
if (high_x) {
if (!has_hx || d.x < hx) {
hx = d.x;
}
has_hx = true;
}
if (low_y) {
if (!has_ly || d.y > ly) {
ly = d.y;
}
has_ly = true;
}
if (high_y) {
if (!has_hy || d.y < hy) {
hy = d.y;
}
has_hy = true;
}
};
apply_bounds(a, orient1);
apply_bounds(b, orient2);
if (has_lx && has_hx && lx > hx) {
return 0;
}
if (has_ly && has_hy && ly > hy) {
return 0;
}
int left_idx = has_lx ? pref.exact_x_index(lx) : 0;
int right_idx = has_hx ? pref.exact_x_index(hx) : pref.dx - 1;
int low_idx = has_ly ? pref.exact_y_index(ly) : 0;
int high_idx = has_hy ? pref.exact_y_index(hy) : pref.dy - 1;
if (left_idx > right_idx || low_idx > high_idx) {
return 0;
}
return pref.sum_rect_idx(left_idx, right_idx, low_idx, high_idx);
}
int64 solve_exact_small_k() const {
int64 best = 0;
const int n = (int)deals.size();
for (int i = 0; i < n; ++i) {
for (int o = 0; o < 4; ++o) {
best = max(best, sum_quadrant(i, o) - deals[i].cost);
}
}
for (int i = 0; i < n; ++i) {
for (int j = i + 1; j < n; ++j) {
for (int oi = 0; oi < 4; ++oi) {
int64 si = sum_quadrant(i, oi);
for (int oj = 0; oj < 4; ++oj) {
int64 sj = sum_quadrant(j, oj);
int64 inter = sum_intersection(i, oi, j, oj);
best = max(best, si + sj - inter - deals[i].cost - deals[j].cost);
}
}
}
}
vector<int64> costs;
costs.reserve(n);
for (const auto& d : deals) {
costs.push_back(d.cost);
}
sort(costs.begin(), costs.end());
if (costs.size() >= 4) {
best = max(best, total - costs[0] - costs[1] - costs[2] - costs[3]);
}
return best;
}
static int64 choose_distinct(const Best3& best3, int ban1, int ban2) {
for (const auto& cand : best3.vals) {
if (cand.id >= 0 && cand.id != ban1 && cand.id != ban2) {
return cand.value;
}
}
return INF64;
}
int64 solve_family_g1() const {
int64 best = 0;
MinSegTree seg(ny);
for (int lx = 0; lx < nx; ++lx) {
seg.clear();
const auto& left_ids = ids_by_x[lx];
for (int rx = lx; rx < nx; ++rx) {
for (int id : ids_by_x[rx]) {
seg.add_point(deals[id].yr, deals[id].cost, id);
}
for (int b : left_ids) {
for (int a : ids_by_x[rx]) {
if (a == b || deals[b].y > deals[a].y) {
continue;
}
Best3 query = seg.query(deals[b].yr, deals[a].yr);
int64 c_cost = choose_distinct(query, a, b);
if (c_cost >= INF64) {
continue;
}
int64 uncovered = pref.strict_tl(deals[b].x, deals[a].y);
best = max(best, total - uncovered - deals[a].cost - deals[b].cost - c_cost);
}
}
}
}
return best;
}
int64 solve_family_g2() const {
int64 best = 0;
MinSegTree seg(ny);
for (int lx = 0; lx < nx; ++lx) {
seg.clear();
const auto& left_ids = ids_by_x[lx];
for (int rx = lx; rx < nx; ++rx) {
for (int id : ids_by_x[rx]) {
seg.add_point(deals[id].yr, deals[id].cost, id);
}
for (int a : left_ids) {
for (int b : ids_by_x[rx]) {
if (a == b || deals[b].y > deals[a].y) {
continue;
}
Best3 query = seg.query(0, deals[b].yr);
int64 c_cost = choose_distinct(query, a, b);
if (c_cost >= INF64) {
continue;
}
int64 uncovered = pref.strict_bl(deals[a].x, deals[b].y);
best = max(best, total - uncovered - deals[a].cost - deals[b].cost - c_cost);
}
}
}
}
return best;
}
int64 solve_family_g3() const {
int64 best = 0;
MinSegTree seg(ny);
for (int c_id = 0; c_id < (int)deals.size(); ++c_id) {
seg.clear();
int start_x = deals[c_id].xr;
for (int rx = start_x; rx < nx; ++rx) {
for (int id : ids_by_x[rx]) {
if (id == c_id || deals[id].y < deals[c_id].y) {
continue;
}
int64 value = deals[id].cost + pref.strict_tl(deals[c_id].x, deals[id].y);
seg.add_point(deals[id].yr, value, id);
}
for (int b : ids_by_x[rx]) {
if (b == c_id || deals[b].y < deals[c_id].y) {
continue;
}
Best3 query = seg.query(deals[b].yr, ny - 1);
int64 best_a = choose_distinct(query, b, c_id);
if (best_a >= INF64) {
continue;
}
int64 uncovered_br = pref.strict_br(deals[b].x, deals[c_id].y);
int64 score = total - deals[c_id].cost - deals[b].cost - uncovered_br - best_a;
best = max(best, score);
}
}
}
return best;
}
int64 solve_family_g4() const {
int64 best = 0;
MaxSegTree seg(nx);
for (int c_id = 0; c_id < (int)deals.size(); ++c_id) {
seg.clear();
for (const auto& d : deals) {
if (&d - &deals[0] == c_id) {
continue;
}
if (d.y > deals[c_id].y) {
seg.chmax_point(d.xr, pref.sum_ge_le(d.x, d.y) - d.cost);
}
}
int64 base = pref.sum_le_le(deals[c_id].x, deals[c_id].y) - deals[c_id].cost;
for (int a_id = 0; a_id < (int)deals.size(); ++a_id) {
if (a_id == c_id) {
continue;
}
if (!(deals[c_id].x < deals[a_id].x && deals[a_id].y < deals[c_id].y)) {
continue;
}
int64 overlap = pref.sum_xle_y_between(deals[c_id].x, deals[a_id].y, deals[c_id].y);
int64 extra_a = pref.sum_le_ge(deals[a_id].x, deals[a_id].y) - overlap - deals[a_id].cost;
int64 extra_b = seg.query_suffix_max(deals[a_id].xr + 1);
if (extra_b <= -INF64 / 2) {
continue;
}
best = max(best, base + extra_a + extra_b);
}
}
return best;
}
int64 solve_only_three_deal_families() const {
int64 best = 0;
best = max(best, solve_family_g1());
best = max(best, solve_family_g2());
best = max(best, solve_family_g3());
best = max(best, solve_family_g4());
return best;
}
};
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, m;
cin >> n >> m;
vector<Deal> deals(n);
for (int i = 0; i < n; ++i) {
cin >> deals[i].x >> deals[i].y >> deals[i].cost;
}
vector<Item> items(m);
int64 total_price = 0;
for (int i = 0; i < m; ++i) {
cin >> items[i].x >> items[i].y >> items[i].price;
total_price += items[i].price;
}
SolverContext base_ctx(deals, items);
int64 best_savings = base_ctx.solve_exact_small_k();
for (int t = 0; t < 8; ++t) {
SolverContext ctx(transform_deals(deals, t), transform_items(items, t));
best_savings = max(best_savings, ctx.solve_only_three_deal_families());
}
cout << (total_price - best_savings) << '\n';
return 0;
}
