stablegradients/pie-gem5-pairs huggingface dataset:
// Slower C++ solution:
#include <iostream>

#include <cstdio>

#include <cstdlib>

#include <cmath>

#include <algorithm>

#include <cstring>

#include <vector>



using namespace std;



inline int gi()

{

	int f = 1, x = 0;

	char c = getchar();

	while (c < '0' || c > '9')

	{

		if (c == '-')

			f = -1;

		c = getchar();

	}

	while (c >= '0' && c <= '9')

	{

		x = x * 10 + c - '0';

		c = getchar();

	}

	return f * x;

}



const int mod = 1000000007;

vector<int> G[5005];

int f[5005][5005], g[5005], tmp[5005], n, sz[5005];



void dfs(int u, int fa)

{

	f[u][sz[u] = 1] = 1;

	for (auto v : G[u])

	{

		if (v != fa)

		{

			dfs(v, u);

			for (int i = 1; i <= sz[u] + sz[v]; i++) tmp[i] = 0;

			for (int i = 1; i <= sz[u]; i++)

			{

				for (int j = 0; j <= sz[v]; j++)

				{

					tmp[i + j] = (tmp[i + j] + 1ll * f[u][i] * f[v][j] % mod) % mod;

				}

			}

			for (int i = 1; i <= sz[u] + sz[v]; i++) f[u][i] = tmp[i];

			sz[u] = sz[u] + sz[v];

		}

	}

	for (int i = 2; i <= sz[u]; i = i + 2) f[u][0] = (f[u][0] + mod - 1ll * f[u][i] * g[i] % mod) % mod;

}



int main()

{

	g[0] = 1, n = gi();

	for (int i = 2; i <= n; i = i + 2) g[i] = 1ll * g[i - 2] * (i - 1) % mod;

	for (int i = 1; i < n; i++)

	{

		int x = gi(), y = gi();

		G[x].push_back(y), G[y].push_back(x);

	}

	dfs(1, 0);

	printf("%d\n", mod - f[1][0]);

	return 0;

}


// Faster C++ solution for the same problem (measured speedup: 1.132704317025989x):
#include<bits/stdc++.h>

using namespace std;

typedef int ll;

typedef long long int li;

const ll MAXN=5e3+51,MOD=1e9+7;

struct Edge{

	ll to,prev;

};

Edge ed[MAXN<<1];

ll nc,tot,from,to;

ll last[MAXN],sz[MAXN],f[MAXN],tmp[MAXN],dp[MAXN][MAXN];

inline ll read()

{

    register ll num=0,neg=1;

    register char ch=getchar();

    while(!isdigit(ch)&&ch!='-')

    {

        ch=getchar();

    }

    if(ch=='-')

    {

        neg=-1;

        ch=getchar();

    }

    while(isdigit(ch))

    {

        num=(num<<3)+(num<<1)+(ch-'0');

        ch=getchar();

    }

    return num*neg;

}

inline void addEdge(ll from,ll to)

{

	ed[++tot].prev=last[from];

	ed[tot].to=to;

	last[from]=tot;

}

inline void dfs(ll node,ll fa)

{

	ll p;

	sz[node]=dp[node][1]=1;

	for(register int i=last[node];i;i=ed[i].prev)

	{

		if(ed[i].to!=fa)

		{

			dfs(ed[i].to,node);

			for(register int j=0;j<=sz[node];j++)

			{

				tmp[j]=dp[node][j],dp[node][j]=0;

			}

			for(register int j=0;j<=sz[node];j++)

			{

				for(register int k=0;k<=sz[ed[i].to];k++)

				{

					p=(li)tmp[j]*dp[ed[i].to][k]%MOD;

					dp[node][j+k]=(dp[node][j+k]+p)%MOD;

				}

			}

			sz[node]+=sz[ed[i].to];

		}

	}

	for(register int i=0;i<=sz[node];i+=2)

	{

		dp[node][0]=(dp[node][0]+MOD-(li)dp[node][i]*f[i]%MOD)%MOD;

	}

}

int main()

{

	nc=read(),f[0]=1;

	for(register int i=0;i<nc-1;i++)

	{

		from=read(),to=read();

		addEdge(from,to),addEdge(to,from);

	}

	for(register int i=2;i<=nc;i++)

	{

		f[i]=(li)f[i-2]*(i-1)%MOD;

	}

	dfs(1,0),printf("%d\n",(MOD-dp[1][0])%MOD);

}
// Slower C++ solution:
#include<bits/stdc++.h>

