#include<stdio.h>

#define max(a,b) a>b?a:b

int h[30];

main()

{

int c,n,i,j;

scanf("%d%d",&c,&n);

for(i=1; i<=n; i++)

scanf("%d",&h[i]);

int a[n+1][c+1];

for(i=1; i<=n; i++)

for(j=0; j<=c; j++)

a[i][j]=0;

for(j=0; j<=c; j++)

if(h[1]<=j)a[1][j]=h[1];

for(i=2; i<=n; i++)

for(j=0; j<=c; j++)

if(j<h[i])a[i][j]=a[i-1][j];

else a[i][j]=max(a[i-1][j],a[i-1][j-h[i]]+h[i]);

int max1=0;

for(i=1; i<=n; i++)

for(j=0; j<=c; j++)

if(a[i][j]<=c)

max1=max1>a[i][j]?max1:a[i][j];

printf("%d",max1);

}

#include<bits/stdc++.h>

using namespace std;

int n,m;

int p[1001];

int v[1001];

int f[1001][1001];

int main()

{

cin>>n>>m;

for(int i=1;i<=m;i++)

{

cin>>v[i]>>p[i];

}

for(int i=1;i<=m;i++)

{

for(int j=n;j>=0;j--)

{

if(v[i]<j)

{

f[i][j]=max(f[i-1][j],f[i-1][j-v[i]]+p[i]*v[i]); // 状态转移方程！

}

else f[i][j]=f[i-1][j];

}

}

cout<<f[m][n];

}