using P = pair; using VP = vector

; int @n, @m; ll @a; vector e(n + 1); rep(m) { int @l, @r; ll @x; e[r].push_back({l, x}); } VLL f(n + 1, -ll_inf); // f_{i, j} := 到第 i 个位置,最后一刀在 (j, j + 1) 之间的最大贡献 f[0] = 0; ll mx = 0; rep(i, 1, n + 1) { f[i] = mx - a; for(auto x : e[i]) { f[i] >?= f[x.first - 1] + x.second - (i == n ? 0 : a); } mx >?= f[i]; } for(auto x : f) mx >?= x; wt(mx);