Областная олимпиада по информатике 2017 г.

В стране T K − Robots есть $n$ городов. Для удобство пронумеруем их от 1 до n. Из каждого города выходит ровно одна односторонняя дорога. Из i - го города в город $p_i$. В начале в городе i находится $a_i$ роботов. Роботы очень любят путешествовать по стране. За один момент времени, робот находящиеся в городе i пойдет в город $p_i$. Найдите максимальное количество роботов, которые одновременно будут в одном городе.

Входные данные

В первой строке входных данных находится одно целое число $n$($2 ≤ n ≤ 10^5$) - количество городов.
Во второй строке находятся n целых числа $p_1, p_2, ..., p_n$ ($1 ≤ p_i ≤ n$) и $p_i \ne i$.
В третьей строке находятся n целых числа $a_1, a_2, ..., a_n$ ($0 ≤ a_i ≤ 10^9$), где $a_i$ - количество роботов в i-ом городе.

Выходные данные

Выведите одно целое число — максимальное возможное количество роботов, которые будут находиться в одном городе одновременно.

Примеры:

1. Вход:

3 
2 3 1 
5 4 8

Ответ:

8

2. Вход:

5 
5 3 4 2 1 
7 6 0 3 3

Ответ:

7

3. Вход:

7 
7 1 1 3 3 7 4 
3 1 4 0 2 0 2

Ответ:

5

4. Вход:

12
11 1 6 1 7 8 8 7 7 9 12 11
12 29 7 19 4 8 39 31 22 34 25 40

Ответ:

81

5. Вход:

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

Ответ:

12

Оценивание:

В 8% тестовых данных: $2 ≤ n ≤ 10^5$ , и $p_1, p_2, ..., p_n$ - является перестановкой чисел 1, 2, .., n.
В 20% тестовых данных: 2 ≤ n ≤ 2000.
В 20% тестовых данных: 2 ≤ n ≤ 105, а также выполняются следующие условия:

• a) p1 = 2, p2 = 1
• b) Из любого города можно добраться в город с номером 1. В остальных ограничения из условия.

В первой подзадаче могут находится только 1 и 2 тест из примеров. Во второй и четвертой подзадаче могут находится все тесты из примеров. В третьей подзадаче могут находится только 5 тест из примеров.