UVa 10163 - Storage Keepers

// UVa 10163 - Storage Keepers
// dynamic programming

#include <iostream>
#include <string.h>
using namespace std;

const int maxm = 30;
const int maxn = 100;
const int maxp = 1000;
const int oo = maxm * maxp + 1;

int main() {
	int n, m;
	while ((cin >> n >> m) && (n || m)) {

		// input
		int p[maxm];
		for (int i = 0; i < m; i++)
			cin >> p[i];

		// find L
		int L[maxn + 1];
		memset(L, 0, sizeof(L));
		L[0] = oo;
		for (int i = 0; i < m; i++)
			for (int j = n; j >= 1; j--)
				for (int k = 0; k < j; k++) {
					int newL = min(p[i] / (j - k), L[k]);
					if (newL > L[j])
						L[j] = newL;
				}

		// find Y
		int T[maxn + 1];
		if (L[n] == 0)
			T[n] = 0;
		else {
			memset(T, 127, sizeof(T));
			T[0] = 0;
			for (int i = 0; i < m; i++)
				for (int j = n; j >= 1; j--)
					for (int k = 0; k < j; k++)
						if (min(p[i] / (j - k), L[k]) >= L[n]
								&& T[k] + p[i] < T[j])
							T[j] = T[k] + p[i];
		}

		// output
		cout << L[n] << " " << T[n] << endl;
	}
	return 0;
}