מדינת 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$.