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); for (int i = 0; i < n + 1; i++) for (int j = 0; j < v + 1; j++) dp[i][j] = 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 v2 = min(v, j + ss[i].gas); if (v2 >= d) { dp[i + 1][v2 - d] = min(dp[i + 1][v2 - 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;