小欧有一棵包含个结点的树，每个结点有一个人，处在第个结点的人想吃恰好个苹果。但他手里有个苹果，可能不够吃，也可能太多了。 他们每次传递可以向树上相邻的结点传递1个苹果，小欧想知道，让所有人都恰好获得他想吃的苹果的数量总共需要有多少次传递？

输入描述:

第一行输入一个整数。第二行输入个整数，保证所有都为非负整数，且和恰好等于。接下来行，每一行输出两个整数,表示结点和结点有一条边。

输出描述:

一行一个整数，表示最小次数。