#include <iostream>
#include <cstdio>
#include <cstring>

using namespace std;

const int K = 1e3 + 10;

int o2[K], n2[K], weight[K];

const int M = 25, N = 85;

int dp[M][N];

int main()
{
    int m, n, k;
    scanf("%d%d%d", &m, &n, &k);

    for(int i = 1; i <= k; i++)
    {
        scanf("%d%d%d", &o2[i], &n2[i], &weight[i]);
    }

    memset(dp, 0x3f, sizeof dp);
    dp[0][0] = 0;

    for(int i = 1; i <= k; i++)
    {
        for(int j = m; j >= 0; j--)
        {
            for(int u = n; u >= 0; u--)
            {
                dp[j][u] = min(dp[j][u], dp[max(0, j - o2[i])][max(0, u - n2[i])] + weight[i]);
            }
        }
    }

    printf("%d\n", dp[m][n]);
}

#include <iostream>
#include <cstdio>

using namespace std;

const int N = 1e3 + 10;

int volume[N], weight[N];

int dp[N][N];

int main()
{
    int n, v;
    scanf("%d%d", &n, &v);

    for(int i = 1; i <= n; i++)
    {
        scanf("%d%d", &volume[i], &weight[i]);
    }

    for(int i = n; i >= 1; i--)
    {
        for(int j = 0; j <= v; j++)
        {
            dp[i][j] = dp[i+1][j];

            if(j >= volume[i]) dp[i][j] = max(dp[i+1][j], dp[i+1][j - volume[i]] + weight[i]);
        }
    }

    for(int i = 1, j = v; i <= n; i++)
    {
        if(j >= volume[i] && dp[i][j] == dp[i+1][j - volume[i]] + weight[i]) 
        {
            printf("%d ", i);

            j = j - volume[i];
        }
    }
    puts("");
}

#include <iostream>
#include <cstdio>

using namespace std;

const int N = 510, M = 6e3 + 10;

int v[N], w[N], s[N];

// int dp[N][M];
int dp[M];

int main()
{
    int n, m;
    scanf("%d%d", &n, &m);

    for(int i = 1; i <= n; i++)
    {
        scanf("%d%d%d", &v[i], &w[i], &s[i]);
    }

    for(int i = 1; i <= n; i++)
    {
        // for(int j = 0; j <= m; j++)
        for(int j = m; j >= 0; j--)
        {
            for(int k = 0; k <= s[i] && j >= k * v[i]; k++)
            {
                dp[j] = max(dp[j], dp[j - k*v[i]] + k * w[i]);
            }
        }
    }

    printf("%d\n", dp[m]);

    // for(int i = 1; i <= n; i++)
    // {
    //     for(int j = 0; j <= m; j++)
    //     {
    //         for(int k = 0; k <= s[i] && j >= k * v[i]; k++)
    //         {
    //             dp[i][j] = max(dp[i][j], dp[i-1][j - k*v[i]] + k * w[i]);
    //         }
    //     }
    // }
    //
    // printf("%d\n", dp[n][m]);
}

#include <iostream>
#include <cstdio>

using namespace std;

int v[] = {0, 10, 20, 50, 100};

const int N = 1010;

// int dp[5][N];

int dp[N];

int main()
{
    int n;
    scanf("%d", &n);

    dp[0] = 1;
    for(int i = 1; i <= 4; i++)
    {
        for(int j = v[i]; j <= n; j++)
        {
            dp[j] = dp[j] + dp[j - v[i]];
        }
    }

    printf("%d\n", dp[n]);

    // dp[0][0] = 1;
    // for(int i = 1; i <= 4; i++)
    // {
    //     for(int j = 0; j <= n; j++)
    //     {
    //         if(j == 0) dp[i][j] = 1;
    //
    //         dp[i][j] = dp[i-1][j];
    //
    //         if(j - v[i] >= 0) dp[i][j] = dp[i][j] + dp[i][j - v[i]];
    //     }
    // }
    //
    // printf("%d\n", dp[4][n]);
}

#include <iostream>
#include <cstdio>

using namespace std;

const int N = 110;

int v[N];

const int M = 1e4 + 10;

int dp[M];

int main()
{
    int n, m;
    scanf("%d%d", &n, &m);

    for(int i = 1; i <= n; i++)
    {
        scanf("%d", &v[i]);
    }

    // dp[0][0] = 1;
    // for(int i = 1; i <= n; i++)
    // {
    //     for(int j = 0; j <= m; j++)
    //     {
    //         if(j == 0) dp[i][j] = 1;
    //
    //         dp[i][j] = dp[i-1][j];
    //
    //         if(j - v[i] >= 0) dp[i][j] = dp[i][j] + dp[i-1][j - v[i]];
    //     }
    // }

    dp[0] = 1;
    for(int i = 1; i <= n; i++)
    {
        for(int j = m; j >= v[i]; j--)
        {
            if(j - v[i] >= 0) dp[j] = dp[j] + dp[j - v[i]];
        }
    }

    printf("%d\n", dp[m]);
}

#include <iostream>
#include <cstdio>

using namespace std;

const int N = 110;

int v1[N], v2[N];

const int M = 1e3 + 10;
const int K = 510;

int dp[M][K];

