DNA 자르기

긴 DNA 사슬을 더 작은 사슬로 자르는 단백질을 연구하고 있다. 이 단백질은 다음과 같이 동작한다. 긴 DNA 사슬을 자르기 위해 단백질은 먼저 사슬 전체를 "읽고" 두 부분(반드시 같을 필요는 없다)으로 자른 다음, 두 작은 사슬을 재귀적으로 자른다.

사슬 $S_1S_2$를 두 부분 $S_1$과 $S_2$로 자르는 데는 $S_1S_2$의 길이($S_1$의 길이와 $S_2$의 길이의 합)에 비례하는 에너지가 든다. 더 일반적으로, 사슬 $S_1 \ldots S_N$ ($N > 1$)을 자르는 데는 이를 둘로 자르는 데 드는 $S_1 \ldots S_N$의 길이에 비례하는 에너지에, 두 작은 사슬을 재귀적으로 자르는 데 필요한 에너지를 더한 만큼이 든다.

원래 DNA 사슬 $S_1 \ldots S_N$과, 자른 뒤 얻은 $N$개의 조각 $S_1, \ldots, S_N$을 알고 있다. 자연은 보통 에너지 효율이 매우 높기 때문에, DNA 사슬을 자르는 데 필요한 최소 에너지가 얼마인지 궁금하다.

이 최소 에너지의 계산은 $L_1, \ldots, L_N$에만 달려 있다는 것을 알아냈다. 여기서 $L_i$는 $S_i$의 길이이다. $N$개의 정수 $L_1, \ldots, L_N$이 주어질 때, 긴 사슬을 이 조각들로 자르는 데 단백질이 필요로 하는 최소 에너지를 계산하려고 한다.

입력은 두 줄로 이루어진다.

• 첫째 줄: 문자열의 개수 $N$, 정수이다.
• 둘째 줄: $L_1, \ldots, L_N$을 나타내는 공백으로 구분된 $N$개의 정수.

원래 사슬을 자르는 데 필요한 최소 총 에너지, 정수 하나를 한 줄에 출력한다.

• $1 \le N \le 500$;
• 모든 $1 \le i \le N$에 대해 $0 \le L_i \le 10^{14}$.