d.cpp

#include <cstdio>
#include <algorithm>

using namespace std;

struct pii
{
    pii() {}
    pii(int f, int s) : first(f), second(s) {}
    int first, second;
    bool operator<(const pii &rhs) const {
        if (this->first < rhs.first)
            return true;
        else if (this->first > rhs.first)
            return false;

        return this->second > rhs.second;
    }
};

pii dp[101][50000];

int main()
{
    for (;;) {
        int n;
        scanf("%d", &n);
        if (n == 0)
            break;

        int p[100];
        for (int i = 0; i < n; ++i)
            scanf("%d", &p[i]);

        fill(&dp[0][0], &dp[101][0], pii(-1, 0));
        dp[0][0] = pii(0, 0);

        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < 50000; ++j) {
                if (dp[i][j].first < 0)
                    continue;

                dp[i + 1][j] = max(dp[i][j], dp[i + 1][j]);

                {
                    int c = (5000 - p[i]) % 1000;
                    int d = c >= 500;
                    dp[i + 1][j + c - d * 500] = max(pii(dp[i][j].first + d, dp[i][j].second + p[i]), dp[i + 1][j + c - d * 500]);
                }
                if (j >= (p[i] + 500) % 1000) {
                    int e = j - ((p[i] + 500) % 1000);
                    dp[i + 1][e] = max(pii(dp[i][j].first + 1, dp[i][j].second + p[i]), dp[i + 1][e]);
                }
            }
        }

        pii ans = pii(-1, 0);
        for (int j = 0; j < 50000; ++j)
            ans = max(ans, dp[n][j]);

        printf("%d %d\n", ans.first, ans.second);
    }

    return 0;
}