울타리 수리

농부 존은 목장을 둘러싼 울타리의 일부를 수리하려고 한다. 울타리를 재어 보니, 각각 정수 길이 $L_i$ ($1 \le L_i \le 50{,}000$)를 갖는 널빤지 $N$개 ($1 \le N \le 20{,}000$)가 필요하다는 것을 알았다. 존은 이 $N$개의 널빤지로 잘라 낼 수 있을 만큼 긴 널빤지 하나, 즉 길이가 모든 $L_i$의 합과 같은 널빤지 하나를 산다. 톱질할 때 톱밥으로 사라지는 길이("kerf")는 무시한다.

존에게는 나무를 자를 톱이 없어서, 이 긴 널빤지를 들고 이웃 농부 돈의 농장으로 찾아가 톱을 빌려 달라고 정중히 부탁한다. 농부 돈은 톱을 빌려주는 대신, $N-1$번의 톱질 각각에 요금을 매기기로 한다. 한 번의 톱질 요금은 그때 잘리는 나무 조각의 길이와 정확히 같다. 예를 들어 길이 21인 조각을 자르면 21원이 든다.

$N$개의 널빤지를 만들려면 모두 $N-1$번 잘라야 한다. 자르는 순서와 위치는 존이 마음대로 정할 수 있고, 순서에 따라 중간 조각들의 길이가 달라지므로 총 요금도 달라진다. 존이 $N$개의 널빤지를 만드는 데 써야 하는 최소 금액을 구하여라.

• 첫째 줄: 널빤지의 개수 $N$
• 둘째 줄부터 $N+1$번째 줄까지: 각 줄에 필요한 널빤지의 길이 $L_i$가 하나씩 주어진다.

• 첫째 줄: $N-1$번의 톱질로 널빤지들을 만드는 데 필요한 최소 금액

처음 널빤지의 길이는 $8+5+8=21$이다. 첫 번째 톱질은 21원이 들고, 이 널빤지를 길이 13과 8로 자른다. 두 번째 톱질은 13원이 들고, 13을 8과 5로 자르므로 총합은 $21+13=34$원이 된다. 만약 21을 16과 5로 잘랐다면 두 번째 톱질에 16원이 들어 총 37원이 되고, 이는 34원보다 많다.