Problem

You are given a binary tree with N nodes numbered from 1 to N. For each node i, let A_i denote the value of node i. Let S_Anc(i) be the sum of values of all the nodes whose ancestors are node i inclusive and rooted at node 1. Let F(i) = |S_Anc(i) - S_Subtree(i)|. S_Subtree(i) is the sum of values of all the nodes on the simple path between node i and node N. If there is no child on some side, then it would be denoted by -1.

Task

Calculate the sum of F(v) for all v from 1 to N.

Constraints

• 1 <= n <= 100
• |x| is the absolute value of x.
• 1-based indexing is followed.

Example

Assumptions

• N = 3
• A = [2, 3, -2]
• C = [[2, 3], [1, -1], [-1, -1]]

Approach

• For the 1st vertex, S_Anc(1) = A_2 + A_3 + A_4 = -1 and S_Subtree(1) = A_1 = 2. Therefore, F(1) = |1-2| = 1.
• For the 2nd vertex, S_Anc(2) = A_4 = -2 and S_Subtree(2) = A_1 + A_2 = 6. Therefore, F(2) = |1-6| = 5.

Input

• N. Represents the size of array A
• A. Represents an array of integers of size N
• C. Represents a 2D array of size N

Output

The sum of F(v) for all v from 1 to N.