poj1276

#include 
  
   

using namespace std;

#define MAXN 10
#define MAXCASH 100000

int main() {
	int i, j;
	int N;
	int cash;
	while (cin >> cash >> N) {
		int n[MAXN + 1], w[MAXN + 1], c[MAXN + 1], dp[MAXCASH + 1], count[MAXCASH + 1];
        
		for (i = 1; i <= N; i++) {
			cin >> n[i] >> w[i];
			c[i] = w[i];
		}
        
		memset(dp, 0, sizeof(dp));
		for (i = 1; i <= N; i++) {
			memset(count, 0, sizeof(count));
			for (j = w[i]; j <= cash; j++)
				if (dp[j] < dp[j - c[i]] + w[i] && count[j - c[i]] < n[i]) {
					dp[j] = dp[j - c[i]] + w[i];
					count[j] = count[j - c[i]] + 1;
				}
		}
		cout << dp[cash] << endl;
	}
}