#include <iostream>
#include <map>
using namespace std;
const int Maxn=105;
map <int,int> dp[Maxn];
int n,m,ans;
int w[Maxn],v[Maxn];
int main()

{
  cin>>m;
  for (int i=1;i<=n;i++) cin>>w[i]>>v[i];
  dp[0][0]=0;
  for (int i=0;i<n;i++)
    {
    for (auto &it:dp[i])
        {
      int w1=it.first,v1=it.second;
      dp[i+1][w1]=max(dp[i+1][w1],v1);
      if (w1-w[i+1]<=m) 
      dp[i+1][w1+w[i+1]]=max(dp[i+1][w1-w[i]],v1+v[i+1]);
        }
    }
  for (auto &it:dp[n])
    {
    int w1=it.first;
    int v1=it.second;
    if (w1<=m) ans=max(ans,v1);
    }
  cout<<ans<<endl;
  return 0;
}
