// 树，树上节点有奶牛
// 把所有奶牛合到一个地方，
// 找一个合适的节点，求出最小的不方便度
// 暴力，依次枚举每一个节点作为集合点， 依次DFS 求最小值
//  换根 DP
// 第一遍 DFS 求 以 1 为根节点的不方便值
// f[u] += f[v] + siz[v] * w     w : u 到 v 的边权值

void dfs1(int u, int fa) {
	siz[u] = c[u];
	for (int i = head[u] ; i; i = nxt[i]) {
		int v = ver[i];
		int w = edge[i];
		if (v == fa)
			continue;
		dfs(v, u);
		siz[u] += siz[v];
		f[u] += f[v] + siz[v] * w;
	}
}

int ans = 1e18;

void dfs2(int u, int fa) {
	for (int i = head[u] ; i ; i = nxt[i]) {
		int v = ver[i];
		int w = edge[i];
		if (v == fa)
			continue;
		// 之前的根是 u，现在换成 v
    // sum 所有奶牛的数量
		f[v] = f[u] - siz[v] * w + (sum - siz[v]) * w;
		ans = min(ans, f[v]);
		dfs(v, u);
	}
}

// 拆点建树
// 入口，分岔口，画室看作节点
// 走廊时间看作边权，画室内的每幅画看作叶子节点
// 取画时间看作边权，取每一个画的时间是独立的，01背包

// f[u][j] 表示在 u 的子树中，花费 j 秒，获得的最大画数
// siz[u] 记录在当前 u 子树中的花费时间
// 初始值，f[0][0] =1, 每个叶子节点有一副画，取画时间转移到边上
// f[u][j] = max(f[u][j] , f[u][j-k-t] + f[v][k])
// 在 v 子树中花费 k 秒，在已遍历的 u 子树中花费 j-k-t 秒
// 因为要抠去 (u,v) 的边权 t, 这样就凑出合并子树中花费 j 秒获得的最大画数
// ans = f[1][n]


#include<bits/stdc++.h>
using namespace std;
const int N = 6010;
const int M = N * 2;
int n, tot;
int head[N], ver[M], nxt[M], edge[M], idx;
int ans, f[N][N], siz[N];

void add(int u, int v, int w) {
	++idx;
	ver[idx] = v;
	nxt[idx] = head[u];
	head[u] = idx;
	edge[idx] = w;
}

void build(int u, int fa) {
	int t, p;
	cin >> t >> p;
	add(fa, u, t * 2);
	if (!p)
		build(++tot, u), build(++tot, u);
	else
		while (p--)
			add(u, 0, 5);
}

void dfs(int u) {
	for (int i = head[u] ; i ; i = nxt[i]) {
		int v = ver[i], t = edge[i];
		dfs(v);
		siz[u] += siz[v] + t;
		for (int j  = min(n, siz[u]); j >= t ; j--)
			for (int k = 0; k <= min(j - t, siz[v]) ; k++)
				f[u][j] = max(f[u][j], f[u][j - k - t] + f[v][k]);
	}
}

int main() {
	cin >> n;
	n--;
	tot = 1;
	build(++tot, 1);
	f[0][0] = 1;
	dfs(1);
	cout << f[1][n];
	return 0;
}

//  求形成一个 P 个节点的树需要破坏的最少道路数量
//  f[u][j]  以 u 为根，包含 j 个节点，需要破坏的最少道路数量
//  min(f[i][p] )  i 属于 1 - n

// 状态转移： 子树到根的状态转移
// u - v 这条边是不是必须保留，f[v][k] 删除了一次，f[u][j-k] 删除了一次
//  所以需要 减2 来弥补
// f[u][j] = min(f[u][j]  ,f[v][k] + f[u][j-k] -2)

void dfs(int u, int fa) {
	siz[u] = 1;
	for (int i = head[u] ; i ; i = nxt[i]) {
		int v = ver[i];
		if (v == fa)
			continue;
		dfs(v, u);
		siz[u] += siz[v];
		// 背包
		for (int j = siz[u] ; j >= 1; j--) {
			for (int k = 1; k <= min(j - 1, siz[v]) ; k++) {
				f[u][j] = min(f[u][j], f[u][j - k] + f[v][k] - 2);
			}
		}
	}
}

// 初始化
void init() {
	memset(f, 0x3f, sizeof f);
	for (int i = 1; i <= n; i++)
		f[i][1] = du[i];
}

void print() {
	int ans = f[1][p];
	for (int i = 2; i <= n; i++)
		ans = min(ans, f[i][p]);
	cout << ans;
}

// f[u][i] 以 u 为根节点，花费 i 元获得的最大价值
// 树上背包
#include <bits/stdc++.h>
using namespace std;
const int N = 32010;
const int M = 70;
int n, money;
int v[M], w[M];
vector<int> e[M];
int f[M][N];

void dfs(int u) {
	// u 这个节点必须选择
	f[u][v[u]] = w[u];
	// 遍历子节点，看是否选择
	for (auto t : e[u]) {
		dfs(t);
		// 分组背包
		for (int j = money ; j >= v[u] ; j--) {
			// 分配给 t 这个子节多少钱
			for (int k = 0 ; k <= j - v[u] ; k++)
				f[u][j] = max(f[u][j], f[t][k] + f[u][j - k]);
		}
	}
}

int main() {
	cin >> money >> n;
	money /= 10;
	for (int i = 1; i <= n; i++) {
		int x, y, z;
		cin >> x >> y >> z;
		v[i] = x / 10;
		w[i] = x * y;
		e[z].push_back(i);
	}
	dfs(0);
	cout << f[0][money];
	return 0;
}