#include <bits/stdc++.h>
using namespace std;
int n, m;    // 物品数量、背包大小
int v[35];   // v[i]：第i件物品的大小
int w[35];   // w[i]：第i件物品的价值
int dp[205]; // dp[j]：j 的体积下的最大价值
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    // 输入
    cin >> m >> n;
    for (int i = 1; i <= n; i++)
        cin >> v[i] >> w[i];
    // dp
    for (int i = 1; i <= n; i++)
        for (int j = v[i]; j <= m; j++)
            dp[j] = max(dp[j], w[i] + dp[j - v[i]]);
    // 输出
    cout << "max=" << dp[m] << "\n";
    return 0;
}

#include <bits/stdc++.h>
using namespace std;
int n, m;    // 物品数量、背包大小
int v[35];   // v[i]：第i件物品的大小
int w[35];   // w[i]：第i件物品的价值
int dp[205]; // dp[j]：j 的体积下的最大价值
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    // 输入
    cin >> m >> n;
    for (int i = 1; i <= n; i++)
        cin >> v[i] >> w[i];
    // dp
    for (int i = 1; i <= n; i++)
    {
        int pi = m / v[i]; // 第i种物品最多选取的件数
        for (int t = 1; t <= pi; t++)
            // 尝试使用 (v[i],w[i]) 这件物品，01 地去更新 dp 数组
            for (int j = m; j >= v[i]; j--)
            {
                // dp[j+1]~dp[m] : 前 i 件物品的情况
                // dp[0] ~ dp[j] : 前 i-1 件物品的情况
                dp[j] = max(dp[j], w[i] + dp[j - v[i]]);
            }
    }
    // 输出
    cout << "max=" << dp[m] << "\n";
    return 0;
}

#include <bits/stdc++.h>
using namespace std;
int n, m;    // 物品数量、背包大小
int v[35];   // v[i]：第i件物品的大小
int w[35];   // w[i]：第i件物品的价值
int dp[205]; // dp[j]：j 的体积下的最大价值
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    // 输入
    cin >> m >> n;
    for (int i = 1; i <= n; i++)
        cin >> v[i] >> w[i];
    // dp
    for (int i = 1; i <= n; i++)
    {
        int pi = m / v[i]; // 第i种物品最多选取的件数
        for (int t = 1; t <= pi; t *= 2)
        {
            pi -= t;
            // 尝试使用 (v[i]*t,w[i]*t) 这件物品，01 地去更新 dp 数组
            for (int j = m; j >= v[i] * t; j--)
            {
                // dp[j+1]~dp[m] : 前 i 件物品的情况
                // dp[0] ~ dp[j] : 前 i-1 件物品的情况
                dp[j] = max(dp[j], w[i] * t + dp[j - v[i] * t]);
            }
        }
        if (pi > 0)
        {
            // 尝试使用 (v[i]*pi,w[i]*pi) 这件物品，01 地去更新 dp 数组
            for (int j = m; j >= v[i] * pi; j--)
            {
                // dp[j+1]~dp[m] : 前 i 件物品的情况
                // dp[0] ~ dp[j] : 前 i-1 件物品的情况
                dp[j] = max(dp[j], w[i] * pi + dp[j - v[i] * pi]);
            }
        }
    }
    // 输出
    cout << "max=" << dp[m] << "\n";
    return 0;
}