# ZeroJudge - f817: TOI_y21m4_a03枯枝
### 題目連結：https://zerojudge.tw/ShowProblem?problemid=f817
###### tags: `ZeroJudge` `動態規劃（Dynamic Programming）`

#include <iostream>
#include <algorithm>
using namespace std;

int main() {
	cin.sync_with_stdio(false); cin.tie(nullptr);
	static long long dryness[1000][1000], total;
	int branches;
	while (cin >> branches) {
		total = 0;
		for (int i = 0; i < branches; ++i) {
			cin >> dryness[i][i];
			total += dryness[i][i];
		}
		for (int i = 1; i < branches; ++i)
			dryness[i - 1][i] = dryness[i - 1][i - 1] + dryness[i][i];
		for (int length = 3; length <= branches; ++length)
			for (int i = 0, j; i <= branches - length; ++i) {
				j = i + length - 1;
				dryness[i][j] = (1LL << 60);
				for (int k = i + 1; k < j; ++k)
					dryness[i][j] = min(dryness[i][j], max(dryness[i + 1][k], dryness[k + 1][j]));
				dryness[i][j] += dryness[i][i];
			}
		cout << dryness[0][branches - 1] << ' ' << total << '\n';
	}
}