#define rep(i,a,b) for(int i=(a);i<=(b);i++)

#define per(i,a,b) for(int i=(a);i>=(b);i--)

#define REP(i,n) for(int i=(0);i<(n);i++)

#define fi first

#define se second

#define pb push_back

#define mp make_pair

using namespace std;

typedef pair<int,int> pii;

typedef vector<int> vi;

typedef long long ll;



template<class T> inline void read(T &x){

	int f=0;x=0;char ch=getchar();

	for(;!isdigit(ch);ch=getchar())f|=(ch=='-');

	for(;isdigit(ch);ch=getchar())x=x*10+ch-'0';

	if(f)x=-x;

}



const int N=5005,mod=1e9+7,inv2=(mod+1)/2;

int f[N][N],fac[N],rev[N],g[N],sz[N],t[N],n,x,y;

vi e[N];



int power(int x,int p){

	int res=1;

	for(;p;p>>=1,x=(ll)x*x%mod)

		if(p&1)res=(ll)res*x%mod;

	return res;

}



void dfs(int u,int fa){

	f[u][1]=sz[u]=1;

	for(auto v:e[u])

		if(v!=fa){

			dfs(v,u);

			fill(g,g+sz[u]+sz[v]+1,0);

			rep(a,1,sz[u])rep(b,0,sz[v])

				g[a+b]=(g[a+b]+(ll)f[u][a]*f[v][b])%mod;

			sz[u]+=sz[v];

			rep(a,1,sz[u])f[u][a]=g[a];

		}

	int sum=0;

	rep(i,1,sz[u])

		if(i%2==0&&f[u][i])

			sum=(sum+(ll)f[u][i]*t[i])%mod;

	f[u][0]=mod-sum;

}



int main(){

	read(n);

	fac[0]=1;

	rep(i,1,n)fac[i]=(ll)fac[i-1]*i%mod;

	rev[n]=power(fac[n],mod-2);

	per(i,n,1)rev[i-1]=(ll)rev[i]*i%mod;

	rep(i,1,n)if(i%2==0)

		t[i]=(ll)fac[i]*rev[i/2]%mod*power(inv2,i/2)%mod;

	rep(i,1,n-1){

		read(x),read(y);

		e[x].pb(y),e[y].pb(x);

	}

	dfs(1,0);

	printf("%d\n",(mod-f[1][0])%mod);

	return 0;

}

// Faster C++ solution for the same problem (measured speedup: 1.1344017187968773x):
#include<bits/stdc++.h>

using namespace std;

typedef int ll;

typedef long long int li;

const ll MAXN=5e3+51,MOD=1e9+7;

struct Edge{

	ll to,prev;

};

Edge ed[MAXN<<1];

ll nc,tot,from,to;

ll last[MAXN],sz[MAXN],f[MAXN],tmp[MAXN],dp[MAXN][MAXN];

inline ll read()

{

    register ll num=0,neg=1;

    register char ch=getchar();

    while(!isdigit(ch)&&ch!='-')

    {

        ch=getchar();

    }

    if(ch=='-')

    {

        neg=-1;

        ch=getchar();

    }

    while(isdigit(ch))

    {

        num=(num<<3)+(num<<1)+(ch-'0');

        ch=getchar();

    }

    return num*neg;

}

inline void addEdge(ll from,ll to)

{

	ed[++tot].prev=last[from];

	ed[tot].to=to;

	last[from]=tot;

}

inline void dfs(ll node,ll fa)

{

	ll p;

	sz[node]=dp[node][1]=1;

	for(register int i=last[node];i;i=ed[i].prev)

	{

		if(ed[i].to!=fa)

		{

			dfs(ed[i].to,node);

			for(register int j=0;j<=sz[node];j++)

			{

				tmp[j]=dp[node][j],dp[node][j]=0;

			}

			for(register int j=0;j<=sz[node];j++)

			{

				for(register int k=0;k<=sz[ed[i].to];k++)

				{

					p=(li)tmp[j]*dp[ed[i].to][k]%MOD;

					dp[node][j+k]=(dp[node][j+k]+p)%MOD;

				}

			}

			sz[node]+=sz[ed[i].to];

		}

	}

	for(register int i=0;i<=sz[node];i+=2)

	{

		dp[node][0]=(dp[node][0]+MOD-(li)dp[node][i]*f[i]%MOD)%MOD;

	}

}

