시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 512 MB 4 3 2 66.667%

문제

You are studying a protein that splits long chains of DNA into smaller chains. This protein works in the following way: to split a long chain of DNA, the protein first “reads” the whole chain and cuts it into two (non-necessarily equal) parts and, then, recursively splits the two smaller chains.

Splitting a chain S1S2 into the two parts S1 and S2 takes an amount of energy proportional to the length of S1S2 (which is the sum of the lengths of S1 and S2). More generally, splitting a chain S1 . . . SN (N > 1) takes an energy proportional to the length of S1 . . . SN to cut it into two, plus the energy required to recursively split the two smaller chains.

You know the original DNA chain S1 . . . SN and the N fragments S1, . . . , SN obtained after the split. Since nature is usually very energy-efficient, you wonder what the minimal energy required to split the DNA chain is.

You noticed that the computation of this minimal energy only depends on L1, . . . , LN where Li is the length of Si. Given these N integers L1, . . . , LN, you want to compute the minimal energy required by the protein to split the long chain into these chunks.

입력

The input consists of two lines:

  • on the first line: the number N of strings, an integer;
  • on the second line: N space-separated integers representing L1, . . . , LN.

출력

The output should contain a single line with a single integer, the minimal total energy required to split the original chain.

제한

  • 1 ≤ N ≤ 500;
  • 0 ≤ Li ≤ 1014 for all 1 ≤ i ≤ N.

예제 입력 1

3
1 2 1

예제 출력 1

7

We always need a first split on the original chain (of length 4) followed by a second cut on a chain of length 3. Therefore the minimal cost is 3 + 4 = 7.

예제 입력 2

3
2 1 1

예제 출력 2

6

A first possibility is to split S1S2S3 into S1S2 and S3, and then split S1S2, for a total energy cost of 7. The only other possibility is to split S1S2S3 into S1 and S2S3, and then split S2S3, for a total cost of 6. Thus, the minimal energy required is 6.