تتكون دولة IOI من $N$ من البلدات المرقمة من البلدة $1$ إلى البلدة $N$، وترتبط البلدات ببعضها بواسطة طرق. يوجد في دولة IOI عدد $K$ من الطرق، وكل طريق يربط بين بلدتين ($2$) مختلفتين. يمكن للسيارات التحرك بحرية في كلا الاتجاهين عبر الطرق، ولكن لا يمكن الانتقال من بلدة إلى أخرى عبر غير الطرق.

قرر JOI-kun، الذي يعيش في البلدة $1$ في دولة IOI، الذهاب إلى منزل جدته التي تعيش في البلدة $N$ بواسطة سيارات الأجرة. توجد في دولة IOI شركات سيارات أجرة عددها $N$ مرقمة من شركة سيارات الأجرة $1$ إلى شركة سيارات الأجرة $N$. لدى شركات سيارات الأجرة في دولة IOI القواعد الخاصة التالية:

• لا يمكن ركوب سيارة أجرة تابعة لشركة سيارات الأجرة $i$ إلا في البلدة $i$.
• أجرة سيارة الأجرة التابعة لشركة سيارات الأجرة $i$ هي $C_i$ بغض النظر عن المسافة المقطوعة.
• يمكن لسيارة الأجرة التابعة لشركة سيارات الأجرة $i$ أن تقطع بحد أقصى $R_i$ من الطرق المتتالية منذ ركوبها.

على سبيل المثال، عندما تكون $R_1 = 2$، فإنه عند ركوب سيارة أجرة تابعة لشركة سيارات الأجرة $1$ من البلدة $1$، يمكن قطع طريقين ($2$) بحد أقصى؛ ولذلك، لقطع $3$ طرق أو أكثر، يلزم تبديل سيارة الأجرة في إحدى البلدات في منتصف الطريق.

لا يستطيع JOI-kun ركوب سيارة أجرة أو النزول منها في أي مكان غير البلدات. كما لا يمكنه استخدام أي وسيلة نقل أخرى غير سيارات الأجرة. اكتب برنامجاً لإيجاد القيمة الصغرى لإجمالي الأجرة اللازمة لكي يصل JOI-kun إلى البلدة $N$.

الإدخال

يتكون الإدخال من $1 + N + K$ من الأسطر.

يحتوي السطر $1$ على عددين صحيحين $2$ مفصولين بفراغ وهما $N, K$ ($2 \le N \le 5000$, $N - 1 \le K \le 10000$). يشير هذا إلى أن دولة IOI تتكون من $N$ من البلدات وأن عدد الطرق في دولة IOI هو $K$.

يحتوي السطر $i$ ($1 \le i \le N$) من الأسطر الـ $N$ التالية على عددين صحيحين $2$ مفصولين بفراغ وهما $C_i, R_i$ ($1 \le C_i \le 10000$, $1 \le R_i \le N$). يشير هذا إلى أن أجرة سيارة الأجرة التابعة للشركة $i$ هي $C_i$، وأنه يمكنها قطع بحد أقصى $R_i$ من الطرق المتتالية منذ ركوبها.

يحتوي السطر $j$ ($1 \le j \le K$) من الأسطر الـ $K$ التالية على عددين صحيحين مختلفين $2$ مفصولين بفراغ وهما $A_j, B_j$ ($1 \le A_j < B_j \le N$). يشير هذا إلى وجود طريق بين البلدة $A_j$ والبلدة $B_j$. لا يتكرر نفس الزوج $(A_j, B_j)$ مرتين ($2$) أو أكثر.

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

الإخراج

اطبع في سطر $1$ عدداً صحيحاً يمثل القيمة الصغرى لإجمالي الأجرة اللازمة لكي يذهب JOI-kun من البلدة $1$ إلى البلدة $N$.

أمثلة

مثال الإدخال 1

6 6
400 2
200 1
600 3
1000 1
300 5
700 4
1 2
2 3
3 6
4 6
1 5
2 4

مثال الإخراج 1

700

ملاحظة

يتوافق المثال أعلاه مع الشكل التالي. تمثل الدوائر البلدات، وتمثل الخطوط الطرق.

في هذا المثال، لكي يصل JOI-kun إلى البلدة $6$ بأقل أجرة، يتبع الخطوات التالية:

• يركب سيارة أجرة من البلدة $1$ ويذهب إلى البلدة $5$. (الأجرة $400$)
• يركب سيارة أجرة من البلدة $5$ ويذهب إلى البلدة $6$. (الأجرة $300$)

بما أن إجمالي الأجرة عندما يسلك JOI-kun هذا المسار هو $400 + 300 = 700$، نطبع $700$.