int main()

{

	nc=read(),f[0]=1;

	for(register int i=0;i<nc-1;i++)

	{

		from=read(),to=read();

		addEdge(from,to),addEdge(to,from);

	}

	for(register int i=2;i<=nc;i++)

	{

		f[i]=(li)f[i-2]*(i-1)%MOD;

	}

	dfs(1,0),printf("%d\n",(MOD-dp[1][0])%MOD);

}
// Slower C++ solution:
#include <iostream>

#include <cstdio>

#include <cstdlib>

#include <cmath>

#include <algorithm>

#include <cstring>

#include <vector>



using namespace std;



inline int gi()

{

	int f = 1, x = 0;

	char c = getchar();

	while (c < '0' || c > '9')

	{

		if (c == '-')

			f = -1;

		c = getchar();

	}

	while (c >= '0' && c <= '9')

	{

		x = x * 10 + c - '0';

		c = getchar();

	}

	return f * x;

}



const int mod = 1000000007;

vector<int> G[5005];

int f[5005][5005], g[5005], tmp[5005], n, sz[5005];



void dfs(int u, int fa)

{

	f[u][sz[u] = 1] = 1;

	for (auto v : G[u])

	{

		if (v != fa)

		{

			dfs(v, u);

			for (int i = 1; i <= sz[u] + sz[v]; i++) tmp[i] = 0;

			for (int i = 1; i <= sz[u]; i++)

			{

				for (int j = 0; j <= sz[v]; j++)

				{

					tmp[i + j] = (tmp[i + j] + 1ll * f[u][i] * f[v][j] % mod) % mod;

				}

			}

			for (int i = 1; i <= sz[u] + sz[v]; i++) f[u][i] = tmp[i];

			sz[u] = sz[u] + sz[v];

		}

	}

	for (int i = 2; i <= sz[u]; i = i + 2) f[u][0] = (f[u][0] + mod - 1ll * f[u][i] * g[i] % mod) % mod;

}



int main()

{

	g[0] = 1, n = gi();

	for (int i = 2; i <= n; i = i + 2) g[i] = 1ll * g[i - 2] * (i - 1) % mod;

	for (int i = 1; i < n; i++)

	{

		int x = gi(), y = gi();

		G[x].push_back(y), G[y].push_back(x);

	}

	dfs(1, 0);

	printf("%d\n", mod - f[1][0]);

	return 0;

}


// Faster C++ solution for the same problem (measured speedup: 1.1188042240812255x):
#include<bits/stdc++.h>

using namespace std;



typedef long long LL;



const int N=5000,mod=1000000007;



int add(int a,int b,int p=mod){return a+b>=p?a+b-p:a+b;}

int sub(int a,int b,int p=mod){return a-b<0?a-b+p:a-b;}

int mul(int a,int b,int p=mod){return (LL)a*b%p;}

void sadd(int &a,int b,int p=mod){a=add(a,b,p);}

void ssub(int &a,int b,int p=mod){a=sub(a,b,p);}

void smul(int &a,int b,int p=mod){a=mul(a,b,p);}



int n;

struct side{

  int y,next;

}e[N*2+9];

int lin[N+9],cs;



void Ins(int x,int y){e[++cs].y=y;e[cs].next=lin[x];lin[x]=cs;}

void Ins2(int x,int y){Ins(x,y);Ins(y,x);}



void into(){

  scanf("%d",&n);

  for (int i=1;i<n;++i){

	int x,y;

	scanf("%d%d",&x,&y);

	Ins2(x,y);

  }

}



int g[N+9];



void Get_g(){

  g[0]=1;

  for (int i=2;i<=n;i+=2) g[i]=mul(g[i-2],i-1);

}



int siz[N+9],dp[N+9][N+9],tmp[N+9];



