Задача . E. Поликарп и работы

У Поликарпа есть очень много работ. Каждая работа характеризуется тремя целыми числами l_i, r_i и t_i. Тройка (l_i, r_i, t_i) означает, что для выполнения работы i нужно выбрать целое число s_i (l_i ≤ s_i; s_i + t_i - 1 ≤ r_i), тогда работа будет выполняться непрерывно t_i единиц времени, начиная с момента времени s_i и до момента времени s_i + t_i - 1, включительно. Иными словами, работа выполняется в течение непрерывного отрезка времени продолжительностью t_i, должна быть начата не раньше l_i, а закончена не позже r_i.

Работы Поликарпа обладают удивительным свойством: для любых работ j, k (при j < k) l_j < l_k и r_j < r_k.

Пусть имеется упорядоченное множество работ A, содержащее |A| работ. Будем считать, что a_j = (l_j, r_j, t_j) (1 ≤ j ≤ |A|). Также будем считать, что работы упорядочены по возрастанию l_j с увеличением номера.

Рассмотрим следующую рекурсивную функцию f, аргументом которой является упорядоченное множество работ A, а результатом является целое число. Функция f(A) определяется жадным алгоритмом, которые описан ниже на псевдоязыке программирования.

• Шаг 1. , ans = 0.
• Шаг 2. Рассматриваем все работы в порядке увеличения их номера в множестве A. Заведем счетчик текущей работы, i = 0.
• Шаг 3. Переходим к следующей работе: i = i + 1. Если i > |A|, то перейти к шагу 8.
• Шаг 4. Если можно выполнить работу в момент времени s_i = max(ans + 1, l_i), то выполнить работу i: s_i = max(ans + 1, l_i), ans = s_i + t_i - 1, . Перейти к следующей работе (шаг 3).
• Шаг 5. Иначе, найти такую работу , что, во-первых, работу a_i можно выполнить в момент времени s_i = max, во-вторых, значение положительно и принимает максимальное значение среди всех b_k, удовлетворяющих первому условию. Если в качестве b_k можно выбрать несколько работ, выбрать ту, у которой номер в множестве A наибольший.
• Шаг 6. Если удалось выбрать работу b_k, то , . Перейти к следующей работе (шаг 3).
• Шаг 7. Если не удалось выбрать работу b_k, то пропустить работу i. Перейти к следующей работе (шаг 3).
• Шаг 8. Выдать ans в качестве результата работы f(A).

Поликарп запутался во всех этих формулах и определениях, поэтому он попросил вас промоделировать работу функции f, вычислите значение f(A).