Техніка навчання підмайстра#9580

Техніка навчання підмайстра

2 секунди

256 мегабайтів

Середня

А́біґейль навчається на коваля і прагне спланувати своє навчання так, щоб виготовити якомога більше мечів, ставши відомим експертом.

У неї є можливість навчатися у $n$ майстрів, які готові прийняти її як ученицю. $i$ -ий майстер працює з хвилини $a_{i}$ a_i до хвилини $b_{i}$ b_i, тобто загалом $b_{i} - a_{i}$ b_i - a_i хвилин. Протягом цього часу А́біґейль може працювати в кузні цього майстра. Вона може заходити і виходити з кузні кілька разів, і під час кожного візиту виготовляти один або кілька мечів. Однак, щоб виготовити меч під наглядом $i$ -го майстра, вона повинна працювати там безперервно $t_{i}$ t_i хвилин. Вона не може залишити меч незавершеним і продовжити роботу над ним після наступного візиту до цієї кузні.

Допоможіть А́біґейль скласти оптимальний план і визначити максимальну кількість мечів, які вона може виготовити під наглядом $n$ майстрів.

Вхідні дані

Перший рядок містить кількість майстрів $n (1 \leq n \leq 2 \cdot 1 0^{5})$ n~(1 \le n \le 2 \cdot 10^5).

Кожен з наступних $n$ рядків містить три цілі числа $a_{i}, b_{i}, t_{i} (1 \leq a_{i} < a_{i} + t_{i} \leq b_{i} \leq 1 0^{18})$ a_i, b_i, t_i~(1 \le a_i < a_i + t_i \le b_i \le 10^{18}) — початковий і кінцевий час роботи майстра, а також час, необхідний для виготовлення одного меча під його наглядом.

Вихідні дані

Виведіть максимальну кількість мечів, які А́біґейль може виготовити, використовуючи оптимальну стратегію навчання.

Приклади

Приклад 1

Приклад 2

Приклад 3