void Dfs_dp(int k,int fa){

  dp[k][1]=1;

  siz[k]=1;

  for (int i=lin[k];i;i=e[i].next)

	if (e[i].y^fa){

	  int y=e[i].y;

	  Dfs_dp(y,k);

	  for (int i=0;i<=siz[k];++i)

		for (int j=0;j<=siz[y];++j) sadd(tmp[i+j],mul(dp[k][i],dp[y][j]));

	  siz[k]+=siz[e[i].y];

	  for (int i=0;i<=siz[k];++i) dp[k][i]=tmp[i],tmp[i]=0;

	}

  for (int i=2;i<=siz[k];i+=2) ssub(dp[k][0],mul(dp[k][i],g[i]));

}



void work(){

  Get_g();

  Dfs_dp(1,0);

}



void outo(){

  printf("%d\n",sub(0,dp[1][0]));

}



int main(){

  into();

  work();

  outo();

  return 0;

}
// Slower C++ solution:
#include<bits/stdc++.h>

#define rep(i,a,b) for(int i=(a);i<=(b);i++)

#define per(i,a,b) for(int i=(a);i>=(b);i--)

#define REP(i,n) for(int i=(0);i<(n);i++)

#define fi first

#define se second

#define pb push_back

#define mp make_pair

using namespace std;

typedef pair<int,int> pii;

typedef vector<int> vi;

typedef long long ll;



template<class T> inline void read(T &x){

	int f=0;x=0;char ch=getchar();

	for(;!isdigit(ch);ch=getchar())f|=(ch=='-');

	for(;isdigit(ch);ch=getchar())x=x*10+ch-'0';

	if(f)x=-x;

}



const int N=5005,mod=1e9+7,inv2=(mod+1)/2;

int f[N][N],fac[N],rev[N],g[N],sz[N],t[N],n,x,y;

vi e[N];



int power(int x,int p){

	int res=1;

	for(;p;p>>=1,x=(ll)x*x%mod)

		if(p&1)res=(ll)res*x%mod;

	return res;

}



void dfs(int u,int fa){

	f[u][1]=sz[u]=1;

	for(auto v:e[u])

		if(v!=fa){

			dfs(v,u);

			fill(g,g+sz[u]+sz[v]+1,0);

			rep(a,1,sz[u])rep(b,0,sz[v])

				g[a+b]=(g[a+b]+(ll)f[u][a]*f[v][b])%mod;

			sz[u]+=sz[v];

			rep(a,1,sz[u])f[u][a]=g[a];

		}

	int sum=0;

	rep(i,1,sz[u])

		if(i%2==0&&f[u][i])

			sum=(sum+(ll)f[u][i]*t[i])%mod;

	f[u][0]=mod-sum;

}



int main(){

	read(n);

	fac[0]=1;

	rep(i,1,n)fac[i]=(ll)fac[i-1]*i%mod;

	rev[n]=power(fac[n],mod-2);

	per(i,n,1)rev[i-1]=(ll)rev[i]*i%mod;

	rep(i,1,n)if(i%2==0)

		t[i]=(ll)fac[i]*rev[i/2]%mod*power(inv2,i/2)%mod;

	rep(i,1,n-1){

		read(x),read(y);

		e[x].pb(y),e[y].pb(x);

	}

	dfs(1,0);

	printf("%d\n",(mod-f[1][0])%mod);

	return 0;

}

// Faster C++ solution for the same problem (measured speedup: 1.120480796018568x):
#include<bits/stdc++.h>

using namespace std;



typedef long long LL;



const int N=5000,mod=1000000007;



int add(int a,int b,int p=mod){return a+b>=p?a+b-p:a+b;}

int sub(int a,int b,int p=mod){return a-b<0?a-b+p:a-b;}

int mul(int a,int b,int p=mod){return (LL)a*b%p;}

void sadd(int &a,int b,int p=mod){a=add(a,b,p);}

void ssub(int &a,int b,int p=mod){a=sub(a,b,p);}

void smul(int &a,int b,int p=mod){a=mul(a,b,p);}



int n;

struct side{

  int y,next;

}e[N*2+9];

int lin[N+9],cs;



void Ins(int x,int y){e[++cs].y=y;e[cs].next=lin[x];lin[x]=cs;}

void Ins2(int x,int y){Ins(x,y);Ins(y,x);}



void into(){

  scanf("%d",&n);

  for (int i=1;i<n;++i){

	int x,y;

	scanf("%d%d",&x,&y);

	Ins2(x,y);

  }

}



