题目描述

在到达鲁塞之前，Georgi 买了一张该市公共交通的地图。

地图上有 N 个路口，编号为 1 到 N。某些路口对之间恰好有一条双向直接街道相连（也就是说，这条街道中间没有其他路口），并且从任意一个路口都可以通过地图上的街道到达任意另一个路口。街道总数恰好也是 N 条。

地图中的街道描述方式如下：对于每个路口 i，给出恰好一条从路口 i 通向路口 p_i 的街道，其中 p_i 是这条街道另一端的路口编号（允许 i = p_i），这条街道的长度为 w_i。

现在 Georgi 已经到了鲁塞，他想进行一次尽可能长的散步，但要求他走的是某两个路口之间的最短路径。换句话说，他要找一对路口，使得这两个路口之间的最短路径长度尽可能大。

请你编写程序 transport，求出这条路径的长度。

输入格式

第一行输入一个正整数 N，表示路口数量。

第二行输入 N 个正整数 p_1, p_2, ..., p_N。

第三行输入 N 个正整数 w_1, w_2, ..., w_N。

输出格式

输出一行一个整数，表示所求路径的长度。

数据范围

• 1 ≤ N ≤ 10^6
• 1 ≤ p_i ≤ N
• 1 ≤ w_i ≤ 10^6

样例

输入

8
2 4 4 1 1 5 5 7
1 2 3 4 5 6 7 8

输出

26

说明

所求的最长最短路径位于顶点 3 和 8 之间，即：

3-4-2-1-5-7-8

其总长度为 26。

子任务与评分

只有当某个子任务中的所有测试点都通过时，才能获得该子任务的分数。