#include <bits/stdc++.h>
using namespace std;
const int MAXN = 30;
const int MAXM = 200;
const int MAXT = 10;
int n, m, t;
int num[MAXT + 5];         // 可以用 v[i][0] 代替
int v[MAXT + 5][MAXN + 5]; // v[i][j]: 第i组第j个物品对应的体积
int w[MAXT + 5][MAXN + 5]; // w[i][j]: 第i组第j个物品对应的价值
int dp[MAXM + 5];
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> m >> n >> t;
    for (int i = 1; i <= n; i++)
    {
        int vv, ww, tt;
        cin >> vv >> ww >> tt;
        // 放入第 tt 组
        num[tt]++;
        v[tt][num[tt]] = vv;
        w[tt][num[tt]] = ww;
    }
    for (int k = 1; k <= t; k++) // 枚举组
    {
        for (int j = m; j >= 0; j--)          // 枚举每个体积
            for (int i = 1; i <= num[k]; i++) // 枚举组内物品
            {
                // 每个体积最终只会被组内的一个物品刷新
                // 组内物品之间不会叠加
                if (v[k][i] <= j)
                    dp[j] = max(dp[j],
                                dp[j - v[k][i]] + w[k][i]);
            }
        // 第一组处理完每个体积后再处理第二组
        // 保证了两组之间允许叠加
    }
    cout << dp[m] << "\n";
    return 0;
}