/* -*- coding: utf-8 -*- * * 3459.cc: No.3459 Defeat Slimes - yukicoder */ #include #include #include #include using namespace std; /* constant */ const int MAX_N = 200000; const long long MAX_C = 1000000000000000000LL; const long long LINF = 1LL << 62; /* typedef */ using ll = long long; using pli = pair; using mll = map; /* global variables */ ll cs[MAX_N], ls[MAX_N], xs[MAX_N]; pli lis[MAX_N + 1]; /* subroutines */ /* main */ int main() { int n; ll y, z; scanf("%d%lld%lld", &n, &y, &z); for (int i = 0; i < n; i++) scanf("%lld%lld%lld", cs + i, ls + i, xs + i); for (int i = 0; i < n; i++) lis[i] = {ls[i], i}; sort(lis, lis + n); lis[n] = {LINF, 0}; mll xcs; ll sum = 0; for (int i = 0; y < z;) { while (i < n && lis[i].first <= y) { int j = lis[i++].second; auto &xcj = xcs[xs[j]]; xcj = min(MAX_C, xcj + cs[j]); } if (xcs.empty()) break; auto mit = xcs.end(); mit--; auto &[x, c] = *mit; ll dy = min(z, lis[i].first) - y; ll dc = min(c, (dy + x - 1) / x); y += x * dc; c -= dc; if (c == 0) xcs.erase(mit); sum += dc; } printf("%lld\n", (y >= z) ? sum : -1LL); return 0; }