Cerculete

Cerință

Gigel a descoperit cuvântul permutări și dintr-o dată a devenit foarte pasionat de ce reprezinta ele.
O permutare este o schimbare a ordinii elementelor unei mulțimi.
Exemplu: O permutare de ordin $5$ validă este $[1,5,2,3,4]$ în timp ce $[1,2,3,3,4]$ sau $[1,2,4,7,3]$ nu sunt valide. Ordinul permutari reprezintă numărul de elemente din șir.
Gigel jucându-se cu permutări la întâmplare a descoperit că ele formează cicluri. De exemplu luăm permutarea de ordin $7$ $[4,3,2,5,7,6,1]$.
Această permutare are următoarele cicluri:

• $1 \rightarrow 4 \rightarrow 5 \rightarrow 7 \rightarrow 1$;
• $2 \rightarrow 3 \rightarrow 2$.

Mai precis pornești de la o poziție $i$ a permutării și sari la valoare $p_i$ până când se revine la poziția inițială.

Un ciclu valid este și un ciclu cu un singur element $[1,2,3,4,5]$ are $5$ cicluri cu un singur element.

Gigel plictisindu-se doar de permutări a mai asociat și un cost fiecărui element printr-un alt vector $val$ tot de lungime $n$. Astfel oricare element de la $1$ la $n$ are costul respectiv $v_i$.

Deoarce Gigel nu se prea descurcă la informatică îți cere ție sa afli sa afli subsecvența de sumă maximă din toate ciclurile.

(Considerăm și o subsecvență vidă ca fiind una validă, adică putem să nu luam nici un element din ciclu, astfel suma devine $0$).

Date de intrare

Citești din fișier un număr $N$, și $2$ vectori.

Primul vector reprezinta permutarea inițială, în timp ce cel de al doilea reprezintă costul asociat fiecărui element de la $1$ la $N$.

Al doilea vector reprezintă costul asociat fiecarui element de la $1$ la $N$.

Date de ieșire

Se va afisa un singur număr reprezentând suma maxima din toate ciclurile posibile.

Restricții și precizări

• $N \leq 100 \ 000$,
• $1 \leq p_i \leq N$;
• $-5 \ 000 \leq v_i \leq 5 \ 000$.

  #	Punctaj	Restricții
  1	10	$p_i = i$
  2	20	$p_i = i + 1, i < N , p_N = 1$, $N \leq 2 \ 000$
  3	10	$p[i] \geq 0$
  4	20	$N \leq 2 \ 000$
  5	40	Fără restricții suplimentare

Exemplul 1

Cerculete.in

5
2 3 4 5 1 
-1 3 4 2 -6

Cerculete.out

9

Explicație

Se formeaza un singur ciclu de lungime $5$ care conține toate elementele, iar suma maxima posibilă este formată din elementele: $3$ $4$ $2$ valoarea finală fiind $9$.

Exemplul 2

Cerculete.in

10
3 5 4 7 9 8 10 6 2 1
5 -3 -5 3 -2 2 -9 3 -3 10

Cerculete.out

15

Explicație

Acest exemplu formeaza $3$ cicluri acestea fiind:

• $1 \rightarrow 3 \rightarrow 4 \rightarrow 7 \rightarrow 10$ de lungime $5$ cu subsecvența de sumă maximă $15$ (deoarece avem cicluri în alte cuvinte nu avem un inceput si un sfarsit determinat putem lua primul și ultimul element (ca și cum ne-am roti într-un cerc));
• Subsecvența de sumă maximă este: $10 \rightarrow 1$
• $2 \rightarrow 5 \rightarrow 9$ de lungime $3$ cu subsecvența de sumă maximă $0$ (alegem subsecvența vidă)
• $6 \rightarrow 8$ de lungime $2$ cu subsecvența de sumă maximă $5$