איי JOI הם מדינת איים קטנה באוקיינוס השקט. באיי JOI ישנם $N$ איים, הממוספרים מ-$1$ עד $N$.

באיי JOI התקשורת בין האיים נעשית בעיקר באמצעות רדיו. בכל אי יש משדר אחד ומקלט אחד. המשדר יכול לשדר גלי רדיו לכל הכיוונים, אך המקלט יכול לקלוט גלי רדיו רק מכיוון מסוים. לכן כל מקלט יכול לקלוט גלי רדיו רק מאי מסוים אחד. עם זאת, באמצעות שינוי כיוון המקלט אפשר לשנות את האי שממנו הוא יכול לקלוט גלי רדיו.

כעת, המקלט באי $i$ ($1\le i\le N$) יכול לקלוט גלי רדיו מהאי $A_i$ ($A_i\ne i$). העלות של שינוי כיוון המקלט באי $i$ היא $C_i$, ללא תלות בכיוון החדש שנבחר.

באיי JOI מופעל שירות מברקים כשירות ציבורי. אם המקלט באי $j$ ($1\le j\le N$, $j\ne i$) יכול לקלוט גלי רדיו מהאי $i$ ($1\le i\le N$), אפשר לשלוח מברק מהאי $i$ לאי $j$ בתקשורת רדיו. אפשר גם לשלוח מברק דרך כמה איים. כלומר, עבור האיים $i$, $j$, $k$ ($1\le i,j,k\le N$, והם שונים זה מזה), אם אפשר לשלוח מברק מהאי $i$ לאי $j$ ומהאי $j$ לאי $k$, אפשר לשלוח מברק מהאי $i$ לאי $k$. אי אפשר לשלוח מברקים בשום דרך מלבד תקשורת רדיו.

בתפקידכם כשר התקשורת של איי JOI, אתם רוצים שיהיה אפשר לשלוח מברק מכל אי לכל אי. לשם כך ייתכן שיהיה צורך לשנות את כיוון המקלטים בכמה איים. העלות של שינוי כיוון המקלטים בכמה איים היא סכום העלויות של שינוי כיוונו של כל אחד מהמקלטים הללו.

חשבו את העלות המינימלית הדרושה כדי שיהיה אפשר לשלוח מברק מכל אי לכל אי.

המשימה

בהינתן מספר האיים באיי JOI ומידע על המקלט בכל אי, כתבו תוכנית המחשבת את העלות המינימלית הדרושה כדי שיהיה אפשר לשלוח מברק מכל אי לכל אי.

קלט

קראו את הנתונים הבאים מהקלט הסטנדרטי.

• השורה הראשונה מכילה מספר שלם $N$. הוא מציין שבאיי JOI ישנם $N$ איים.
• השורה ה-$i$ ($1\le i\le N$) מבין $N$ השורות הבאות מכילה את המספרים השלמים $A_i$, $C_i$ המופרדים ברווח. הם מציינים שהמקלט באי $i$ יכול כעת לקלוט גלי רדיו מהאי $A_i$, ושעלות שינוי כיוונו היא $C_i$.

פלט

הדפיסו בשורה אחת לפלט הסטנדרטי את העלות המינימלית הדרושה כדי שיהיה אפשר לשלוח מברק מכל אי לכל אי.

מגבלות

כל נתוני הקלט מקיימים את התנאים הבאים.

• $2\le N\le 100\,000$.
• $1\le A_i\le N$ ($1\le i\le N$).
• $A_i\ne i$ ($1\le i\le N$).
• $1\le C_i\le 1\,000\,000\,000$ ($1\le i\le N$).

תתי־משימות

תת־משימה 1 [10 נקודות]

• מתקיים $N\le 10$.

תת־משימה 2 [30 נקודות]

• מתקיים $N\le 15$.

תת־משימה 3 [30 נקודות]

• מתקיים $N\le 3\,000$.

תת־משימה 4 [30 נקודות]

אין מגבלות נוספות.

דוגמאות

קלט 1

4
2 2
1 4
1 3
3 1

פלט 1

4

הסבר

משנים את כיוון המקלט באי $2$ כך שיוכל לקלוט גלי רדיו מהאי $4$. אז אפשר לשלוח מברק מכל אי לכל אי, והעלות היא $4$.

אין דרך לשנות את כיווני המקלטים בעלות נמוכה מ-$4$, ולכן מדפיסים $4$.

קלט 2

4
2 2
1 6
1 3
3 1

פלט 2

5

הסבר

תחילה משנים את כיוון המקלט באי $1$ כך שיוכל לקלוט גלי רדיו מהאי $4$. לאחר מכן משנים את כיוון המקלט באי $3$ כך שיוכל לקלוט גלי רדיו מהאי $2$. אז אפשר לשלוח מברק מכל אי לכל אי, והעלות היא $2+3=5$.

אין דרך לשנות את כיווני המקלטים בעלות נמוכה מ-$5$, ולכן מדפיסים $5$.

קלט 3

4
2 2
1 3
4 2
3 3

פלט 3

4

הסבר

די לשנות את כיוון המקלטים באיים $1$ ו-$3$.

קלט 4

3
2 1
3 1
1 1

פלט 4

0

הסבר

אין צורך לשנות את כיוון המקלט באף אי.