题目描述

农夫约翰为了修理栅栏，要将一块很长的木板切割成N块，准备切成的木板长度为Ln，未切割前木板的长度恰好为切割后木板长度的总和。每次切断木板时，需要的开销为这块木板的长度。例如长度为21的木板要切成长度为5、8、8的三块木板，长度为21的木板切成长度为13和8的木板时，开销为21。再将长度为13的板切成长度为5和8的板时，开销为13。于是合计开销为34。请求出按照目标要求将木板切割完的最小开销是多少。

输入格式

第一行是将木板切割成的块数 N (1<=N<=20000)；

第二行有N个数ai，分别为第i块木板的长度。

输出格式

木板切割完的最小开销。

输入/输出样例

3
8 5 8

34

说明/提示

时间1000ms，内存256MiB