记录编号	601509	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	1841.[国家集训队2011]免费的馅饼(加强版)	最终得分	100
用户昵称	OTTF	是否通过	通过
代码语言	C++	运行时间	0.420 s
提交时间	2025-06-25 16:41:25	内存使用	3.98 MiB

#include <algorithm>
#include <cmath>
#include <cstdio>
#include <iostream>

using namespace std;

const int N = 114514;

struct pancake {
	int t;
	int p;
	int v;
	int x;

	bool operator< (pancake other) {
		return 2 * t - p < 2 * other.t - other.p;
	}
};

int n;
int w;
pancake nums[N];
int magic[N];
int tree[N];
int dp[N];
int res;

void ParseIn () {
	
	freopen ("free.in", "r" ,stdin);
	freopen ("free.out", "w", stdout);

	cin >> w >> n;
	for (int i = 1; i <= n; i++) {
		cin >> nums[i].t >> nums[i].p >> nums[i].v;
		magic[i] = 2 * nums[i].t + nums[i].p;
	}
	sort (magic + 1, magic + 1 + n);
	for (int i = 1; i <= n; i++) {
		nums[i].x = lower_bound(magic + 1, magic + 1 + n, 2 * nums[i].t + nums[i].p) - magic;
	}
	sort (nums + 1, nums + 1 + n);

}

inline int lowbit (int id) {
	return id & (-id);
}

void add (int id, int x) {
	for (; id <= n; id += lowbit (id)) {
		tree[id] = max (tree[id], x);
	}
}

int query (int id) {
	int res = 0;
	for (; id; id -= lowbit (id)) {
		res = max (res, tree[id]);
	}
	return res;
}

void Core () {

	for (int i = 1; i <= n; i++) {
		dp[i] = query (nums[i].x) + nums[i].v;
		add (nums[i].x, dp[i]);
		res = max (res, dp[i]);
	}
	
}

void CWriteOut () {
	
	cout << res << endl;
	
}

int main () {
	
	ParseIn ();
	Core ();
	CWriteOut ();
	
	return 0;
}