int g[N+9];



void Get_g(){

  g[0]=1;

  for (int i=2;i<=n;i+=2) g[i]=mul(g[i-2],i-1);

}



int siz[N+9],dp[N+9][N+9],tmp[N+9];



void Dfs_dp(int k,int fa){

  dp[k][1]=1;

  siz[k]=1;

  for (int i=lin[k];i;i=e[i].next)

	if (e[i].y^fa){

	  int y=e[i].y;

	  Dfs_dp(y,k);

	  for (int i=0;i<=siz[k];++i)

		for (int j=0;j<=siz[y];++j) sadd(tmp[i+j],mul(dp[k][i],dp[y][j]));

	  siz[k]+=siz[e[i].y];

	  for (int i=0;i<=siz[k];++i) dp[k][i]=tmp[i],tmp[i]=0;

	}

  for (int i=2;i<=siz[k];i+=2) ssub(dp[k][0],mul(dp[k][i],g[i]));

}



void work(){

  Get_g();

  Dfs_dp(1,0);

}



void outo(){

  printf("%d\n",sub(0,dp[1][0]));

}



int main(){

  into();

  work();

  outo();

  return 0;

}
// Slower C++ solution:
// ===================================

//   author: M_sea

//   website: http://m-sea-blog.com/

// ===================================

#include <algorithm>

#include <iostream>

#include <cstdlib>

#include <cstring>

#include <cstdio>

#include <cmath>

#define re register

using namespace std;



inline int read() {

    int X=0,w=1; char c=getchar();

    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }

    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();

    return X*w;

}



const int N=5000+10;

const int mod=1e9+7;



struct edge { int v,nxt; } e[N<<1];

int head[N];



inline void addEdge(int u,int v) {

    static int e_cnt=0;

    e[++e_cnt]=(edge){v,head[u]},head[u]=e_cnt;

}



int n,sz[N];

int f[N][N],g[N],tmp[N];



inline void dfs(int u,int fa) {

    sz[u]=f[u][1]=1;

    for (re int i=head[u];i;i=e[i].nxt) {

        int v=e[i].v; if (v==fa) continue;

        dfs(v,u);

        for (re int j=1;j<=sz[u]+sz[v];++j) tmp[j]=0;

        for (re int j=1;j<=sz[u];++j)

            for (re int k=0;k<=sz[v];++k)

                tmp[j+k]=(tmp[j+k]+1ll*f[u][j]*f[v][k])%mod;

        sz[u]+=sz[v];

        for (re int j=1;j<=sz[u];++j) f[u][j]=tmp[j];

    }

    for (re int i=2;i<=sz[u];i+=2)

        f[u][0]=(f[u][0]-1ll*f[u][i]*g[i]%mod+mod)%mod;

}



int main() {

    n=read();

    for (re int i=1;i<n;++i) {

        int u=read(),v=read();

        addEdge(u,v),addEdge(v,u);

    }

    g[0]=1;

    for (re int i=2;i<=n;i+=2) g[i]=1ll*g[i-2]*(i-1)%mod;

    dfs(1,0); printf("%d\n",mod-f[1][0]);

    return 0;

}


// Faster C++ solution for the same problem (measured speedup: 5.206965995888109x):
#include <cstdio>

#include <algorithm>

#include <vector>

#define file(x) freopen(#x".in", "r", stdin), freopen(#x".out", "w", stdout)



inline int read()

{

	int data = 0, w = 1; char ch = getchar();

	while (ch != '-' && (ch < '0' || ch > '9')) ch = getchar();

	if (ch == '-') w = -1, ch = getchar();

	while (ch >= '0' && ch <= '9') data = data * 10 + (ch ^ 48), ch = getchar();

	return data * w;

}



const int N(5010), Mod(1e9 + 7);

struct edge { int next, to; } e[N << 1];

int head[N], e_num, f[N][N], g[N], size[N], n;

inline void add_edge(int from, int to)

{

	e[++e_num] = (edge) {head[from], to};

	head[from] = e_num;

}



void dfs(int x, int fa)

