Областная олимпиада по информатике 2016-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, ..., pn$ ($1 ≤ pi ≤ n$) и $p_i ̸= i$.
В третьей строке находятся n целых числа $a1, a2, ..., an$ ($0 ≤ ai ≤ 10^9$), где $a_i$ - количество роботов в i-ом городе.

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

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

Примеры:

Вход:

3 
2 3 1 
5 4 8

Ответ:

8

Вход:

5 
5 3 4 2 1 
7 6 0 3 3

Ответ:

7

Вход:

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

Ответ:

5

Вход:

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

Вход:

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 тест из примеров.