Чаклунство
Кастування заклинання — це безперервний процес, що починається з певної кількості енергії (вимірюється в мані), яку можна використати для виклику елементів у заклинання. Кожен елемент може бути викликаний у будь-якій кількості миттєво, споживаючи енергію, після чого він одразу стає частиною заклинання, забезпечуючи потужність (вимірюється в мані за секунду) з цього моменту. Ця потужність викликає накопичення енергії з часом, яка, в свою чергу, може бути використана для виклику додаткових елементів. Ми продовжуємо цей процес, поки загальна потужність нашого заклинання не досягне необхідного рівня.
Є одна складність у цьому процесі, яку досвідчені заклиначі використовують, щоб ефективніше кастувати заклинання. Кожен елемент може мати до одного батьківського елемента, який підтримує його виклик, роблячи його вдвічі дешевшим, якщо батьківський елемент вже присутній. Наприклад, якщо елемент A підтримує елемент B та елемент C, ми можемо викликати 1 одиницю елемента A спочатку за повну вартість, а потім викликати 0.5 одиниці елемента B та 0.5 одиниці елемента C за половину вартості. Якщо ми потім викличемо ще 0.5 одиниці елемента C, ця частина буде за повну вартість енергії знову, оскільки 1 одиниця елемента A вже підтримує інші елементи. Зверніть увагу, що всі 3 елементи вносять свій повний вихід потужності в заклинання; підтримка не заважає виходу потужності жодним чином, і не споживає елемент.
Маючи початкову кількість енергії, цільову кількість потужності та опис елементів заклинання, доступних для виклику, визначте, як кастувати заклинання, яке досягне цільової кількості потужності за мінімальний час.
Вхідні дані
Вхідні дані складатимуться з кількох тестових випадків. Кожен тестовий випадок починається з рядка з 3 цілими числами, розділеними пробілами: N, E та P, що позначають кількість елементів, початкову енергію (в мані) та цільову потужність (в мані за секунду) відповідно. Після цього рядка йдуть N рядків, i-й з яких описує елемент i трьома цілими числами, розділеними пробілами: e_i, p_i та parent_i, що позначають вартість енергії для виклику, вихід потужності та індекс батьківського елемента (1-індексований; parent_i = 0, якщо елемент i не має батьківського елемента).
Обмеження включають:
1 ≤ N ≤ 1000, 1 ≤ E ≤ 10^9, 1 ≤ P ≤ 10^9.
1 ≤ e_i ≤ 10^9 для всіх i, 0 ≤ p_i ≤ 10^9 для всіх i, 0 ≤ parent_i ≤ N для всіх i.
Принаймні один pi буде позитивним.
Жоден елемент не є своїм власним предком; іншими словами, жоден елемент не здатний підтримувати сам себе, будь то прямо чи опосередковано.
Вхідні дані завершуються випадком, де N = E = P = 0, який не слід обробляти.
Вихідні дані
Для кожного тестового випадку виведіть один рядок з одним цілим числом, що дорівнює мінімальній кількості секунд, необхідних для досягнення цільової потужності (округлене до найближчого цілого числа вгору).