/*
针对第i个游戏机
f[j]预算为j元的时候的最大价值
tmp[j]前i-1个
for(int i=cost;i<=m;i++){
	f[j] = tmp[j-cost]
}
for(int i=1;i<=tot;i++){
	x价格,y价值
	for(int j=m;j>=x;j--){
		f[j] = max(f[j],f[j-x]+y);
	}
}
for(int i=1;i<=m;i++)f[i] = max(f[i],tmp[i])
*/
#include <bits/stdc++.h>
using namespace std;
const int N = 55;
int n, m, f[1000005], tmp[1000005];

int main() {
	cin >> n >> m;
	for (int i = 1; i <= n; i++) {
		int cost, tot;
		cin >> cost >> tot;
		memset(f, 0xcf, sizeof(f));
		for (int j = cost; j <= m; j++)
			f[j] = tmp[j - cost];
		while (tot--) {
			int x, y;
			cin >> x >> y;
			for (int j = m; j >= x; j--) {
				f[j] = max(f[j], f[j - x] + y);
			}
		}
		for (int j = 0; j <= m; j++) {
			f[j] = max(f[j], tmp[j]);
			tmp[j] = f[j];
		}
	}
	cout << f[m] << endl;
	return 0;
}

/*
h[i]第i个方块的高度
a[i]第i个方块的最大高度
c[i]第i个方块的数量

先放限制高度低的
*/
#include <bits/stdc++.h>
using namespace std;
const int N = 4005;
struct node {
	int c, v;
} p[N];
int n, f[1000005];

bool cmp(node a, node b) {
	return a.v < b.v;
}

int main() {
	cin >> n;
	int cnt = 0;
	for (int i = 1; i <= n; i++) {
		int x, y, z;
		cin >> x >> y >> z;
		for (int j = 1; j <= z; j *= 2) {
			p[++cnt].v = y;
			p[cnt].c = j * x;
			z -= j;
		}
		if (z) {
			p[++cnt].v = y;
			p[cnt].c = z * x;
		}
	}
	sort(p + 1, p + cnt + 1, cmp);
	int res = 0;
	for (int i = 1; i <= cnt; i++) {
		for (int j = p[i].v; j >= p[i].c; j--) {
			f[j] = max(f[j], f[j - p[i].c] + p[i].c);
			res = max(res, f[j]);
		}
	}
	cout << res << endl;
	return 0;
}

/*
f[j]派出j名士兵的最大价值
f[j] = max(f[j],f[j-2*a[i]]+i)
*/
#include <bits/stdc++.h>
using namespace std;
const int N = 105;
int s, n, m;
int a[105][105];
int f[20005];

int main() {
	cin >> s >> n >> m;
	for (int i = 1; i <= s; i++) {
		for (int j = 1; j <= n; j++) {
			cin >> a[j][i];
		}
	}
	for (int i = 1; i <= n; i++) {
		sort(a[i] + 1, a[i] + s + 1);
	}
	for (int i = 1; i <= n; i++) {
		for (int j = m; j >= 0; j--) {
			for (int k = 1; k <= s; k++) {
				if (j > 2 * a[i][k]) {
					f[j] = max(f[j], f[j - 2 * a[i][k] - 1] + k * i);
				}
			}
		}
	}
	cout << f[m] << endl;
	return 0;
}

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 5005;
int n, m, f[N];
vector<int>e[N];
int w[N], a[N];

int dfs(int x) {
	//x点有一个棋子的最大游戏次数
	if (f[x])
		return f[x];
	int dp[N];
	memset(dp, 0, sizeof(dp));
	for (auto v : e[x]) {
		if (w[v] < w[x]) {
			int c = dfs(v);
			for (int j = w[x] - 1; j >= w[v]; j--) {
				dp[j] = max(dp[j], dp[j - w[v]] + c);
			}
		}
	}
	f[x] = dp[w[x] - 1] + 1;
	return f[x];
}

signed main() {
	cin >> n >> m;
	for (int i = 1; i <= m; i++) {
		int x, y;
		cin >> x >> y;
		e[x].push_back(y);
		e[y].push_back(x);
	}
	for (int i = 1; i <= n; i++)
		cin >> w[i];
	for (int i = 1; i <= n; i++)
		cin >> a[i];
	for (int i = 1; i <= n; i++) {
		if (!f[i]) {
			int c = dfs(i);
		}
	}
	int res = 0;
	for (int i = 1; i <= n; i++) {
		res += f[i] * a[i];
	}
	cout << res << endl;
	return 0;
}

