import sys class InputError(Exception): pass class StrictIn: def __init__(self, s: bytes, i: int = 0, line: int = 1, col: int = 1): self.s = s self.i = i self.line = line self.col = col @staticmethod def from_stdin_ascii() -> "StrictIn": raw = sys.stdin.buffer.read() for p, b in enumerate(raw): if b >= 0x80: raise InputError(f"non-ASCII byte at offset {p}: 0x{b:02x}") if b in (0x09, 0x0A, 0x0D): continue if 0x20 <= b <= 0x7E: continue raise InputError(f"disallowed control byte at offset {p}: 0x{b:02x}") return StrictIn(raw) def _eof(self) -> bool: return self.i >= len(self.s) def _peek(self): return None if self._eof() else self.s[self.i] def _advance(self) -> int: if self._eof(): self._err("unexpected EOF") b = self.s[self.i] self.i += 1 if b == 0x0A: self.line += 1 self.col = 1 else: self.col += 1 return b def _err(self, msg: str) -> None: raise InputError(f"{msg} (line {self.line}, col {self.col})") def _consume_newline(self) -> None: b = self._peek() if b == 0x0A: self._advance() return if b == 0x0D: self._advance() if self._peek() != 0x0A: self._err("bare CR is not allowed (use LF or CRLF)") self._advance() self.line += 1 self.col = 1 return self._err("expected EOL") def skip_spaces(self) -> None: while (not self._eof()) and (self._peek() in (0x20, 0x09)): self._advance() def skip_ws(self) -> None: while not self._eof(): b = self._peek() if b in (0x20, 0x09): self._advance() elif b in (0x0A, 0x0D): self._consume_newline() else: break def read_space(self) -> None: b = self._peek() if b not in (0x20, 0x09): self._err("expected SPACE/TAB") while (not self._eof()) and (self._peek() in (0x20, 0x09)): self._advance() def read_eoln(self) -> None: self._consume_newline() def read_eof(self) -> None: if not self._eof(): self._err("expected EOF (extra data exists)") def read_token(self) -> str: b = self._peek() if b is None: self._err(f"unexpected EOF while reading token") if b in (0x20, 0x09): self._err(f"unexpected leading SPACE/TAB while reading token") if b in (0x0A, 0x0D): self._err(f"unexpected EOL while reading token") start = self.i while not self._eof(): b = self._peek() if b in (0x20, 0x09, 0x0A, 0x0D): break self._advance() return self.s[start:self.i].decode("ascii") def read_int(self, lo=None, hi=None) -> int: t_str = self.read_token() t = t_str.encode("ascii") if t[:1] == b"-": body = t[1:] if len(body) == 0: self._err(f"int is not an integer") else: body = t if len(body) == 0 or (not all(48 <= c <= 57 for c in body)): self._err(f"int is not a base-10 integer") x = int(t_str) if lo is not None and x < lo: self._err(f"int out of range: {x} < {lo}") if hi is not None and x > hi: self._err(f"int out of range: {x} > {hi}") return x def read_string(self, min_len: int | None = None, max_len: int | None = None) -> str: s = self.read_token() if min_len is not None and len(s) < min_len: self._err(f"str too short: len={len(s)} < {min_len}") if max_len is not None and len(s) > max_len: self._err(f"str too long: len={len(s)} > {max_len}") return s from heapq import heappush, heappop ins = StrictIn.from_stdin_ascii() n = ins.read_int(1, 2*10**5) ins.read_space() y = ins.read_int(1, 10**18) ins.read_space() z = ins.read_int(y + 1, 10**18) ins.read_eoln() clx = [] for _ in range(n): c = ins.read_int(1, 10**18) ins.read_space() l = ins.read_int(1, 10**18) ins.read_space() x = ins.read_int(1, 10**18) ins.read_eoln() clx.append((c, l, x)) ins.read_eof() clx.sort(key=lambda x: x[1]) clx.append((1, 10**18+1, 1)) h = [] for i in range(n): if clx[i][1] <= y: heappush(h, (-clx[i][2], clx[i][0])) else: break ans = 0 while y < z: nxtl = clx[i][1] if h: x, c = heappop(h) x = -x if y + c * x >= z and z <= nxtl + x: ans += (z - y + x - 1) // x print(ans) exit() if y + c * x < nxtl: ans += c y += c * x else: ans += (nxtl - y + x - 1) // x y += ((nxtl - y + x - 1) // x) * x heappush(h, (-x, c - (nxtl - y + x - 1) // x)) else: print(-1) exit() # print(y, ans,h) while clx[i][1] <= y: heappush(h, (-clx[i][2], clx[i][0])) i += 1