Winter Driving

Στον Μεγάλο Λευκό Βορρά, υπάρχουν ~N~ πόλεις αριθμημένες από το ~1~ έως το ~N~. Εκεί ζουν ~A_i~ πολίτες της πόλης ~i~. Υπάρχουν ~N~ - ~1~ δρόμοι αριθμημένοι από το ~2~ έως το ~N~. Ο δρόμος ~j~ συνδέει την πόλη ~j~ και την πόλη ~P_j~ , όπου ~P_j~ ~\le~ ~j~. Υπάρχουν το πολύ ~36~ δρόμοι που συνδέονται με οποιαδήποτε πόλη.

Κατά τη διάρκεια του χειμώνα, όλοι οι δρόμοι θα μετατραπούν σε αυτοκινητόδρομους μονής κατεύθυνσης λόγω επικίνδυνων οδηγικών συνθηκών. Δηλαδή, ο δρόμος ~j~ θα γίνει αυτοκινητόδρομος που είναι είτε μονόδρομος από την πόλη ~j~ στην πόλη ~P_j~ είτε μονή διαδρομή από την πόλη ~P_j~ στην πόλη ~j~.

Κάθε πολίτης θέλει να στείλει μια γιορτινή κάρτα σε κάθε άλλο πολίτη. Ο πολίτης ~x~ μπορεί να στείλει μια κάρτα στον πολίτη ~y~ εάν είναι δυνατό να ταξιδέψει από την πόλη που ζει ο ~x~ στην πόλη που ζει ο ~y~ χρησιμοποιώντας μόνο αυτοκινητόδρομους.

Ποιος είναι ο μέγιστος αριθμός γιορτινών καρτών που μπορούν να σταλούν μετά τη μετατροπή όλων των δρόμων σε αυτοκινητόδρομους;

Είσοδος

Η πρώτη γραμμή περιέχει έναν ακέραιο ~N~ (~2~ ~\le~ ~N~ ~\le~ ~200\,000~).

Η δεύτερη γραμμή περιέχει ~N~ ακέραιους ~A_1~, ..., ~A_N~ (~1~ ~\le~ ~A_i~ ~\le~ ~10\,000~).

Η τρίτη γραμμή περιέχει ~N~ - ~1~ ακέραιους ~P_2~, ..., ~P_N~ (~1~ ~\le~ ~P_j~ ~\le~ ~j~).

Έστω ότι ~D~ είναι ο μέγιστος αριθμός δρόμων που συνδέονται σε οποιαδήποτε πόλη. Είναι εγγυημένο ότι ~D~ ~\le~ ~36~.

Βαθμολογία

Για ~5~ από τους ~25~ διαθέσιμους βαθμούς, ~N~ ~\le~ ~10~.

Για επιπλέον ~5~ από τους ~25~ διαθέσιμους βαθμούς, ~N~ ~\le~ ~1\,000~ και ~D~ ~\le~ ~10~.

Για επιπλέον ~5~ από τους ~25~ διαθέσιμους βαθμούς, ~D~ ~\le~ ~18~.

Για επιπλέον ~5~ από τους ~25~ διαθέσιμους βαθμούς, θα υπάρχουν ~37~ πόλεις, όπου μία πόλη συνδέεται με ~36~ άλλες πόλεις και αυτές οι άλλες ~36~ πόλεις συνδέονται μόνο με αυτή την μία πόλη.

Έξοδος

Εκτυπώστε μία γραμμή με έναν ακέραιο, το μέγιστο αριθμό καρτών που μπορούν να σταλούν μετά τη μετατροπή όλων των δρόμων σε αυτοκινητόδρομους.

Παράδειγμα

input

4
3 3 4 1
1 2 1

output

67

Επεξήγηση του παραδείγματος

Ένας πιθανός τρόπος να μετατρέψουμε τους δρόμους σε αυτοκινητόδρομους είναι να γίνει ο δρόμος ~2~ μονόδρομος από την πόλη ~2~ στην πόλη ~1~, ο δρόμος ~3~ να γίνει μονόδρομος από την πόλη ~3~ στην πόλη ~2~ και να γίνει ο δρόμος ~4~ μονόδρομος από την πόλη ~1~ στην πόλη ~4~.

Εξετάστε τις παρακάτω εικόνες, με τις πόλεις και τον αντίστοιχο πληθυσμό (σε παρένθεση) για τους αρχικούς δρόμους

και πως φαίνεται αφότου έχουν μετατραπεί όλοι οι δρόμοι σε αυτοκινητόδρομους:

Κάθε πολίτης στην πόλη ~3~ μπορεί να στείλει ~3~ γιορτινές κάρτες στους πολίτες της πόλης ~3~, ~3~ γιορτινές κάρτες στους πολίτες της πόλης ~2~, ~3~ γιορτινές κάρτες στους πολίτες της πόλης ~1~ και ~1~ γιορτινή κάρτα στον πολίτη της πόλης ~4~, για ένα σύνολο ~40~ γιορτινών καρτών που στάλθηκαν από την πόλη ~3~.

Παρομοίως,

• οι πολίτες της πόλης ~2~ στέλνουν ~6~ γιορτινές κάρτες ο καθένας, για ένα σύνολο ~18~ γιορτινών καρτών.

• οι πολίτες της πόλης ~1~ στέλνουν ~3~ γιορτινές κάρτες ο καθένας, για ένα σύνολο ~9~ γιορτινών καρτών.

• ο πολίτης της πόλης ~4~ δεν μπορεί να στείλει καμία γιορτινή κάρτα.

Ένα σύνολο από ~40~ + ~18~ + ~9~ = ~67~ κάρτες έχει σταλεί.