#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = (1LL << 20);
ll tree[2 * N];
const int ID = 0;
void init() {
for (int i = 0; i < 2 * N; ++i) {
tree[i] = ID;
}
}
ll query(int l, int r, int ind = 1, int L = 0, int R = N - 1) {
if (l <= L && R <= r) {
return tree[ind];
} if (l > R || L > r) {
return ID;
}
int M = (L + R) / 2;
return max(query(l, r, 2 * ind, L, M), query(l, r, 2 * ind + 1, M + 1, R));
}
void update(int x, ll v, int ind = 1, int L = 0, int R = N - 1) {
if (L > x || x > R) {
return;
}
if (L == x && x == R) {
tree[ind] = max(tree[ind], v);
return;
}
int M = (L + R) / 2;
update(x, v, 2 * ind, L, M);
update(x, v, 2 * ind + 1, M + 1, R);
tree[ind] = max(tree[2 * ind + 1], tree[2 * ind]);
}
array<ll, 3> a[N], b[N];
ll pa[N], pb[N];
int main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
init();
int n, m;
cin >> n >> m;
// {time, req, score}
for (int i = 0; i < n; ++i) {
for (int j = 0; j < 3; ++j) {
cin >> a[i][j];
}
}
for (int i = 0; i < m; ++i) {
for (int j = 0; j < 3; ++j) {
cin >> b[i][j];
}
}
for (int i = 0; i < n; ++i) {
pa[i + 1] = pa[i] + a[i][0];
}
for (int i = 0; i < m; ++i) {
pb[i + 1] = pb[i] + b[i][0];
}
ll ans = 0;
// edges[i] : {time, dir, score} -1 means A[i]->B
vector<vector<array<ll, 3>>> edges(n);
for (int i = 0; i < n; ++i) {
auto can_get = [&] (int x) -> bool { // can process x'th from B and still get award for A[i]
return pb[x + 1] + pa[i + 1] <= a[i][1];
};
if (can_get(m - 1)) {
ans += a[i][2];
continue;
}
if (!can_get(0)) {
continue;
}
int lo = 0, hi = m - 1;
while (lo < hi) {
int md = (lo + hi + 1) / 2;
if (can_get(md)) lo = md;
else hi = md - 1;
}
if (a[i][2] > 0) { // do A[i] before B[lo + 1]
edges[i].push_back({lo + 1, -1, a[i][2]});
} else { // do B[lo + 1] before A[i]
ans += a[i][2];
edges[i].push_back({lo + 1, 1, -a[i][2]});
}
}
for (int i = 0; i < m; ++i) {
auto can_get = [&] (int x) -> bool {
return pa[x + 1] + pb[i + 1] <= b[i][1];
};
if (can_get(n - 1)) {
ans += b[i][2];
continue;
}
if (!can_get(0)) {
continue;
}
int lo = 0, hi = n - 1;
while (lo < hi) {
int md = (lo + hi + 1) / 2;
if (can_get(md)) lo = md;
else hi = md - 1;
}
if (b[i][2] > 0) { // do B[i] before A[lo + 1]
edges[lo + 1].push_back({i, 1, b[i][2]});
} else { // do A[lo + 1] before B[i]
ans += b[i][2];
edges[lo + 1].push_back({i, -1, -b[i][2]});
}
}
// segtree[x] after time t stores dp(first t from A, x from B), 1B
for (int t = 0; t < n; ++t) {
sort(edges[t].begin(), edges[t].end());
vector<pair<ll, ll>> to_upd;
// cout << "!! " << t << '\n';
ll dp = 0, dp2 = 0;
for (auto [at, dir, w]: edges[t]) {
if (dir == -1) { // outwards
dp2 = max(dp2, dp) + w;
to_upd.push_back({at + 1, dp2});
} else { // inwards
dp = max(dp, query(0, at + 1)) + w;
to_upd.push_back({at + 1, dp});
}
// cout << "? " << at << ' ' << dir << ' ' << w << '\n';
}
for (auto [x, v]: to_upd) {
update(x, v);
// cout << "upd " << x << ' ' << v << '\n';
}
}
cout << (ans + query(0, m)) << '\n';
return 0;
}
ce
