Вам дано корневое дерево на \(n\) вершинах, его корень имеет номер \(1\). В \(i\)-й вершине записано число \(w_i\). Разбейте его на минимальное число таких вертикальных путей, что сумма чисел \(w_i\) в вершинах пути не превосходит \(S\), а количество вершин в пути не превосходит \(L\). Каждая вершина должна принадлежать ровно одному пути.
Вертикальным путём называется последовательность вершин \(v_1, v_2, \ldots, v_k\), где \(v_i\) (\(i \ge 2\)) — непосредственный предок \(v_{i - 1}\) в дереве.
Выходные данные
Выведите одно целое число — минимальное число вертикальных путей. Если разбить дерево невозможно, выведите \(-1\).
Примечание
В первом примере дерево разбивается на пути \(\{1\},\ \{2\},\ \{3\}\).
Во втором примере дерево разбивается на пути \(\{1,\ 2\},\ \{3\}\) или \(\{1,\ 3\},\ \{2\}\).
В третьем примере разбить дерево невозможно.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3 1 3
1 2 3
1 1
|
3
|
|
2
|
3 3 6
1 2 3
1 1
|
2
|
|
3
|
1 1 10000
10001
|
-1
|