#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
const int N = 3200 + 10, M = 60, S = 15;
struct package {
    int n, v[S], w[S];
} T[M];
int n, m, v[M], p[M], q[M];
int f[N], s;
int main() {
    freopen("budgetb.in","r",stdin);
    freopen("budgetb.out","w",stdout);
    scanf("%d %d %d", &n, &m, &s);
    n /= 10;
    for(int i=1; i<=m; i++) {
        scanf("%d %d %d", &v[i], &p[i], &q[i]);
        v[i] /= 10;
        if(!q[i]) {
            T[i].n++;
            T[i].v[1] = v[i];
            T[i].w[1] = v[i] * p[i];
        }
    } int u = 0;
    for(int i=1; i<=m; i++) if((u = q[i]))
        for(s = T[u].n; s > 0; s--) {
            T[u].n++;
            T[u].v[T[u].n] = T[u].v[s] + v[i];
            T[u].w[T[u].n] = T[u].w[s] + v[i] * p[i];
        }
    for(int i=1; i<=m; i++) if(T[i].n)
        for(int k=n; k>=0; k--)
            for(int j=1; j<=T[i].n; j++) if(k >= T[i].v[j])
                f[k] = max(f[k], f[k - T[i].v[j]] + T[i].w[j]);
    printf("%d\n", f[n] * 10);
    return 0;
}