{

	static int tmp[N];

	size[x] = 1; int *fx = f[x]; fx[1] = 1;

	for (int i = head[x]; i; i = e[i].next)

	{

		int to = e[i].to; if (to == fa) continue;

		dfs(to, x);

		for (int j = 0; j <= size[x]; j++)

			for (int k = 0; k <= size[to]; k++)

				tmp[j + k] = (tmp[j + k] + 1ll * fx[j] * f[to][k]) % Mod;

		size[x] += size[to], std::copy(tmp + 1, tmp + size[x] + 1, fx + 1);

		std::fill(tmp + 1, tmp + size[x] + 1, 0);

	}

	fx[0] = 0;

	for (int i = 1; i <= size[x]; i++)

		fx[0] = (fx[0] - 1ll * fx[i] * g[i] % Mod + Mod) % Mod;

}



int main()

{

	n = read(), g[0] = 1;

	for (int i = 1, a, b; i < n; i++)

		a = read(), b = read(), add_edge(a, b), add_edge(b, a);

	for (int i = 2; i <= n; i += 2) g[i] = 1ll * g[i - 2] * (i - 1) % Mod;

	dfs(1, 1); printf("%d\n", Mod - f[1][0]);

	return 0;

}
// Slower C++ solution:
#include<stdio.h>

#include<stdlib.h>

#include<string.h>

#include<math.h>

#include<algorithm>

#include<queue>

#include<set>

#include<map>

#include<iostream>

using namespace std;

#define ll long long

#define REP(a,b,c) for(int a=b;a<=c;a++)

#define re register

#define file(a) freopen(a".in","r",stdin);freopen(a".out","w",stdout)

typedef pair<int,int> pii;

#define mp make_pair

inline int gi()

{

	int f=1,sum=0;char ch=getchar();

	while(ch>'9' || ch<'0'){if(ch=='-')f=-1;ch=getchar();}

	while(ch>='0' && ch<='9'){sum=(sum<<3)+(sum<<1)+ch-'0';ch=getchar();}

	return f*sum;

}

const int N=110;

int n,x,D,p[N],v[N],id[N];

ll m[N],f[N*N*N];

void upt(ll m,int val){for(int i=n*n*n;i>=val;i--)f[i]=min(f[i],f[i-val]+m);}

bool cmp(int x,int y){return 1ll*m[y]*v[x]>1ll*m[x]*v[y];}

int main()

{

	n=gi();x=gi();D=gi();m[1]=gi();

	for(int i=2;i<=n;i++){m[i]=gi();p[i]=gi();}

	for(int i=1;i<=n;i++)v[i]=1,id[i]=i;

	for(int i=n;i>1;i--)m[p[i]]+=m[i],v[p[i]]+=v[i];

	memset(f,63,sizeof(f));f[0]=0;//package

	for(int i=1;i<=n;i++)

	{

		int lim=1,ret=(i==1)?n:min(n,D);

		while(ret>=lim)

		{

			ret-=lim;upt(1ll*m[i]*lim,1ll*lim*v[i]);lim<<=1;

		}

		upt(1ll*m[i]*ret,1ll*ret*v[i]);

	}

	int ans=0;sort(id+1,id+n+1,cmp);

	for(int i=0;i<=n*n*n;i++)

		if(f[i]<=x)

		{

			int res=x-f[i],sum=i;

			for(int j=1;j<=n;j++)

			{

				int del=(id[j]==1)?res/m[1]:min(max(0ll,(ll)D-n),res/m[id[j]]);

				sum+=v[id[j]]*del;

				res-=del*m[id[j]];

			}

			ans=max(ans,sum);

		}

	printf("%d\n",ans);

	return 0;

}


// Faster C++ solution for the same problem (measured speedup: 5.20885778415894x):
#include<bits/stdc++.h>

#define ll long long

using namespace std;

int n,x,d,mx,k;

int siz[55],fa[55],a[55];

ll ans,c[55],f[55*55*55];

