#include <bits/stdc++.h>
#define all(x) (x).begin(),(x).end()
using namespace std;
using ll = long long;
using ld = long double;
#define int ll
#define sz(x) ((int)(x).size())
using pii = pair<ll,ll>;
using tii = tuple<int,int,int>;
// default constructorul trebuie sa fie identitate
// sorry it had to be this way
template<typename Mono, typename Lazy>
struct AINT {
const Mono ID_M = Mono();
const Lazy ID_L = Lazy();
struct Node {
Mono val;
Lazy lazy;
Node(Mono a, Lazy b): val(a), lazy(b) {;}
Node operator += (const Lazy& x) { return *this = Node(val + x, lazy + x); }
Node operator + (const Node& x) const { return Node(x.val + val, Lazy()); }
};
vector<Node> aint;
int n, L_limit, R_limit;
void init(int _n) {
n = _n;
L_limit = 1;
R_limit = n;
aint.resize(2 * n + 5, Node(ID_M, ID_L));
fill(all(aint), Node(ID_M, ID_L));
}
void init(int L, int R) {
n = R - L + 1;
L_limit = L;
R_limit = R;
aint.resize(2 * n + 5, Node(ID_M, ID_L));
fill(all(aint), Node(ID_M, ID_L));
}
void push(int node, int L, int R) {
if(aint[node].lazy != ID_L)
aint[L] += aint[node].lazy;
aint[R] += aint[node].lazy;
aint[node].lazy = ID_L;
}
tii get_sons(int node, int cl, int cr) {
return {cl + cr >> 1, node + 1, node + ((cl + cr >> 1) - cl + 1) * 2};
}
template<typename VecType>
void write(const VecType& v) {
write<VecType>(v, 1, 1, n);
}
template<typename VecType>
void write(const VecType& v, int node, int cl, int cr) {
if(cl == cr) {
aint[node].val = v[cl];
aint[node].lazy = ID_L;
return;
}
auto [mid, L, R] = get_sons(node, cl, cr);
write(v, L, cl, mid);
write(v, R, mid + 1, cr);
aint[node] = aint[L] + aint[R];
return;
}
void set(int p, Mono val) { set(p, val, 1, L_limit, R_limit); }
void set(int p, Mono val, int node, int cl, int cr) {
if(cr < p || p < cl) return;
if(cl == cr) { aint[node].val = val; return; }
auto [mid, L, R] = get_sons(node, cl, cr);
push(node, L, R);
set(p, val, L, cl, mid);
set(p, val, R, mid + 1, cr);
aint[node] = aint[L] + aint[R];
return;
}
void upd(int l, int r, Lazy x) { upd(l, r, x, 1, L_limit, R_limit); }
void upd(int l, int r, Lazy x, int node, int cl, int cr) {
if(cr < l || r < cl) return;
if(l <= cl && cr <= r) {
aint[node] += x;
return;
}
auto [mid, L, R] = get_sons(node, cl, cr);
push(node, L, R);
upd(l, r, x, L, cl, mid);
upd(l, r, x, R, mid + 1, cr);
aint[node] = aint[L] + aint[R];
return;
}
Mono query(int l, int r) { return query(l, r, 1, L_limit, R_limit); }
Mono query(int l, int r, int node, int cl, int cr) {
if(cr < l || r < cl) return ID_M;
if(l <= cl && cr <= r) return aint[node].val;
auto [mid, L, R] = get_sons(node, cl, cr);
push(node, L, R);
return query(l, r, L, cl, mid) + query(l, r, R, mid + 1, cr);
}
template<class CB>
int find_right(CB&& cb) { return find_right(cb, 1, L_limit, R_limit); }
template<class CB>
int find_right(CB&& cb, int node, int cl, int cr) {
if(!cb(aint[node].val, cl, cr)) return cr + 1;
if(cl == cr) return cl;
auto [mid, L, R] = get_sons(node, cl, cr);
push(node, L, R);
int tmp_rez = find_right(cb, L, cl, mid);
if(tmp_rez == mid + 1) return find_right(cb, R, mid + 1, cr);
return tmp_rez;
}
template<class CB>
int find_left(CB&& cb) { return find_right(cb, 1, L_limit, R_limit); }
template<class CB>
int find_left(CB&& cb, int node, int cl, int cr) {
if(!cb(aint[node].val, cl, cr)) return cl - 1;
if(cl == cr) return cl;
auto [mid, L, R] = get_sons(node, cl, cr);
push(node, L, R);
int tmp_rez = find_right(cb, R, mid + 1, cr);
if(tmp_rez == mid) return find_right(cb, L, cl, mid);
return tmp_rez;
}
void print(int node, int cl, int cr) {
if(cl == cr) {
fprintf(stderr, "(%d, %d) ", aint[node].val.simple, aint[node].val.active);
return;
}
auto [mid, L, R] = get_sons(node, cl, cr);
push(node, L, R);
print(L, cl, mid);
print(R, mid + 1, cr);
return;
}
};
struct EMPT {
EMPT operator +(const EMPT& x) const {return EMPT(); }
bool operator != (const EMPT& x) const { return 0; }
};
struct Node {
ll simple;
ll active;
Node(): simple(0), active(0) {;}
Node(ll a, ll b): simple(a), active(b) {;}
Node operator +(const Node& x) const { return Node(simple + x.simple, active + x.active); }
Node operator +(const EMPT& x) const { return *this; }
};
const int nmax = 1e6 + 5;
ll A[nmax], ALimit[nmax], AScore[nmax];
ll B[nmax], BLimit[nmax], BScore[nmax];
vector<pii> eventscol[nmax];
ll dp[nmax][nmax];
signed main() {
cin.tie(0) -> sync_with_stdio(0);
int n, m;
cin >> n >> m;
AINT<Node,EMPT> aint;
aint.init(1, n); // stocam derivata s_i - s_i-1
for(int i = 1; i <= n; i++)
cin >> A[i] >> ALimit[i] >> AScore[i];
for(int i = 1; i <= m; i++)
cin >> B[i] >> BLimit[i] >> BScore[i];
for(int i = 1; i <= n; i++) A[i] += A[i - 1];
for(int i = 1; i <= m; i++) B[i] += B[i - 1];
//for(int i = 1; i <= n; i++) cerr << A[i] << ' '; cerr << '\n';
//for(int i = 1; i <= m; i++) cerr << B[i] << ' '; cerr << '\n';
ll _0 = 0;
auto pushLineMod = [&](int ptr, int C) {
auto R = aint.query(ptr, ptr);
R.active += C;
aint.set(ptr, R);
};
auto pushColMod = [&](int ptr, int C) {
auto R = aint.query(ptr, ptr);
R.simple += C;
aint.set(ptr, R);
};
for(int i = 1; i <= n; i++) _0 += AScore[i] * (AScore[i] < 0);
for(int i = 1; i <= m; i++) _0 += BScore[i] * (BScore[i] < 0);
for(int i = 1; i <= n; i++) {
if(ALimit[i] < A[i] || AScore[i] == 0) continue;
int u = distance(B, upper_bound(B, B + m + 1, ALimit[i] - A[i])) - 1;
if(AScore[i] < 0) {
//cerr << i << ", " << AScore[i] << ": " << u + 1 << '\n';
eventscol[u + 1].emplace_back(i, -AScore[i]);
}
else {
//cerr << i << ", " << AScore[i] << ": " << 0 << ' ' << u + 1 << '\n';
eventscol[0].emplace_back(i, AScore[i]);
eventscol[u + 1].emplace_back(i, -AScore[i]);
}
}
//_0 = 0;
//ll inutil = 0;
//{
//ll negC = 0;
//for(int i = 1; i <= n; i++)
//negC += (AScore[i] < 0) * AScore[i];
//for(int i = 1; i <= m; i++)
//negC += (BScore[i] < 0) * BScore[i];
//for(int i = 0; i <= n; i++) {
//for(int j = 0; j <= m; j++) {
//if(AScore[i + 1] > 0) {
//if(A[i + 1] + B[j] <= ALimit[i + 1])
//dp[i + 1][j] = max(dp[i + 1][j], dp[i][j] + AScore[i + 1]);
//else
//dp[i + 1][j] = max(dp[i + 1][j], dp[i][j]);
//}
//else {
//if(A[i + 1] + B[j] > ALimit[i + 1])
//dp[i + 1][j] = max(dp[i + 1][j], dp[i][j] - AScore[i + 1]);
//else
//dp[i + 1][j] = max(dp[i + 1][j], dp[i][j]);
//}
//if(BScore[j + 1] > 0) {
//if(A[i] + B[j + 1] <= BLimit[j + 1])
//dp[i][j + 1] = max(dp[i][j + 1], dp[i][j] + BScore[j + 1]);
//else
//dp[i][j + 1] = max(dp[i][j + 1], dp[i][j]);
//}
//else {
//if(A[i] + B[j + 1] > BLimit[j + 1])
//dp[i][j + 1] = max(dp[i][j + 1], dp[i][j] - BScore[j + 1]);
//else
//dp[i][j + 1] = max(dp[i][j + 1], dp[i][j]);
//}
//}
//}
//cerr << negC << '\n';
//for(int j = 0; j <= m; j++) {
//for(int i = 1; i <= n; i++)
//cout << dp[i][j] << ' ';
//cout << '\t';
//for(int i = 1; i <= n; i++)
//cout << dp[i][j] - dp[i - 1][j] << ' ';
//cout << '\n';
//}
//}
//cerr << _0 << '\n';
for(int i = 0; i <= m; i++) {
sort(all(eventscol[i]), [&](auto a, auto b) { return a.second < b.second; });
for(auto [ptr, C] : eventscol[i]) {
if(C > 0) {
int cpy = C;
auto finder = [&](Node val, int cl, int cr) -> bool {
if(cr <= ptr) return 0;
if(val.simple > 0) return 1;
return 0;
};
while(1) {
int nv_ptr = aint.find_right(finder);
if(nv_ptr == n + 1) break;
auto R = aint.query(nv_ptr, nv_ptr);
int mn = min(C, R.simple);
C -= mn;
R.simple -= mn;
aint.set(nv_ptr, R);
if(C == 0) break;
ptr = nv_ptr;
}
pushLineMod(ptr, cpy);
}
else
pushLineMod(ptr, C),
pushColMod(ptr, -C);
}
if(i == 0 || BScore[i] == 0 || BLimit[i] < B[i]) {
_0 -= (BScore[i] < 0) * BScore[i];
//cerr << i << '\n';
//cerr << _0 << ' ';
//aint.print(1, 1, n);
//cerr << "\n---\n";
continue;
}
int u = distance(A, upper_bound(A, A + n + 1, BLimit[i] - B[i])) - 1;
//cerr << B[i] << ' ' << BLimit[i] << '\n';
//cerr << i << ": " << u << ", " << BScore[i] << '\n';
//cerr << A[u] << ' ' << A[u + 1] << ' ' << BLimit[i] - B[i] << '\n';
_0 += BScore[i] * (BScore[i] > 0);
//inutil += (BScore[i] > 0) * BScore[i];
if(u == n) {
//cerr << i << '\n';
//cerr << _0 << ' ';
//aint.print(1, 1, n);
//cerr << "\n---\n";
continue;
}
if(BScore[i] < 0) {
pushColMod(u + 1, -BScore[i]);
}
else {
auto finder = [&](Node val, int cl, int cr) -> bool {
if(cr <= u) return 0;
if(val.simple > 0) return 1;
return 0;
};
while(1) {
int nv_u = aint.find_right(finder);
//cerr << nv_u << '\n';
if(nv_u == n + 1) break;
auto R = aint.query(nv_u, nv_u);
int mn = min(BScore[i], R.simple);
BScore[i] -= mn;
R.simple -= mn;
aint.set(nv_u, R);
if(BScore[i] == 0) break;
u = nv_u;
}
}
}
auto R = aint.query(1, n);
cout << _0 + R.simple + R.active << '\n';
}
/**
Anul asta nu se da centroid
-- Rugaciunile mele
*/
Compilation message
dishes.cpp: In instantiation of 'tii AINT<Mono, Lazy>::get_sons(ll, ll, ll) [with Mono = Node; Lazy = EMPT; tii = std::tuple<long long int, long long int, long long int>; ll = long long int]':
dishes.cpp:125:24: required from 'Mono AINT<Mono, Lazy>::query(ll, ll, ll, ll, ll) [with Mono = Node; Lazy = EMPT; ll = long long int]'
dishes.cpp:119:42: required from 'Mono AINT<Mono, Lazy>::query(ll, ll) [with Mono = Node; Lazy = EMPT; ll = long long int]'
dishes.cpp:232:33: required from here
dishes.cpp:56:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
56 | return {cl + cr >> 1, node + 1, node + ((cl + cr >> 1) - cl + 1) * 2};
| ~~~^~~~
dishes.cpp:56:49: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
56 | return {cl + cr >> 1, node + 1, node + ((cl + cr >> 1) - cl + 1) * 2};
| ~~~^~~~
/tmp/ccPIQW1x.o: in function `__tcf_0':
dishes.cpp:(.text+0x8): relocation truncated to fit: R_X86_64_PC32 against symbol `eventscol' defined in .bss section in /tmp/ccPIQW1x.o
/tmp/ccPIQW1x.o: in function `main':
dishes.cpp:(.text.startup+0x2d): relocation truncated to fit: R_X86_64_PC32 against symbol `std::cin' defined in .bss._ZSt3cin section in /usr/lib/gcc/x86_64-linux-gnu/10/libstdc++.a(globals_io.o)
dishes.cpp:(.text.startup+0x45): relocation truncated to fit: R_X86_64_PC32 against symbol `std::cin' defined in .bss._ZSt3cin section in /usr/lib/gcc/x86_64-linux-gnu/10/libstdc++.a(globals_io.o)
dishes.cpp:(.text.startup+0x159): relocation truncated to fit: R_X86_64_PC32 against symbol `A' defined in .bss section in /tmp/ccPIQW1x.o
dishes.cpp:(.text.startup+0x160): relocation truncated to fit: R_X86_64_PC32 against symbol `ALimit' defined in .bss section in /tmp/ccPIQW1x.o
dishes.cpp:(.text.startup+0x167): relocation truncated to fit: R_X86_64_PC32 against symbol `AScore' defined in .bss section in /tmp/ccPIQW1x.o
dishes.cpp:(.text.startup+0x178): relocation truncated to fit: R_X86_64_PC32 against symbol `std::cin' defined in .bss._ZSt3cin section in /usr/lib/gcc/x86_64-linux-gnu/10/libstdc++.a(globals_io.o)
dishes.cpp:(.text.startup+0x1c6): relocation truncated to fit: R_X86_64_PC32 against symbol `B' defined in .bss section in /tmp/ccPIQW1x.o
dishes.cpp:(.text.startup+0x1cd): relocation truncated to fit: R_X86_64_PC32 against symbol `BLimit' defined in .bss section in /tmp/ccPIQW1x.o
dishes.cpp:(.text.startup+0x1d4): relocation truncated to fit: R_X86_64_PC32 against symbol `BScore' defined in .bss section in /tmp/ccPIQW1x.o
dishes.cpp:(.text.startup+0x1e7): additional relocation overflows omitted from the output
/usr/bin/ld: failed to convert GOTPCREL relocation; relink with --no-relax
collect2: error: ld returned 1 exit status
