جزر 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,k$ مختلفة عن بعضها)، إذا أمكن إرسال برقية من الجزيرة $i$ إلى الجزيرة $j$، ومن الجزيرة $j$ إلى الجزيرة $k$، فيمكن إرسال برقية من الجزيرة $i$ إلى الجزيرة $k$. ولا يمكن إرسال البرقيات بأي وسيلة غير الاتصال اللاسلكي.

أنت وزير الاتصالات في جزر JOI، وتريد جعل إرسال برقية من أي جزيرة إلى أي جزيرة أخرى ممكنًا. لتحقيق ذلك، قد تحتاج إلى تغيير اتجاه أجهزة الاستقبال في بعض الجزر. وتساوي تكلفة تغيير اتجاه أجهزة الاستقبال في عدة جزر مجموع تكاليف تغيير اتجاه كل جهاز منها.

احسب أقل تكلفة لازمة لجعل إرسال برقية من أي جزيرة إلى أي جزيرة أخرى ممكنًا.

المهمة

اكتب برنامجًا يحسب أقل تكلفة لازمة لجعل إرسال برقية من أي جزيرة إلى أي جزيرة أخرى ممكنًا، عند إعطائه عدد الجزر في جزر JOI ومعلومات أجهزة الاستقبال في كل جزيرة.

الإدخال

اقرأ البيانات التالية من الإدخال القياسي.

• يحتوي السطر الأول على عدد صحيح $N$، وهو عدد الجزر في جزر JOI.
• يحتوي السطر $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

ملاحظة

لا حاجة إلى تغيير اتجاه جهاز الاستقبال في أي جزيرة.