Сік#6836
В одній з фавел Ріо-де-Жанейро засяяло світло. Після місяців кропіткої роботи, нарешті, вдалося підключити генератор до тисяч подовжувачів, і нетрі осяялися мільйонами яскравих вогнів...
Однак пропускної здатності подовжувачів виявилося недостатньо, щоб задовольнити енергетичні потреби всіх будинків у нетрях. Тому інженери повинні були ретельно вибрати, які будинки підключити, а які залишити без підключення, перш ніж увімкнути генератор. Їхнє завдання полягало в тому, щоб забезпечити енергією якомога більше будинків, враховуючи енергетичні потреби кожного будинку та пропускну здатність подовжувачів.
Більш конкретно, генератор і кожен будинок представлені вузлами, а подовжувачі — ребрами між ними. Таким чином, кожен вузол отримує живлення рівно від одного іншого вузла. Крім того, кожен вузол, крім вузла генератора, має невід'ємну потребу в енергії. Генератор виробляє кількість енергії, яка значно перевищує загальну пропускну здатність підключених до нього подовжувачів, і тому може розглядатися як нескінченне джерело енергії.
Використовуючи ці дані, визначте, скільки будинків інженери змогли забезпечити енергією відповідно до їхніх потреб.
Перший рядок вхідних даних містить одне ціле число 0 \leq n \leq 1000, яке позначає кількість будинків у нетрях.
Далі слідують рядків у форматі p_i\ r_i\ c_i, де 0 \leq p_i \leq n — це батьківський вузол будинку , 0 \leq r_i \leq 100 — потреба в енергії будинку , а 1 \leq c_i \leq 100 — пропускна здатність подовжувача, що з'єднує будинок з будинком p_i.
Генератор має індекс .
Виведіть максимальну кількість будинків, чиї енергетичні потреби були задоволені.
Приклад 1