#include <stdio.h>
#include <string.h>
#include <stdlib.h>
typedef struct thing
{
int cost; /* 代价 */
int value; /* 价值 */
}THING;
THING *thi = NULL; /* 保存物品信息 */
int maxCost = 0; /* 总金额 */
int count = 0; /* 物品数 */
int maxValueTmp[1000][100] = {-1}; /* maxValueTmp[i][j]保存花费i能放下前j个物品的最大价值,-1表示未知 */
int max(int a, int b)
{
return a >= b ? a : b;
}
/* 花费cost取前n个物品能获得的最大价值 */
int getMaxValue(int cost,int num)
{
int maxValue = 0;
if (maxValueTmp[cost][num] != -1)
{
maxValue = maxValueTmp[cost][num]; /* 获得保存的值 */
}
else if (num == 0) /* 如果只有1个物品(第1个物品num为0) */
{
if (cost >= thi[num].cost) /* 能够放下当前物品 */
{
maxValue = thi[num].value; /* 获得的价值就是当前物品的价值 */
}
else
{
maxValue = 0; /* cost值不够放下当前物品,获得价值为0 */
}
}
else if (cost >= thi[num].cost) /* cost值够放下当前物品(num),当前物品不是最后一个 */
{
maxValue = max((getMaxValue(cost-thi[num].cost,num-1) + thi[num].value), /* 放当前物品,value为用(cost-当前物品cost)去放前(num-1)个物品取得的价值加当前物品的价值 */
(getMaxValue(cost,num-1)) /* 不放当前物品,value为用(cost)去放前(num-1)个物品取得的价值 */
);
}
else /* cost值不够放下当前物品 */
{
maxValue = getMaxValue(cost,num-1);
}
maxValueTmp[cost][num] = maxValue; /* 保存cost值放前num个物品能取得的最大value */
return maxValue;
}
int main()
{
int i = 0;
scanf("%d %d",&maxCost,&count);
thi = (THING *)malloc((count)*sizeof(THING));
memset(thi,0,count*sizeof(THING));
memset(&maxValueTmp[0][0],-1,sizeof(maxValueTmp));
for (i = 0; i < count; i++)
{
scanf("%d %d",&thi[i].cost, &thi[i].value);
}
printf("%d\n",getMaxValue(maxCost,count-1));
return 0;
}