[NOIP2023] 天天爱打卡

• 时间限制：2 秒
• 内存限制：512 MiB

题目描述

试运行共 $n$ 天。某天跑步打卡会消耗 $d$ 点能量，能量允许为负；连续打卡不能超过 $k$ 天。

共有 $m$ 个挑战。挑战 $(x_i,y_i,v_i)$ 表示：若第 $x_i-y_i+1$ 天至第 $x_i$ 天全部打卡，则获得 $v_i$ 点能量。多个满足的挑战奖励都会获得。

初始能量为 $0$。求试运行结束时能达到的最大能量。

输入格式

第一行两个整数 $c,t$，表示测试点编号和数据组数。

每组数据第一行四个正整数 $n,m,k,d$；接下来 $m$ 行，每行三个正整数 $x_i,y_i,v_i$。

输出格式

对每组数据输出一行一个整数，表示最大能量。

样例输入 1

1 1
3 2 2 1
2 2 4
3 2 3

样例输出 1

2

样例说明

第 $1,2$ 天打卡，第 $3$ 天休息，能量为 $-1-1+4=2$。

数据范围

令 $l_i=x_i-y_i+1$。对于所有数据：$1\le t\le10$，$1\le k\le n\le10^9$，$1\le m\le10^5$，$1\le l_i\le x_i\le n$，$1\le d,v_i\le10^9$。

本题采用独立计分点，各子任务内所有测试点等分。