AC

#include <iostream>
#include <vector>
#include <algorithm>
#include <climits>

using namespace std;

int main() {

int n;
cin >> n;
vector<int> weights(n);
int total = 0;
for (int i = 0; i < n; ++i) {
    cin >> weights[i];
    total += weights[i];
}
int half_n = n / 2;
int max_possible = 450 * 100; 
vector<vector<bool>> dp(half_n + 2, vector<bool>(max_possible + 1, false));
dp[0][0] = true;

for (int i = 0; i < n; ++i) {
    int weight = weights[i];
    for (int j = half_n; j >= 0; --j) {
        for (int k = max_possible; k >= 0; --k) {
            if (dp[j][k] && j + 1 <= half_n + 1 && k + weight <= max_possible) {
                dp[j + 1][k + weight] = dp[j + 1][k + weight] || dp[j][k];
            }
        }
    }
}

int best = 0;
int half_total = total / 2;
for (int k = half_total; k >= 0; --k) {
    bool found = false;
    for (int j = half_n; j <= half_n + 1; ++j) {
        if (j <= n && dp[j][k]) {
            found = true;
            break;
        }
    }
    if (found) {
        best = k;
        break;
    }
}

int other = total - best;
if (best < other) {
    cout << best << " " << other << endl;
} else {
    cout << other << " " << best << endl;
}

return 0;

}