int main()
{
    int n, m, k;
    scanf("%d%d%d", &n, &m, &k);

    for(int i = 1; i <= k; i++)
    {
        scanf("%d%d", &v1[i], &v2[i]);
    }

    // for(int i = 1; i <= k; i++)
    // {
    //     for(int j = 0; j <= n; j++)
    //     {
    //         for(int u = 0; u < m; u++)
    //         {
    //             dp[i][j][u] = dp[i-1][j][u];
    //
    //             if(j - v1[i] >= 0 && u - v2[i] >= 0)
    //                 dp[i][j][u] = max(dp[i][j][u], dp[i-1][j - v1[i]][u - v2[i]] + 1);
    //         }
    //     }
    // }

    for(int i = 1; i <= k; i++)
    {
        for(int j = n; j >= v1[i]; j--)
        {
            for(int u = m-1; u >= v2[i]; u--)
            {
                    dp[j][u] = max(dp[j][u], dp[j - v1[i]][u - v2[i]] + 1);
            }
        }
    }

    printf("%d ", dp[n][m-1]);

    int res = -1;
    for(int i = 0; i <= m-1; i++)
    {
        if(dp[n][i] == dp[n][m-1])
        {
            res = i;
            break;
        }
    }

    printf("%d\n", m - res);
}

#include <iostream>
#include <cstdio>

using namespace std;

const int N = 40;

int volume[N];

const int M = 2e4 + 10;

int dp[M];

int main()
{
    int v, n;
    scanf("%d%d", &v, &n);

    for(int i = 1; i <= n; i++)
    {
        scanf("%d", &volume[i]);
    }

    for(int i = 1; i <= n; i++)
    {
        for(int j = v; j >= volume[i]; j--)
        {
            dp[j] = max(dp[j], dp[j - volume[i]] + volume[i]);
        }
    }

    printf("%d\n", v - dp[v]);
}

#include <iostream>
#include <cstdio>

using namespace std;

const int N = 1e2 + 10;

int my_time[N], my_value[N];

const int M = 1e3 + 10;

int dp[M];

int main()
{
    int t, m;
    scanf("%d%d", &t, &m);

    for(int i = 1; i <= m; i++)
    {
        scanf("%d%d", &my_time[i], &my_value[i]);
    }

    for(int i = 1; i <= m; i++)
    {
        for(int j = t; j >= my_time[i]; j--)
        {
            dp[j] = max(dp[j], dp[j - my_time[i]] + my_value[i]);
        }
    }

    printf("%d\n", dp[t]);
}

#include <iostream>
#include <cstdio>

using namespace std;

const int N = 3e3 + 10;

int a[N], b[N];
int dp[N][N];

// int tmp[N][N];

int main()
{
    int n;
    scanf("%d", &n);

    for(int i = 1; i <= n; i++)
    {
        scanf("%d", &a[i]);
    }

    for(int i = 1; i <= n; i++)
    {
        scanf("%d", &b[i]);
    }

    // for(int i = 1; i <= n; i++)
    // {
    //     tmp[i][0] = 1;
    //     for(int j = 1; j <= n; j++)
    //     {
    //         dp[i][j] = dp[i-1][j];
    //
    //         if(a[i] == b[j])
    //         {
    //             dp[i][j] = max(dp[i][j], tmp[i][j-1]);
    //         }
    //
    //         tmp[i][j] = tmp[i][j-1];
    //         // if(a[i] == b[j] && b[j] < a[i])
    //         if(b[j] < a[i])
    //         {
    //             tmp[i][j] = max(tmp[i][j], dp[i][j] + 1);
    //         }
    //     }
    // }

    // 本质是找在k为[1,j-1]的范围内，满足b[k] < a[i]时的dp[i][k]+1的最大值，用这个值来更新dp[i][j]
    for(int i = 1; i <= n; i++)
    {
        int maxv = 1;
        for(int j = 1; j <= n; j++)
        {
            dp[i][j] = dp[i-1][j];

            if(a[i] == b[j])
            {
                dp[i][j] = max(dp[i][j], maxv);
            }

            // tmp[i][j] = tmp[i][j-1];
            // if(a[i] == b[j] && b[j] < a[i])
            if(b[j] < a[i])
            {
                maxv = max(maxv, dp[i][j] + 1);
            }
        }
    }

    // for(int i = 1; i <= n; i++)
    // {
    //     for(int j = 1; j <= n; j++)
    //     {
    //         dp[i][j] = dp[i-1][j];
    //
    //         if(a[i] == b[j])
    //         {
    //             dp[i][j] = max(dp[i][j], 1);
    //
    //             for(int k = 1; k < j; k++)
    //             {
    //                 if(b[k] < b[j])
    //                 {
    //                     dp[i][j] = max(dp[i][j], dp[i][k] + 1);
    //                 }
    //             }
    //         }
    //     }
    // }

    int res = 0;
    for(int j = 1; j <= n; j++)
    {
        res = max(res, dp[n][j]);
    }

    printf("%d\n", res);
}

#include <iostream>
#include <cstdio>

using namespace std;

const int N = 1e3 + 10;

int height[N];

int dp[N];

int last_value[N];

int main()
{
    int n;
    for(n = 0; scanf("%d", &height[n]) != -1; n++)
    {

    }


    int res = 0;
    for(int i = 0; i < n; i++)
    {
        dp[i] = 1;

        for(int j = 0; j < i; j++)
        {
            if(height[j] >= height[i])
            {
                dp[i] = max(dp[i], dp[j] + 1);
            }
        }

        res = max(res, dp[i]);
    }

    printf("%d\n", res);

    int cnt = 0;
    for(int i = 0; i < n; i++)
    {
        int index = 0;
        while(index < cnt && last_value[index] < height[i]) index++;
        last_value[index] = height[i];
        if(index >= cnt) cnt++;
    }

    printf("%d\n", cnt);
}