Buggy python submission (verdict: Time Limit Exceeded):
import sys, math

def calcweight_bellman_ford(N_vertices, edges, times, cost3, inf):
    is_confirmed = [False] * N_vertices

    distances = [0] * N_vertices
    distances[-1] = inf
    flag_updated = True
    """
    edges: [start, dest, cost] -> [cost, start, end]
    """
    moved = [0] * N_vertices
    for time in range(times):
        for edge in edges:
            left = edge[1]
            dest = edge[2]
            cost = edge[0]
            if(distances[left] == inf or moved[left] >= times):
                continue

            if(distances[dest] > distances[left] + cost ):
                distances[dest] = distances[left] + cost
                moved[dest] = moved[left]+1

    if(moved[-1]==1):
        distances[-1] = cost3 * (-1)

    return distances[-1]


if(__name__ == "__main__"):
    """
    N = int( input().strip() )
    Length = list( map(int, input().strip().split() ) )

    edges = [ [] for _ in range(N+2) ]
    for i in range(N):
        edges[0].append([0, i]) #[cost, edge]
    for i in range(1, N+1):
        edges[i].append([0, N+1])
    for i in range(N):
        edges[i].append([ CList[i]*(-1), PList[i] ])
    """
    N, K= map(int, input().strip().split() )
    PList = list( map(int, input().strip().split() ) )
    CList = list( map(int, input().strip().split() ) )
    inf = 10**6

    """
    N_vertices = 2+N
    """
    N_vertices = 1+N

    edges3 = []
    costs = []
    for i in range(N):
        edges3.append([ CList[i]*(-1), i, PList[i]-1 ])
        costs.append(CList[i])

    cost = max(costs)
    """
    for i in range(N):
        edges3.append([0, 0, i+1]) #[cost, start, end]
    """
    for i in range(N):
        edges3.append([0, i, N])


    """
    weight = -inf
    for i in range(1, N+1):
        weight2 =(-1) * calcweight_bellman_ford(N_vertices, edges3, K+1, cost, inf)
        if(weight2 > weight):
            weight = weight2
    """
    weight =(-1) * calcweight_bellman_ford(N_vertices, edges3, K+1, cost, inf)
    #weight= calcweight_bellman_ford(N_vertices, 0, edges3, K+2, cost, inf)


    print( weight)


Fixed submission:
import sys, math

def calcweight_tree(N_vertices, edges, times, inf):

    """
    edges: [start, dest, cost] -> [cost, start, end]
    """

    distance = 0

    passed = [False] * N_vertices

    travel_max = -inf
    for i in range(N_vertices):
        if(passed[i] == False):
            distance = 0
            left = i
            cost_sum = 0
            costs = []
            min_distance = inf
            while(True):
                dest = edges[left][1]
                cost = edges[dest][0]
                if(passed[dest]==False):
                    #passed[left] = True
                    passed[dest] = True
                    cost_sum += cost
                    costs.append(cost_sum)
                    left = dest
                    if(min_distance > cost):
                        min_distance = cost
                else:
                    period = len(costs)
                    increase_period = cost_sum
                    break
            # 2 period項準備
            remainder = times%period
            cost_minus = [0]
            for j in range(period-1):
                cost_minus.append(costs[j])
            if(increase_period <= 0):
                """
                for j in range(period):
                    costs.append(costs[j]+increase_period)
                maxindex = 0
                maxindex_start = 0
                maxvalue = -inf

                if(remainder==0):
                    remainder += period

                for st in range(period):
                    maxvalue_candidate = max(costs[st:st+period])
                    if(maxvalue_candidate - cost_minus[st] > maxvalue):
                        maxvalue = maxvalue_candidate - cost_minus[st]
                        maxindex = costs[st:st+period].index(maxvalue_candidate) + st
                        maxindex_start = st
                """
                costs_last = []
                # a_0は0なので。そしてこれは最大値を考えるときには数えないので
                remainder2 = remainder % period

                #print("x", costs, increase_period, remainder2)
                """
                for j in range(remainder2, period):
                    costs_last.append(costs[j])
                for j in range(0, remainder2):
                    costs_last.append(costs[j]+increase_period)
                for j in range(period):
                    costs_last.append(costs_last[j]+increase_period)
                """
                for j in range(period):
                    costs_last.append(costs[j])
                for j in range(period):
                    costs_last.append(costs_last[j]+increase_period)
                maxvalue = -inf
                #print(costs_last, cost_minus)
                for j in range(period):
                    maxvalue_candidate = max(costs_last[j:j+period])
                    if(maxvalue_candidate-cost_minus[j] > maxvalue):
                        maxvalue = maxvalue_candidate-cost_minus[j]

                travel_max = max(maxvalue, travel_max)
            else:
                costs_last = []
                # a_0は0なので。そしてこれは最大値を考えるときには数えないので
                remainder2 = remainder % period
                times_period = times//period-1
                add_n = times_period * increase_period
                #print(costs, increase_period, remainder2, times_period, add_n)
                for j in range(remainder2, period):
                    costs_last.append(costs[j]+add_n)
                for j in range(0, remainder2):
                    costs_last.append(costs[j]+add_n+increase_period)
                for j in range(period):
                    costs_last.append(costs_last[j]+increase_period)
                maxvalue = -inf
                #print(costs_last, cost_minus)
                for j in range(period):
                    maxvalue_candidate = max(costs_last[j:j+period])
                    if(maxvalue_candidate-cost_minus[j] > maxvalue):
                        maxvalue = maxvalue_candidate-cost_minus[j]
                travel_max = max(maxvalue, travel_max)






    return travel_max