int main(){

	cin>>n>>x>>d>>c[1]; mx=n*n*n,k=min(n,d); memset(f,0x3f,sizeof(f)); f[0]=0;

	for(int i=2;i<=n;++i) cin>>c[i]>>fa[i];

	for(int i=n;i>=1;--i) siz[i]++,siz[fa[i]]+=siz[i],c[fa[i]]+=c[i];

	for(int i=1;i<=n;++i) for(int j=1;j<=k;++j) for(int s=mx;s>=siz[i];--s) f[s]=min(f[s],f[s-siz[i]]+c[i]);

	for(int i=1;i<=n;++i) a[i]=i;

	sort(a+1,a+n+1,[](int x,int y){return c[x]*siz[y]<c[y]*siz[x];});

	for(int i=0;i<=mx;++i) if(f[i]<=x){

		ll tmp=i,las=x-f[i];

		for(int j=1;j<=n&&a[j]>1;++j){

			ll now=min(d-k+0ll,las/c[a[j]]);

			las-=c[a[j]]*now,tmp+=now*siz[a[j]]; 

		}

		tmp+=las/c[1]*siz[1];

		ans=max(ans,tmp);

	}

	cout<<ans<<endl;

	return 0;

}
// Slower C++ solution:
#include <bits/stdc++.h>



using namespace std;



#define pb push_back

#define mem(a) memset(a,0,sizeof(a))



typedef long long ll;

typedef pair<int,int> pii;



const int mn=55;



int n;

ll m,D;

int a[mn];

vector<int> g[mn];

struct item{

	ll v,w,num;//value weight

	bool operator < (const item &e) const{

		return v*e.w>e.v*w;

	}

}p[mn];

void dfs(int v,int x){

	p[x].w+=a[v];

	p[x].v++;

	for(int &i:g[v]){

		dfs(i,x);

	}

}



ll d[mn*mn*mn];



inline ll greedy(ll m){

	ll ans=0;

	for (int i = 1; i <= n; i++) {

		ll u = min(m / p[i].w,p[i].num);

		m -= u * p[i].w, ans += p[i].v * u;

	}

	return ans;

}



int main() {

	ios::sync_with_stdio(0);

	cin >> n >> m >> D;

	cin >> a[1];

	for (int i = 2; i <= n; i++) {

		int u;

		cin >> a[i] >> u;

		g[u].pb(i);

		p[i].num = max(D - 50,0ll);

	}

	p[1].num = 1e9;

	for (int i = 1; i <= n; i++) dfs(i, i);

	sort(p + 1, p + n + 1);

	int maxpos = 0;

	fill_n(d, mn*mn*mn, 1ll << 58);

	d[0] = 0;

	for (int i = 1; i <= n; i++) {

		for (int k = 1; k <= min(50ll, D); k++) {

			maxpos += p[i].v;

			for (int j = maxpos; j >= p[i].v; j--) {

				d[j] = min(d[j], d[j - p[i].v] + p[i].w);

			}

		}

	}

	ll ans=0;

	for (int i = 0; i <= maxpos; i++) {

		if (d[i] <= m) ans=max(ans,greedy(m-d[i])+i);

	}

	cout << ans;

	return 0;

}

// Faster C++ solution for the same problem (measured speedup: 0.7702769713481287x):
#include<cstdio>

#include<cstring>

#define retrun return

#define cpnst const

int N,X,D;

typedef long long ll;

ll V[111111],W[111111],f[111111];

ll dp[133333];

cpnst int lim=131072;

void ins(ll v,ll w)

{

	register int i;

	for(i=lim;i>=w;i--)

		if(dp[i]>dp[i-w]+v)dp[i]=dp[i-w]+v;

}

struct pii

{ll v,w,s;}P[111];

bool operator<(cpnst pii x,cpnst pii y)

{return x.w*y.v>x.v*y.w;}

ll greedy(ll VAG)

{

	register int i;

	ll ret=0;

	for(i=1;i<=N;i++)

	{

		ll K=VAG/P[i].v;

		if(K>P[i].s)K=P[i].s;

		ret+=P[i].w*K,VAG-=P[i].v*K;

	}return ret;

}

void trial(ll v,ll w,int d)

{

	register int i;

	for(i=1;i<=d;d-=i,i<<=1)ins(v*i,w*i);

	if(d)ins(v*d,w*d);

}

#include<algorithm>

int main()

