import std; alias GasStation = Tuple!(int, "x", int, "gas", int, "cost"); long calc(int v, int l, GasStation[] ss) { int n = cast(int)ss.length; ss ~= GasStation(l, 0, 0); // sentinel // dp[i 番目のガソリンスタンド][ガソリンの量] auto dp = new long[][](n + 1, v + 1); foreach (i; 0..dp.length) dp[i][] = long.max; if (ss[0].x > v) return -1; dp[0][v - ss[0].x] = 0; for (int i = 0; i < n; i++) { int d = ss[i + 1].x - ss[i].x; for (int j = 0; j <= v; j++) { if (dp[i][j] == long.max) continue; // 補給しないで進む if (j >= d) dp[i + 1][j - d] = min(dp[i + 1][j - d], dp[i][j]); // 補給してから進む auto k = min(v, j + ss[i].gas); if (k >= d) dp[i + 1][k - d] = min(dp[i + 1][k - d], dp[i][j] + ss[i].cost); } } long ans = dp[n].minElement; return ans == long.max ? -1 : ans; } void main() { int n, v, l; scan(n, v, l); GasStation[] ss; foreach (_; 0..n) { int x, gas, cost; scan(x, gas, cost); ss ~= GasStation(x, gas, cost); } writeln(calc(v, l, ss)); } void scan(T...)(ref T a) { string[] ss = readln.split; foreach (i, t; T) a[i] = ss[i].to!t; } T read(T)() { return readln.chomp.to!T; } T[] reads(T)() { return readln.split.to!(T[]); } alias readint = read!int; alias readints = reads!int;