Заклинание
Кастование заклинания — это непрерывный процесс, начинающийся с определенного количества энергии (измеряется в мана), которая может быть использована для призыва элементов в заклинание. Каждый элемент может быть призван в любом количестве мгновенно, потребляя энергию, и сразу становится частью заклинания, обеспечивая мощность (измеряется в мана в секунду) с этого момента. Эта мощность вызывает накопление энергии со временем, которая, в свою очередь, может быть использована для призыва дополнительных элементов. Мы продолжаем этот процесс до тех пор, пока общая мощность нашего заклинания не достигнет требуемого уровня.
В этом процессе есть одно усложнение, которое опытные заклинатели используют для более эффективного кастования заклинаний. Каждый элемент может иметь до одного родительского элемента, который поддерживает его призыв, делая его вдвое дешевле по энергии, чем обычно, если родительский элемент уже присутствует. Например, если элемент 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, который не должен обрабатываться.
Выходные данные
Для каждого тестового случая выведите одну строку с одним целым числом, равным минимальному количеству секунд, необходимому для достижения целевой мощности (округленному до ближайшего целого числа вверх).