У Ashish есть дерево, состоящее из \(n\) вершин, пронумерованных от \(1\) до \(n\), с корнем в вершине \(1\). \(i\)-я вершина дерева имеет стоимость \(a_i\), и в ней записана бинарная цифра \(b_i\). Ashish хочет, чтобы в конце в \(i\)-й вершине была записана бинарная цифра \(c_i\).
Для этого, он может выполнить следующую операцию любое количество раз:
- Выберите любые \(k\) вершин из поддерева любой вершины \(u\) и переставьте цифры в этих вершинах так, как пожелаете, за стоимость \(k \cdot a_u\). Здесь он может выбрать \(k\) в диапазоне от \(1\) до размера поддерева \(u\).
Он хочет выполнить операции так, чтобы у каждой вершины в итоге оказалась цифра, соответствующая желаемой цифре для этой вершины.
Помогите ему найти минимальную общую стоимость, за которую можно сделать так, чтобы после проведения всех операций для каждого \(u\) в вершине \(u\) была записана цифра \(c_u\), или определить, что это невозможно.
Выходные данные
Выведите минимальную общую стоимость, за которую можно сделать так, чтобы в каждой вершине была записана желаемая цифра для этой вершины, или \(-1\), если сделать это невозможно.
Примечание
Дерево, соответствующие примерам \(1\) и \(2\):
В примере \(1\) мы можем выбрать вершину \(1\) и \(k = 4\) за стоимость \(4 \times 1\) = \(4\) и выбрать вершины \({1, 2, 3, 5}\), переставить их цифры и получить желаемые цифры в каждой позиции.
В примере \(2\) мы можем выбрать вершину \(1\) и \(k = 2\) за стоимость \(10000 \times 2\), выбрать вершины \({1, 5}\), обменять их цифры, после чего аналогичным образом выбрать вершину \(2\) и \(k = 2\) за стоимость \(2000 \times 2\) и вершины \({2, 3}\), обменять их цифры, чтобы получить нужные цифры в каждой позиции.
В примере \(3\) невозможно получить нужные цифры, потому что среди начальных цифр нет цифры \(1\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5
1 0 1
20 1 0
300 0 1
4000 0 0
50000 1 0
1 2
2 3
2 4
1 5
|
4
|
|
2
|
5
10000 0 1
2000 1 0
300 0 1
40 0 0
1 1 0
1 2
2 3
2 4
1 5
|
24000
|
|
3
|
2
109 0 1
205 0 1
1 2
|
-1
|