Nutrient Tree

You are given a binary tree with $l$ leaves ($1 \le l \le 50$). Each leaf $k$ produces an amount of nutrients $n_k$ ($1 \le n_k \le 10000$).

Every branch of the tree (think of it as an edge) limits how many nutrients can flow along it toward the root. You have $X$ growth agents ($1 \le X \le 2500$), and each agent can be spent in one of two ways:

• Thicken an edge. Every edge starts with weight $1$. If you assign $w$ growth agents to an edge, that edge can carry at most $(1 + w)^2$ nutrients.
• Boost a leaf. If you assign $s$ growth agents to a leaf whose initial value is $n_k$, its production becomes $n_k + s$.

Nutrients flow from the leaves up toward the root. The amount that travels along an edge is the smaller of the edge's capacity and the amount arriving from below. Where edges meet at an internal node, the incoming amounts are summed before continuing upward.

Determine the maximum amount of nutrients that can reach the root.

The first line contains a description of the tree, defined recursively:

• an integer $n_k$ ($1 \le n_k \le 10000$) denotes a single leaf that produces $n_k$ nutrients, or
• $(T_L\ T_R)$ denotes an internal node whose left and right subtrees are described by $T_L$ and $T_R$ (the two subtree descriptions are separated by a space and wrapped in parentheses).

The second line contains the integer $X$ ($1 \le X \le 2500$), the number of growth agents you have.

Print a single line containing the maximum amount of nutrients that can reach the root of the tree.