У нас есть волшебное дерево: корневое дерево с \(n\) вершинами. Вершины пронумерованы от \(1\) до \(n\). Вершина \(1\) является корнем.
Волшебное дерево дает волшебные плоды. Плоды растут только в тех вершинах, которые не являются корнем. В каждой вершине может быть максимум один плод.
Сейчас день 0 и ни один плод еще не поспел. Каждый плод будет спелым лишь в течение одного дня. Для каждого плода известна вершина \(v_j\), где он растет, день \(d_j\), когда он будет спелым, а также объем \(w_j\) волшебного сока, который мы можем получить, если соберем этот плод в тот день, когда он спелый.
Плоды нужно собирать, отрезая некоторые ветви дерева. Каждый день можно отрезать сколько угодно ветвей. Те части дерева, которые вы отрежете, упадут на землю, и вы сможете собрать все спелые плоды, которые там есть. Все неспелые плоды, упавшие на землю, использовать для получения сока нельзя.
Формально каждый день вы можете удалить некоторые ребра дерева. Когда вы делаете это, дерево распадается на несколько связных компонент. Вы удаляете все компоненты, не содержащие корень, и собираете все спелые плоды в этих компонентах.
Вам дано описание дерево вместе с положением, временем поспевания и сочностью каждого из \(m\) плоды. Найдите максимальный объем сока, который вы можете получить.
Выходные данные
Выведите одно целое число — максимальных объем волшебного сока, который вы можете получить с дерева.
Система оценки
Подзадача 1 (6 баллов): \(n, k \leq 20\), а также \(w_j = 1\) для всех \(j\)
Подзадача 2 (3 балла): фрукты растут только в листьях дерева
Подзадача 3 (11 баллов): \(p_i = i-1\) для всех \(i\), а также \(w_j = 1\) для всех \(j\)
Подзадача 4 (12 баллов): \(k \leq 2\)
Подзадача 5 (16 баллов): \(k \leq 20\), а также \(w_j = 1\) для всех \(j\)
Подзадача 6 (13 баллов): \(m \leq 1,000\)
Подзадача 7 (22 балла): \(w_j = 1\) для всех \(j\)
Подзадача 8 (17 баллов): нет дополнительных ограничений
Примечание
В примере одно из оптимальных решений выглядит так:
- В день 4 отрезать ребро между вершинами 4 и 5 и собрать спелый плод с 1 единицей волшебного сока. В тот же день отрезать ребро между вершинами 1 и 2 и собрать 5 единиц волшебного сока со спелого плода в вершине 3.
- В день 7 ничего не делать. Мы могли бы собрать плод из вершины 4, но это не оптимально.
- В день 9 отрезать ребро между вершинами 1 и 4. Плод в вершине 4 уже не спелый, так что его нужно выбросить, а собрать 3 единицы волшебного сока со спелого фрукта в вершине 6. Кроме того, того же эффекта мы бы добились, отрезав ребро между вершинами 4 и 6.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
6 4 10
1
2
1
4
4
3 4 5
4 7 2
5 4 1
6 9 3
|
9
|