Nutrient Tree

문제

There is a binary tree with l leaves (1 ≤ l ≤ 50) where each leaf k has an amount of nutrients nk (1 ≤ n_k ≤ 10, 000) that it produces.

The branches (which you can think of as edges) of this binary tree limit the maximum amount of nutrients that can flow to the root of the tree. You have X growth agents (1 ≤ X ≤ 2500) that can be used to increase the thickness of an edge or increase the nutrient production of a leaf node. Initially, each edge has a weight of 1 and if you give it w growth agents then it can transport (1 + w)² nutrients. Increasing the nutrient production of a leaf with initial value n_k by s raises the nutrient production of that leaf to n_k + s.

Notice that when edges meet, the amount of nutrient that flows is the sum of nutrients flowing along the incoming edges.

Find the maximum amount of nutrients you can transport to the root.

입력

The first line of input will be a description of the tree. This description can be defined recursively as either an integer n_k (1 ≤ n_k ≤ 10, 000) or as (T_LT_R) where T_L and T_R are descriptions of the left and right subtrees, respectively. The second line of input will be the integer X, the amount of growth agents you have.

출력

On one line, output the maximum amount of nutrients that can flow into the root of the tree.