영양분 나무

잎이 $l$개 ($1 \le l \le 50$)인 이진 트리가 주어집니다. 각 잎 $k$는 영양분 $n_k$ ($1 \le n_k \le 10000$)만큼을 생산합니다.

트리의 각 가지(간선이라고 생각하면 됩니다)는 뿌리 쪽으로 흐를 수 있는 영양분의 양을 제한합니다. 당신에게는 성장제 $X$개 ($1 \le X \le 2500$)가 있으며, 각 성장제는 다음 두 가지 중 하나로 사용할 수 있습니다.

• 간선 굵히기. 모든 간선의 초기 가중치는 $1$입니다. 한 간선에 성장제를 $w$개 사용하면 그 간선은 최대 $(1 + w)^2$만큼의 영양분을 운반할 수 있습니다.
• 잎 강화하기. 초기값이 $n_k$인 잎에 성장제를 $s$개 사용하면 그 잎의 생산량은 $n_k + s$가 됩니다.

영양분은 잎에서 뿌리 방향으로 흐릅니다. 한 간선을 따라 흐르는 양은 그 간선의 용량과 아래에서 올라온 양 중 더 작은 값입니다. 여러 간선이 내부 노드에서 만나면, 들어온 양들을 모두 더한 뒤 위로 올려 보냅니다.

뿌리에 도달할 수 있는 영양분의 최댓값을 구하세요.

첫째 줄에 트리의 설명이 주어집니다. 설명은 다음과 같이 재귀적으로 정의됩니다.

• 정수 $n_k$ ($1 \le n_k \le 10000$)는 영양분 $n_k$를 생산하는 잎 하나를 나타냅니다.
• $(T_L\ T_R)$은 왼쪽 서브트리가 $T_L$, 오른쪽 서브트리가 $T_R$로 설명되는 내부 노드를 나타냅니다. 두 서브트리 설명은 공백으로 구분되어 괄호로 감싸집니다.

둘째 줄에 성장제의 개수인 정수 $X$ ($1 \le X \le 2500$)가 주어집니다.

뿌리에 도달할 수 있는 영양분의 최댓값을 한 줄에 출력하세요.