Takahashi will play a game using a piece on an array of squares numbered 1, 2, \cdots, N. Square i has an integer C_i written on it. Also, he is given a permutation of 1, 2, \cdots, N: P_1, P_2, \cdots, P_N.

Now, he will choose one square and place the piece on that square. Then, he will make the following move some number of times between 1 and K (inclusive):

* In one move, if the piece is now on Square i (1 \leq i \leq N), move it to Square P_i. Here, his score increases by C_{P_i}.



Help him by finding the maximum possible score at the end of the game. (The score is 0 at the beginning of the game.)

Constraints

* 2 \leq N \leq 5000
* 1 \leq K \leq 10^9
* 1 \leq P_i \leq N
* P_i \neq i
* P_1, P_2, \cdots, P_N are all different.
* -10^9 \leq C_i \leq 10^9
* All values in input are integers.

Input

Input is given from Standard Input in the following format:


N K
P_1 P_2 \cdots P_N
C_1 C_2 \cdots C_N


Output

Print the maximum possible score at the end of the game.

Examples

Input

5 2
2 4 5 1 3
3 4 -10 -8 8


Output

8


Input

2 3
2 1
10 -7


Output

13


Input

3 3
3 1 2
-1000 -2000 -3000


Output

-1000


Input

10 58
9 1 6 7 8 4 3 2 10 5
695279662 988782657 -119067776 382975538 -151885171 -177220596 -169777795 37619092 389386780 980092719


Output

29507023469

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Scanner;

public final class Main {

    public static class UnionFind {
        private final int[] parent;
        private final int[] size;
        private int count;

        public UnionFind(int n) {
            parent = new int[n];
            size = new int[n];
            count = n;
            for (int i = 0; i < n; i++) {
                parent[i] = i;
                size[i] = 1;
            }
        }

        public int find(int p) {
            // path compression
            while (p != parent[p]) {
                parent[p] = parent[parent[p]];
                p = parent[p];
            }
            return p;
        }

        public void union(int p, int q) {
            final int rootP = find(p);
            final int rootQ = find(q);
            if (rootP == rootQ) {
                return;
            }
            // union by size
            if (size[rootP] > size[rootQ]) {
                parent[rootQ] = rootP;
                size[rootP] += size[rootQ];
            } else {
                parent[rootP] = rootQ;
                size[rootQ] += size[rootP];
            }
            count--;
        }

        public int count() { return count; }

        public int[] size() { return size; }
    }

    public static void main(String[] args) {
        final Scanner in = new Scanner(new BufferedReader(new InputStreamReader(System.in)));
        final String[] line = in.nextLine().split(" ");
        final int n = Integer.parseInt(line[0]);
        final int k = Integer.parseInt(line[1]);
        final int[] p = new int[n];
        final int[] c = new int[n];
        for (int i = 0; i < n; i++) {
            p[i] = in.nextInt();
        }
        in.nextLine();
        for (int i = 0; i < n; i++) {
            c[i] = in.nextInt();
        }
        in.nextLine();
        final UnionFind uf = new UnionFind(n);
        for (int i = 0; i < n; i++) {
            uf.union(i, p[i] - 1);
        }
        final long[] res = { (long) -1e9 };
        for (int i = 0; i < n; i++) {
            final int currCycle = uf.size[uf.find(i)];
            final long mult = k / currCycle;
            final int r = k % currCycle;
            if (k < currCycle) {
                final long[] remainderCycle = calc(p, c, k, i);
                res[0] = Math.max(res[0], Math.max(remainderCycle[0], remainderCycle[1]));
            } else {
                final long[] fullCycle = calc(p, c, currCycle, i);
                res[0] = Math.max(res[0], Math.max(fullCycle[0], fullCycle[1]));
                res[0] = Math.max(res[0], mult * fullCycle[0]);
                res[0] = Math.max(res[0], (mult - 1) * fullCycle[0] + fullCycle[1]);
                if (r != 0) {
                    final long[] remainderCycle = calc(p, c, r, i);
                    res[0] = Math.max(res[0], mult * fullCycle[0] 
                                              + Math.max(remainderCycle[0], remainderCycle[1]));
                }
            }
        }
        System.out.println(res[0]);
    }

    private static long[] calc(int[] p, int[] c, int k, int startIdx) {
        long curr = 0;
        long bestStep = (long) -1e9;
        for (int i = 0; i < k; i++) {
            final int next = p[startIdx] - 1;
            curr += c[next];
            bestStep = Math.max(bestStep, curr);
            startIdx = next;
        }
        return new long[] { curr, bestStep };
    }
}
