class Solution:
    def maxProfit(self, n: int, p, f, h, b: int) -> int:
        def sol(u,curr,last):
 
            if dp[u][curr][last]!=float('-inf'):
                return dp[u][curr][last]
            # p=0
 
            t1=0
            t2=0
            for v in adj[u]:
                t1+=sol(v,curr,0)
                if last==0:
                    if curr+p[u]//2<=b:
                        t2+=sol(v,curr,1)+f[u]-p[u]//2
                else:
                    if curr+p[u]<=b:
                        t2+=sol(v,curr,1)+f[u]-p[u]
 
            dp[u][curr][last]=max(t1,t2)
            return max(t1,t2)
 
 
 
        def df1(u):
            vis[u]=True
            for v in adj[u]:
                if not vis[u]:
                    df1(v)
            topo.append(u)
 
        adj=[[]  for _ in range(n)]
        for u,v in h:
            adj[u-1].append(v-1)
 
        dp=[[[float('-inf') for _ in range(2)] for _ in range(b+1)] for _ in range(n)]
        topo=[]
        vis=[False for _ in range(n)]
        # for i in range(n):
        #     if not vis[i]:
        #         df1(i)
 
        # print(topo)
        # vis=[False for _ in range(n)]
        return sol(0,0,0)
 
 
 

Y2xhc3MgU29sdXRpb246CiAgICBkZWYgbWF4UHJvZml0KHNlbGYsIG46IGludCwgcCwgZiwgaCwgYjogaW50KSAtPiBpbnQ6CiAgICAgICAgZGVmIHNvbCh1LGN1cnIsbGFzdCk6CiAgICAgICAgICAgIAogICAgICAgICAgICBpZiBkcFt1XVtjdXJyXVtsYXN0XSE9ZmxvYXQoJy1pbmYnKToKICAgICAgICAgICAgICAgIHJldHVybiBkcFt1XVtjdXJyXVtsYXN0XQogICAgICAgICAgICAjIHA9MAogICAgICAgICAgIAogICAgICAgICAgICB0MT0wCiAgICAgICAgICAgIHQyPTAKICAgICAgICAgICAgZm9yIHYgaW4gYWRqW3VdOgogICAgICAgICAgICAgICAgdDErPXNvbCh2LGN1cnIsMCkKICAgICAgICAgICAgICAgIGlmIGxhc3Q9PTA6CiAgICAgICAgICAgICAgICAgICAgaWYgY3VycitwW3VdLy8yPD1iOgogICAgICAgICAgICAgICAgICAgICAgICB0Mis9c29sKHYsY3VyciwxKStmW3VdLXBbdV0vLzIKICAgICAgICAgICAgICAgIGVsc2U6CiAgICAgICAgICAgICAgICAgICAgaWYgY3VycitwW3VdPD1iOgogICAgICAgICAgICAgICAgICAgICAgICB0Mis9c29sKHYsY3VyciwxKStmW3VdLXBbdV0KICAgICAgICAgICAgCiAgICAgICAgICAgIGRwW3VdW2N1cnJdW2xhc3RdPW1heCh0MSx0MikKICAgICAgICAgICAgcmV0dXJuIG1heCh0MSx0MikKICAgICAgICAgICAgCiAgICAgICAgICAgIAoKICAgICAgICBkZWYgZGYxKHUpOgogICAgICAgICAgICB2aXNbdV09VHJ1ZQogICAgICAgICAgICBmb3IgdiBpbiBhZGpbdV06CiAgICAgICAgICAgICAgICBpZiBub3QgdmlzW3VdOgogICAgICAgICAgICAgICAgICAgIGRmMSh2KQogICAgICAgICAgICB0b3BvLmFwcGVuZCh1KQoKICAgICAgICBhZGo9W1tdICBmb3IgXyBpbiByYW5nZShuKV0KICAgICAgICBmb3IgdSx2IGluIGg6CiAgICAgICAgICAgIGFkalt1LTFdLmFwcGVuZCh2LTEpCiAgICAgICAgCiAgICAgICAgZHA9W1tbZmxvYXQoJy1pbmYnKSBmb3IgXyBpbiByYW5nZSgyKV0gZm9yIF8gaW4gcmFuZ2UoYisxKV0gZm9yIF8gaW4gcmFuZ2UobildCiAgICAgICAgdG9wbz1bXQogICAgICAgIHZpcz1bRmFsc2UgZm9yIF8gaW4gcmFuZ2UobildCiAgICAgICAgIyBmb3IgaSBpbiByYW5nZShuKToKICAgICAgICAjICAgICBpZiBub3QgdmlzW2ldOgogICAgICAgICMgICAgICAgICBkZjEoaSkKICAgICAgICAKICAgICAgICAjIHByaW50KHRvcG8pCiAgICAgICAgIyB2aXM9W0ZhbHNlIGZvciBfIGluIHJhbmdlKG4pXQogICAgICAgIHJldHVybiBzb2woMCwwLDApCgoK