Список відер#10394

Список відер

1 секунда

128 мегабайтів

Дуже легка

Фермер Джон розмірковує над тим, як змінити спосіб розподілу відер для доїння своїх корів. Він вважає, що це зрештою дозволить йому використовувати менше відер загалом, але не впевнений, скільки саме йому знадобиться. Будь ласка, допоможіть йому!

Фермер Джон має $n$ корів, зручно пронумерованих $1 \dots n$ . $i$ -ту корову потрібно доїти з часу $s_{i}$ s_i до часу $t_{i}$ t_i, і для цього потрібно $b_{i}$ b_i відер протягом процесу доїння. Декількох корів можна доїти одночасно; в такому випадку вони не можуть ділити відра між собою. Тобто відро, призначене для корови $i$ , не може використовуватися для доїння будь-якої іншої корови в проміжку часу між $s_{i}$ s_i та $t_{i}$ t_i. Звісно, це відро можна використовувати для інших корів поза цим часовим інтервалом. Щоб спростити собі роботу, ФД подбав про те, щоб у будь-який момент часу починалося або закінчувалося доїння щонайбільше однієї корови (тобто всі значення $s_{i}$ s_i та $t_{i}$ t_i є різними).

ФД має комору зі сховищем, що містить відра, пронумеровані послідовно мітками $1$ , $2$ , $3$ і так далі. За новою стратегією доїння, щойно доїння якоїсь корови $i$ розпочинається (у момент часу $s_{i}$ s_i), ФД біжить до комори, бере $b_{i}$ b_i доступних відер з найменшими мітками і призначає їх корові $i$ .

Визначте загальну кількість відер, яку ФД повинен тримати у своїй коморі, щоб успішно подоїти всіх корів.

Вхідні дані

Перший рядок містить ціле число $n (1 \leq n \leq 100)$ n~(1 \le n \le 100). Кожен з наступних $n$ рядків описує одну корову і містить три цілих числа $s_{i}$ s_i, $t_{i}$ t_i та $b_{i} (1 \leq s_{i}, t_{i} \leq 1000, 1 \leq b_{i} \leq 10)$ b_i~(1 \le s_i, t_i \le 1000, 1 \le b_i \le 10).

Вихідні дані

Виведіть одне ціле число — загальну кількість відер, яка потрібна ФД.

Приклади

У цьому прикладі ФД потрібно $4$ відра. Він використовує відра $1$ та $2$ для доїння корови $3$ (починаючи з часу $2$ ) та відро $3$ для доїння корови $1$ (починаючи з часу $4$ ). Коли корова $2$ приходить у момент часу $8$ , відра $1$ та $2$ знову доступні, але відро $3$ — ні, тому він використовує відра $1$ , $2$ та $4$ .

Приклад 1