RT

不吸氧后面三个 T，吸氧才能过得了

#include <cstdio>
#include <cstring>
#include <iostream>
#include <cmath>
#include <algorithm> //These are useful heads.
//#include <map>
//#include <vector>
//#include <stack>
//#include <queue> //These are the heads which are not very useful.
#define F(i, a, b) for(int (i) = (a); (i) <= (b); ++(i))
#define R(i, a, b) for(int (i) = (a); (i) >= (b); --(i))
#define ll long long //No long long see your ancestor
using namespace std;

template<typename T>
inline T read() {
	T f = 1, x = 0; char c = getchar();
	while(!isdigit(c)) {if(c == '-') f = -1; c = getchar();}
	while(isdigit(c)) {x = x * 10 + c - '0'; c = getchar();}
	return x * f;
}
#define Rint read<int>()
#define Rll read<ll>()

const int N = 4e4 + 7, M = 2e5 + 7;
struct node{int x, y, t, id;}a[M];
int n, m, h[M], w[M], id[M];
ll ans[M], f[N][207];

inline void solve(int l, int r, int li, int ri) {
	if(li > ri) return;
	if(l == r) {
		F(i, li, ri)
			if(a[id[i]].t < h[l]) ans[a[id[i]].id] = 0;
			else ans[a[id[i]].id] = w[l];
		return;
	}
	int mid = (l + r) >> 1, cnt1 = 0, cnt2 = 0, tmp1[M] = {0}, tmp2[M] = {0};
	F(i, 0, h[mid] - 1) f[mid][i] = 0;
	F(i, h[mid], 200) f[mid][i] = w[mid];
	R(i, mid - 1, l) {
		F(j, 0, h[i] - 1) f[i][j] = f[i + 1][j];
		F(j, h[i], 200) f[i][j] = max(f[i + 1][j], f[i + 1][j - h[i]] + w[i]);
	}
	F(i, 0, h[mid + 1] - 1) f[mid + 1][i] = 0;
	F(i, h[mid + 1], 200) f[mid + 1][i] = w[mid + 1];
	F(i, mid + 2, r) {
		F(j, 0, h[i] - 1) f[i][j] = f[i - 1][j];
		F(j, h[i], 200) f[i][j] = max(f[i - 1][j], f[i - 1][j - h[i]] + w[i]);
	}
	F(i, li, ri) {
		int x = a[id[i]].x, y = a[id[i]].y, t = a[id[i]].t, idd = a[id[i]].id;
		if(l <= x && x <= mid && mid < y && y <= r) F(j, 0, t) ans[idd] = max(ans[idd], f[x][j] + f[y][t - j]);
		else if(x > mid && y > mid) tmp2[++cnt2] = id[i];
		else tmp1[++cnt1] = id[i];
	}
	F(i, 1, cnt1) id[i + li - 1] = tmp1[i];
	F(i, 1, cnt2) id[i + li + cnt1 - 1] = tmp2[i];
	solve(l, mid, li, li + cnt1 - 1), solve(mid + 1, r, li + cnt1, li + cnt1 + cnt2 - 1);
}

int main() {
	//freopen(".in", "r", stdin);
	//freopen(".out", "w", stdout);
	n = Rint, m = Rint;
	F(i, 1, n) h[i] = Rint;
	F(i, 1, n) w[i] = Rint;
	F(i, 1, m) a[i].x = Rint, a[i].y = Rint, a[i].t = Rint, id[a[i].id = i] = i;
	solve(1, n, 1, m);
	F(i, 1, m) printf("%lld\n", ans[i]);
	return 0;
}