존은 목장 주위의 울타리 부분 부분 교체하기를 원한다. 펜스를 둘러본 후 N (1 ≤ N ≤ 20,000) 개의 나무가 필요하다는 것을 알았다. 각각은 정수 크기 Li ( 1 <= Li <= 50,000) N 개의 나무를 만들 수 있는 긴 나무를 샀다.(즉 Li 의 크기의 합이다) 존은 kerf , 톱질 할 때 나오는 톱밥의 길이는 무시한다. 여러분도 역시 이를 무시해야 한다.

존은 나무를 자를 톱을 가지고 있지 않아서 긴 나무를 들고 농부 돈의 집으로 가서 정중하게 톱을 빌려 줄 수 있는지를 물었다.

그런데 자본주의 물든 돈은 존에게 톱을 빌려주지 않았다. 대신 존에게 N-1 번의 컷 각각의 돈을 받기로 제안했다. 즉 21 크기의 나무를 자를 때는 21 센트의 비용을 준다.

존이 임의 위치에 나무를 자를 수 있는 경우 가장 최소의 비용으로 나무를 자를수 있게 존을 돕는 것이 문제이다.

입력

• 첫 줄에는 나무 토막의 수 N 이 주어지고 ,
• 다음 줄 부터 N 줄에는 각각 나무 토막의 길이가 주어진다.

출력

입출력 예

입력

3
8
5
8

출력

34

Hint

• 첫 번째 컷은 21 의 비용이 들고 , 13 과 8 로 나눈다.
• 두 번째 13 의 비용이 든다. 13 을 8 과 5 로 나눈다.

만약

• 첫 번째 컷은 21 의 비용이 들고 , 16 과 5 로 나눈다.
• 두 번째 컷에서 16 의 비용이 들어, 8 과 8 로 나누면

출처: USACO 2006 November Gold