MLML520 @ 2017-07-19 10:03:07
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
int f[70][32500], son[70][4], v[70], w[70], ha[70], b[70][4];
int main()
{
int m, n, i, j, ans = 0;
memset(f, 0, sizeof(f));
scanf("%d %d", &m, &n);
m /= 10;
for(i = 1; i <= n; i++)
scanf("%d %d %d", &v[i], &w[i], &ha[i]);
for(i = 1; i <= n; i++)
v[i] /= 10;
for(i = 1; i <= n; i++)
{
if(ha[i] != 0)
{
if(son[ha[i]][1] == 0)
{
son[ha[i]][1] = i;
b[ha[i]][1] = v[i] * w[i];
}
else
{
son[ha[i]][2] = i;
b[ha[i]][2] = v[i] * w[i];
}
}
else
b[i][0] = v[i] * w[i];
}
for(i = 1; i <= n; i++)
{
for(j = 1; j <= m; j++)
{
if(ha[i] != 0)
continue;
else
{
if(j >= v[i])
{
f[i][j] = max(f[i][j], f[i - 1][j - v[i]] + b[i][0]);
if(j >= (v[i] + v[son[i][1]]))
f[i][j] = max(f[i][j], f[i - 1][j - v[i] - v[son[i][1]]] + b[i][0] + b[i][1]);
if(j >= (v[i] + v[son[i][2]]))
f[i][j] = max(f[i][j], f[i - 1][j - v[i] - v[son[i][2]]] + b[i][0] + b[i][2]);
if(j >= (v[i] + v[son[i][1]] + v[son[i][2]]))
f[i][j] = max(f[i][j], f[i - 1][j - v[i] - v[son[i][1]] - v[son[i][2]]] + b[i][0] + b[i][1] + b[i][2]);
}
else
f[i][j] = f[i][j - 1];
}
}
}
printf("%d", f[n][m] * 10);
return 0;
}