{

	register int i;

	scanf("%d%d%d",&N,&X,&D);

	int DL=D;

	if(N<DL)DL=N;

	scanf("%lld",V+1),W[1]=1;

	for(i=2;i<=N;i++)

		scanf("%lld%lld",V+i,f+i),W[i]=1;

	for(i=N;i>1;i--)

		V[f[i]]+=V[i],W[f[i]]+=W[i];

	for(i=1;i<=N;i++)

		P[i]=(pii){V[i],W[i],D-DL+X*(i==1)};

	std::sort(P+1,P+N+1);

	for(i=1;i<=lim;i++)dp[i]=2e9;

	for(i=1;i<=N;i++)trial(V[i],W[i],DL);

	ll ans=0;

	for(i=0;i<=lim;i++)

	{

		if(dp[i]>X)continue;

		ll T=greedy(X-dp[i])+i;

		if(T>ans)ans=T;

	}printf("%lld\n",ans);

}

/*

Please don't let me down.

*/
// Slower C++ solution:
#include<bits/stdc++.h>

#define ll long long

#define int ll

using namespace std;

ll c[55],f[250050],sz[55],fa[55];

struct node{

	ll cost,value,count;

	node(ll cost=0,ll value=0,ll count=0){this->cost=cost,this->value=value,this->count=count;}

	inline friend bool operator < (const node a,const node b){return a.cost*b.value<b.cost*a.value;}

}cs[555];

signed main(){

	ll n,x,d,ans=0;cin>>n>>x>>d;cin>>c[1];sz[1]=1;

	for(int i=2;i<=n;++i) cin>>c[i]>>fa[i],sz[i]=1;

	for(int i=n;i;--i) c[fa[i]]+=c[i],sz[fa[i]]+=sz[i];memset(f,0x3f,sizeof f);f[0]=0;

	for(int i=1;i<=n;++i){

		int T=min(n,d);if(i==1) T=n;

		for(int bit=1;bit<=T;T-=bit,bit<<=1) for(int j=n*n*n;j>=bit*sz[i];--j) f[j]=min(f[j],f[j-bit*sz[i]]+bit*c[i]);//bit>>=1;

		for(int j=n*n*n;j>=T*sz[i];--j) f[j]=min(f[j],f[j-T*sz[i]]+T*c[i]);

		if(i==1) cs[i]=node(c[i],sz[i],1e9);

		else cs[i]=node(c[i],sz[i],max(0ll,d-n));

	}

	sort(cs+1,cs+n+1);

	for(int has=0;has<=n*n*n;++has)if(f[has]<=x){

		int las=x-f[has],res=has;

		for(int i=1;i<=n;++i){

			int now=min(cs[i].count,las/cs[i].cost);

			res+=now*cs[i].value;las-=now*cs[i].cost;

		}

		ans=max(ans,res);

	}

	cout<<ans<<endl;

	return 0;

}

// Faster C++ solution for the same problem (measured speedup: 1.2951497385651558x):
#include<bits/stdc++.h>

#define maxn 55

#define LL long long

using namespace std;

int n,m,d,V,lim,ans;

LL f[maxn*maxn*maxn];

struct node{

	int v,id; LL w;

	bool operator < (const node &p)const{return v*p.w>w*p.v;}

}a[maxn];

vector<int>G[maxn];

void dfs(int u){for(int v:G[u]) dfs(v),a[u].v+=a[v].v,a[u].w+=a[v].w;}

void ins(LL v,LL w){for(int i=V;i>=v;i--) f[i]=min(f[i],f[i-v]+w);}

int main()

{

	scanf("%d%d%d%d",&n,&m,&d,&a[1].w),a[1].v=a[1].id=1;

	for(int i=2,x;i<=n;i++) scanf("%d%d",&a[i].w,&x),a[i].v=1,G[x].push_back(i);

	dfs(1);

	memset(f,0x3f,sizeof f),f[0]=0;

	V = n*n*n, lim = min(n,d);

	for(int i=1;i<=n;i++){

		int x=lim;

		for(int j=1;j<=x;x-=j,j<<=1) ins(1ll*j*a[i].v,j*a[i].w);

		if(x) ins(1ll*x*a[i].v,x*a[i].w);

	}

	sort(a+1,a+1+n);

	while(a[n].id!=1) n--;

	for(int i=0;i<=V&&f[i]<=m;i++){

		int v=i,w=f[i];

		for(int j=1;j<n;j++){

			int k=min(1ll*d-lim,(m-w)/a[j].w);

			v+=k*a[j].v,w+=k*a[j].w;

		}

		int k=(m-w)/a[n].w;

		ans=max(ans,v+k*a[n].v);

	}

	printf("%d\n",ans);

}