f[i][j]表示经过第i个红绿灯后还要再经过j个红绿灯才能再一次加速的最小时间
#include<iostream>
#include<algorithm>
#include<cstring>
#include<vector>
#include<array>
using namespace std;
#define int long long
int inf = 1e18;
const int N = 1010;
typedef pair<int, pair<int, int>> piii;
int f[N][N];
int n, m, v, k;
piii w[N];
signed main()
{
cin >> n >> m >> k >> v;
for (int i = 0; i < 1010; i++)
{
for (int j = 0; j < 1010; j++)
{
f[i][j] = inf;
}
}
for (int i = 0; i <= m; i++) f[0][i] = 0;
vector<array<int, 3>> w(m + 10, { 0, 0, 0 });
for (int i = 1; i <= m; i++) {
int a, b, c; cin >> a >> b >> c;
w[i] = { a, b, c };
}
m++;
w[m] = { n,1,0 };
for (int i = 1; i <= m; i++)
{
//加速
f[i][k - 1] = f[i - 1][0];
int times = w[i][1] + w[i][2];
if (f[i][k - 1] % times >= w[i][1])
{
f[i][k - 1] += times - f[i][k - 1] % times;
}
for (int j = 0; j < k; j++)
{
//不能加速
if (j)
{
int t = f[i - 1][j] + (w[i][0] - w[i - 1][0]) * v;
if (t % times >= w[i][1])
{
t += times - t % times;
}
f[i][j - 1] = min(f[i][j-1],t);
}
//能加速但不加速
else
{
int t = f[i - 1][j] + (w[i][0] - w[i - 1][0]) * v;
if (t % times >= w[i][1])
{
t += times - t % times;
}
f[i][j] = min(f[i][j], t);
}
}
}
int res = inf;
for (int i = 0; i < k; i++) res = min(res, f[m][i]);
cout << res << endl;
return 0;
}