LKS.cpp

#include <iostream>
using namespace std;

const int MAX_N = 505;
const int MAX_K = 2000005;

int K, N;
int Value[MAX_N], Weight[MAX_N];
int MaxCost[2][MAX_K];	
// MAX[1][j] là giá trị lớn nhất thu được
// với việc chọn từ đồ vật từ 1 đến i và 
// khối lượng không vượt quá j

// MAX[0][j] là giá trị cũ trước đó.
// Và ngược lại

int Max(int a, int b)
{
	if(a > b) return a;
	return b;
}

int main()
{
	int T, test_case;
	ios::sync_with_stdio(false);
	//freopen("input.txt", "r", stdin);

	cin >> K >> N;
	for(int i = 1; i <= N; i++)
	    cin >> Value[i] >> Weight[i];

	// Trường hợp cơ sở
	for(int j = 0; j <= K; j++)
		MaxCost[0][j] = 0;

	for(int i = 0; i < 2; i++)
		MaxCost[i][0] = 0;

	int before = 0, current = 1;
	for(int i = 1; i <= N; i++)
	{
		for(int j = 1; j <= K; j++)
		{
			// Không chọn vật i
			MaxCost[current][j] = MaxCost[before][j];

			// Chọn vật i
			if(Weight[i] <= j) MaxCost[current][j] = 
			Max(MaxCost[current][j], MaxCost[before][j - Weight[i]] + Value[i]);
		}

		// Đổi current và before cho nhau.
		current = 1 - current;
		before  = 1 - before;
	}
	// N chẵn thì kết quả là MaxCost[0][K]
	// N lẻ thì kết quả là MaxCost[1][K]
	cout << MaxCost[N % 2][K] << endl;
	
	return 0;//Your program should return 0 on normal termination.
}