#include <bits/stdc++.h>
using namespace std;

struct node {
	int v, c;
} p[3005];
int n, f[6005], m;

bool cmp(node a, node b) {
	return a.v < b.v;
}

int main() {
	cin >> n >> m;
	for (int i = 1; i <= n; i++) {
		cin >> p[i].v >> p[i].c;
	}
	sort(p + 1, p + n + 1, cmp);
	int res = 0;
	for (int i = 1; i <= n; i++) {
		for (int j = m + p[i].v - 1; j >= p[i].v; j--) {
			f[j] = max(f[j], f[j - p[i].v] + p[i].c);
			res = max(res, f[j]);
		}
	}
	cout << res << endl;
	return 0;
}

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 1025;
int n, m, v[N], c[N], t[N], f[N][N];
int fa[N];
int g;
vector<int> e[N];
signed main() {
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        cin >> t[i] >> c[i] >> v[i];
        if (t[i] == 0)
            t[i] = m / v[i] + 10;
    }
    memset(fa, -1, sizeof(fa));
    int g;
    cin >> g;
    int cnt = 0;
    for (int i = 1; i <= g; i++) {
        int T;
        cin >> T;
        for (int j = 1; j <= T; j++) {
            int x;
            cin >> x;
            fa[x] = i;
            cnt = i;
        }
    }
    for (int i = 1; i <= n; i++) {
        if (fa[i] == -1)
            e[++cnt].push_back(i);
        else {
            e[fa[i]].push_back(i);
        }
    }
    for (int i = 0; i <= n; i++) {
        for (int j = 0; j <= m; j++) f[i][j] = -1e9;
    }
    f[0][0] = 0;
    for (int i = 1; i <= cnt; i++) {
        for (int j = 0; j <= m; j++) f[i][j] = f[i - 1][j];
        for (int j = 0; j <= m; j++) {
            for (auto V : e[i]) {
                for (int k = 0; k <= t[V]; k++) {
                    if (j >= k * v[V]) {
                        if (f[i - 1][j - k * v[V]] != -1e9)
                            f[i][j] = max(f[i][j], f[i - 1][j - k * v[V]] + k * c[V]);
                    }
                }
            }
        }
        for (int j = 0; j <= m; j++) {
            f[i][j] = max(f[i][j], f[i - 1][j]);
        }
    }
    if (f[cnt][m] != -1e9)
        cout << f[cnt][m] << endl;
    else
        cout << "i'm sorry..." << endl;
    return 0;
}

#include <bits/stdc++.h>
using namespace std;
const int N = 605;
int n, m, f[32005], v[N], c[N], a[N], b[N], t[N];
vector<int>e[N];

int main() {
	cin >> m >> n;
	for (int i = 1; i <= n; i++) {
		int x;
		cin >> v[i] >> c[i] >> x;
		if (x != 0) {
			e[x].push_back(i);
		}
		c[i] = v[i]*c[i];
		t[i] = x;
	}
	for(int i=1;i<=n;i++){
		for(int j=m;j>=0;j--){
			if(t[i]==0){
				//1.主件
				if(j>=v[i])
					f[j] = max(f[j],f[j-v[i]]+c[i]);
				//2.主件+附件1
				if(e[i].size()>=1){
					if(j>=v[i]+v[e[i][0]]){
						f[j] = max(f[j],f[j-v[i]-v[e[i][0]]]+c[i]+c[e[i][0]]);
					}
				}
				//3.主件+附件2
				if(e[i].size()>=2){
					if(j>=v[i]+v[e[i][1]]){
						f[j] = max(f[j],f[j-v[i]-v[e[i][1]]]+c[i]+c[e[i][1]]);
					}
					if(j>=v[i]+v[e[i][0]]+v[e[i][1]]){
						f[j] = max(f[j],f[j-v[i]-v[e[i][0]]-v[e[i][1]]]+c[i]+c[e[i][0]]+c[e[i][1]]);
					}
				}
			}
		}
	}
	cout << f[m] << endl;
	return 0;
}