if(__name__ == "__main__"):
    """
    N = int( input().strip() )
    Length = list( map(int, input().strip().split() ) )

    edges = [ [] for _ in range(N+2) ]
    for i in range(N):
        edges[0].append([0, i]) #[cost, edge]
    for i in range(1, N+1):
        edges[i].append([0, N+1])
    for i in range(N):
        edges[i].append([ CList[i]*(-1), PList[i] ])
    """
    N, K= map(int, input().strip().split() )
    PList = list( map(int, input().strip().split() ) )
    CList = list( map(int, input().strip().split() ) )
    inf = 10**10


    N_vertices = N

    edges3 = []
    costs = []
    for i in range(N):
        edges3.append([ CList[i], PList[i]-1 ])

    weight = calcweight_tree(N_vertices, edges3, K, inf)

    #weight= calcweight_bellman_ford(N_vertices, 0, edges3, K+2, cost, inf)


    print( weight)

Buggy python submission (verdict: Time Limit Exceeded):
import sys, math, bisect

def calcweight_bellman_ford(N_vertices, start, edges, times, costs, inf):
    is_confirmed = [False] * N_vertices

    distances = [inf] * N_vertices
    distances[start] = 0
    flag_updated = True
    """
    edges: [start, dest, cost] -> [cost, start, end]
    """
    moved = [0] * N_vertices
    for time in range(times+2):
        for edge in edges:
            left = edge[1]
            dest = edge[2]
            cost = edge[0]
            if(distances[left] == inf or moved[left] >= times+2):
                continue

            if(distances[dest] > distances[left] + cost ):
                distances[dest] = distances[left] + cost
                moved[dest] = moved[left]+1

    if(moved[-1]==2):
        distances[-1] = costs[-1] * (-1)

    return distances


if(__name__ == "__main__"):
    """
    N = int( input().strip() )
    Length = list( map(int, input().strip().split() ) )

    edges = [ [] for _ in range(N+2) ]
    for i in range(N):
        edges[0].append([0, i]) #[cost, edge]
    for i in range(1, N+1):
        edges[i].append([0, N+1])
    for i in range(N):
        edges[i].append([ CList[i]*(-1), PList[i] ])
    """
    N, K= map(int, input().strip().split() )
    PList = list( map(int, input().strip().split() ) )
    CList = list( map(int, input().strip().split() ) )
    inf = 10**6

    N_vertices = 2+N

    edges3 = []
    costs = []
    for i in range(N):
        edges3.append([ CList[i]*(-1), i+1, PList[i] ])
        costs.append(CList[i])
    costs.sort()
    for i in range(N):
        edges3.append([0, 0, i+1]) #[cost, start, end]
    for i in range(1, N+1):
        edges3.append([0, i, N+1])



    weights =calcweight_bellman_ford(N_vertices, 0, edges3, K, costs, inf)


    print( (-1) * weights[-1])


