Алёна решила сесть на диету и пошла в лес за яблоками. Внезапно она обнаружила волшебное корневое дерево с корнем в вершине 1, на каждом ребре и в каждой вершине которого записаны некоторые числа.
Девочка заметила, что некоторые вершины дерева грустят, поэтому она решила с ними поиграть. Назовем вершину v грустной, если в ее поддереве найдется вершина u, такая что dist(v, u) > au, где au — число, записанное в вершине u, а dist(v, u) — сумма чисел на ребрах на пути от v до u.
Листьями дерева называются вершины, соединенные ребром ровно с одной вершиной, а корень дерева является листом тогда и только тогда, когда дерево состоит из единственной вершины-корня.
Алёна решила удалять листья дерева до тех пор, пока все вершины не перестанут грустить. Какое минимальное количество листьев нужно удалить Алёне?
Выходные данные
Выведите минимальное количество листьев, которое требуется удалить Алёне, чтобы не осталось ни одной грустной вершины.