#include using namespace std; #define For(i, a, b) for(int i = (a); i < (b); i++) #define rep(i, n) For(i, 0, n) #define rFor(i, a, b) for(int i = (a); i >= (b); i--) #define ALL(v) (v).begin(), (v).end() #define rALL(v) (v).rbegin(), (v).rend() #define SZ(v) ((int)(v).size()) using lint = long long; using ld = long double; const int INF = 1001001001; const lint LINF = 1000000000000000000; // 真上から反時計回り const int di[] = {-1, 0, 1, 0}; const int dj[] = {0, -1, 0, 1}; const int di8[] = {-1, -1, 0, 1, 1, 1, 0, -1}; const int dj8[] = {0, -1, -1, -1, 0, 1, 1, 1}; struct SetupIo { SetupIo() { ios::sync_with_stdio(false); cin.tie(nullptr); cout << fixed << setprecision(15); cerr << fixed << setprecision(15); } } setupio; namespace tatsumr { template bool chmin(T &a, const T &b) { return a > b ? a = b, 1 : 0; } template bool chmax(T &a, const T &b) { return a < b ? a = b, 1 : 0; } template T mypow(T a, T b) { T res = 1; while (b) { if (b & 1) { res *= a; } a *= a; b >>= 1; } return res; } template T modpow(T a, T b, T mod) { T res = 1; while (b) { if (b & 1) { res = (res * a) % mod; } a = (a * a) % mod; b >>= 1; } return res; } } // namespace tatsumr using namespace tatsumr; struct Slime { lint C, L, X; Slime(lint _C, lint _L, lint _X) : C(_C), L(_L), X(_X) {} bool operator<(const Slime &rhs) const { return X < rhs.X; } bool operator>(const Slime &rhs) const { return X > rhs.X; } }; int main() { int N; lint Y, Z; cin >> N >> Y >> Z; vector slimes; rep(i, N) { lint C, L, X; cin >> C >> L >> X; slimes.emplace_back(Slime(C, L, X)); } sort(ALL(slimes), [](const Slime &lhs, const Slime &rhs) { return lhs.L < rhs.L; }); priority_queue pq; // 倒せるスライム int i = 0; while (i < N && slimes[i].L <= Y) { pq.emplace(slimes[i]); i++; } lint ans = 0; while (!pq.empty()) { auto s = pq.top(); pq.pop(); // 1. 全種のスライムがpqに入っている場合...sをひたすら倒す if (i == N) { lint need = (Z - Y) / s.X + ((Z - Y) % s.X != 0); // Zになるために最低何匹倒す必要があるか // 1-1. Zに到達できる場合 if (s.C >= need) { ans += need; cout << ans << "\n"; return 0; } // 1-2. まだZ以上にはならない場合 else { Y += s.X * s.C; ans += s.C; } } // 2. まだpqに入れていないスライムがいる場合...ギリギリまでレベル上げ else { lint nl = slimes[i].L; lint need = (nl - Y) / s.X + ((nl - Y) % s.X != 0); // 次のスライムが攻撃可能になるために最低何匹倒す必要があるか // 2-1. sがneed匹以上いる場合...need匹倒して、次のスライムを入れる if (s.C >= need) { // 倒す Y += s.X * need; ans += need; if (s.C > need) { pq.emplace(Slime(s.C - need, s.L, s.X)); } // 倒せるようになったスライムを入れる while (i < N && slimes[i].L <= Y) { pq.emplace(slimes[i]); i++; } } // 2-2. sがneed匹未満のとき...全員倒す else { Y += s.X * s.C; ans += s.C; } } } cout << -1 << "\n"; }