Fixed submission:
import sys, math

def calcweight_tree(N_vertices, edges, times, inf):

    """
    edges: [start, dest, cost] -> [cost, start, end]
    """

    distance = 0

    passed = [False] * N_vertices

    travel_max = -inf
    for i in range(N_vertices):
        if(passed[i] == False):
            distance = 0
            left = i
            cost_sum = 0
            costs = []
            min_distance = inf
            while(True):
                dest = edges[left][1]
                cost = edges[dest][0]
                if(passed[dest]==False):
                    #passed[left] = True
                    passed[dest] = True
                    cost_sum += cost
                    costs.append(cost_sum)
                    left = dest
                    if(min_distance > cost):
                        min_distance = cost
                else:
                    period = len(costs)
                    increase_period = cost_sum
                    break
            # 2 period項準備
            remainder = times%period
            cost_minus = [0]
            for j in range(period-1):
                cost_minus.append(costs[j])
            if(increase_period <= 0):
                """
                for j in range(period):
                    costs.append(costs[j]+increase_period)
                maxindex = 0
                maxindex_start = 0
                maxvalue = -inf

                if(remainder==0):
                    remainder += period

                for st in range(period):
                    maxvalue_candidate = max(costs[st:st+period])
                    if(maxvalue_candidate - cost_minus[st] > maxvalue):
                        maxvalue = maxvalue_candidate - cost_minus[st]
                        maxindex = costs[st:st+period].index(maxvalue_candidate) + st
                        maxindex_start = st
                """
                costs_last = []
                # a_0は0なので。そしてこれは最大値を考えるときには数えないので
                remainder2 = remainder % period

                #print("x", costs, increase_period, remainder2)
                """
                for j in range(remainder2, period):
                    costs_last.append(costs[j])
                for j in range(0, remainder2):
                    costs_last.append(costs[j]+increase_period)
                for j in range(period):
                    costs_last.append(costs_last[j]+increase_period)
                """
                for j in range(period):
                    costs_last.append(costs[j])
                for j in range(period):
                    costs_last.append(costs_last[j]+increase_period)
                maxvalue = -inf
                #print(costs_last, cost_minus)
                for j in range(period):
                    maxvalue_candidate = max(costs_last[j:j+period])
                    if(maxvalue_candidate-cost_minus[j] > maxvalue):
                        maxvalue = maxvalue_candidate-cost_minus[j]

                travel_max = max(maxvalue, travel_max)
            else:
                costs_last = []
                # a_0は0なので。そしてこれは最大値を考えるときには数えないので
                remainder2 = remainder % period
                times_period = times//period-1
                add_n = times_period * increase_period
                #print(costs, increase_period, remainder2, times_period, add_n)
                for j in range(remainder2, period):
                    costs_last.append(costs[j]+add_n)
                for j in range(0, remainder2):
                    costs_last.append(costs[j]+add_n+increase_period)
                for j in range(period):
                    costs_last.append(costs_last[j]+increase_period)
                maxvalue = -inf
                #print(costs_last, cost_minus)
                for j in range(period):
                    maxvalue_candidate = max(costs_last[j:j+period])
                    if(maxvalue_candidate-cost_minus[j] > maxvalue):
                        maxvalue = maxvalue_candidate-cost_minus[j]
                travel_max = max(maxvalue, travel_max)






    return travel_max







if(__name__ == "__main__"):
    """
    N = int( input().strip() )
    Length = list( map(int, input().strip().split() ) )

    edges = [ [] for _ in range(N+2) ]
    for i in range(N):
        edges[0].append([0, i]) #[cost, edge]
    for i in range(1, N+1):
        edges[i].append([0, N+1])
    for i in range(N):
        edges[i].append([ CList[i]*(-1), PList[i] ])
    """
    N, K= map(int, input().strip().split() )
    PList = list( map(int, input().strip().split() ) )
    CList = list( map(int, input().strip().split() ) )
    inf = 10**10


    N_vertices = N

    edges3 = []
    costs = []
    for i in range(N):
        edges3.append([ CList[i], PList[i]-1 ])

    weight = calcweight_tree(N_vertices, edges3, K, inf)

    #weight= calcweight_bellman_ford(N_vertices, 0, edges3, K+2, cost, inf)


    print( weight)