题目背景

某公司内部有一个消息传达机制：总负责人首先将消息告诉他的直接下属，每个收到消息的人再告诉他的直接下属，直到所有人都收到消息。

每个人通知完所有直接下属所需的时间不同。公司想知道从总负责人发出消息开始，到所有人都收到消息至少需要多少分钟。

题目描述

公司有 $n$ 名员工，编号 $0 \sim n-1$。总负责人的编号为 $headID$。

给定两个长度为 $n$ 的数组：

• $manager[i]$：员工 $i$ 的直接上级（总负责人的上级为 $-1$）
• $informTime[i]$：员工 $i$ 通知完所有直接下属所需的分钟数

每名员工只有在收到消息后，才能开始通知自己的下属。求所有人都收到消息所需的最少时间。

输入格式

第一行两个整数 $n, headID$。

第二行 $n$ 个整数 $manager[0] \sim manager[n-1]$。

第三行 $n$ 个整数 $informTime[0] \sim informTime[n-1]$。

输出格式

输出一个整数，表示最少分钟数。

样例输入

7 6
1 2 3 4 5 6 -1
0 6 5 4 3 2 1

样例输出

21

样例解释

通知链：$6 \to 5 \to 4 \to 3 \to 2 \to 1 \to 0$（依次通知） 总耗时 $= 1+2+3+4+5+6 = 21$ 分钟。

数据范围

$1 \le n \le 10^5$，$0 \le headID < n$，$manager[headID] = -1$。 $informTime[i] \le 1000$。