Negara IOI terdiri dari $N$ kota mulai dari kota $1$ hingga kota $N$, dan antarkota dihubungkan oleh jalan. Di negara IOI terdapat $K$ jalan, dan setiap jalan menghubungkan $2$ kota yang berbeda. Mobil dapat bergerak bebas dua arah di jalan tersebut, tetapi kita tidak dapat pergi dari satu kota ke kota lain tanpa melalui jalan.

JOI-kun yang tinggal di kota $1$ di negara IOI memutuskan untuk pergi ke rumah neneknya yang tinggal di kota $N$ menggunakan taksi. Di negara IOI terdapat $N$ perusahaan taksi mulai dari perusahaan taksi $1$ hingga perusahaan taksi $N$. Perusahaan taksi di negara IOI memiliki aturan yang agak khusus sebagai berikut:

• Taksi dari perusahaan taksi $i$ hanya dapat dinaiki di kota $i$.
• Tarif taksi dari perusahaan taksi $i$ adalah $C_i$, tidak bergantung pada jarak yang ditempuh.
• Taksi dari perusahaan taksi $i$ hanya dapat melewati paling banyak $R_i$ jalan secara berturut-turut sejak dinaiki.

Sebagai contoh, jika $R_1 = 2$, ketika menaiki taksi dari perusahaan taksi $1$ di kota $1$, taksi tersebut hanya dapat melewati paling banyak $2$ jalan, sehingga untuk melewati $3$ jalan atau lebih, penumpang harus berganti taksi di kota perantara.

JOI-kun tidak dapat naik atau turun taksi di lokasi selain kota. Ia juga tidak dapat menggunakan alat transportasi selain taksi. Buatlah program untuk mencari nilai minimum dari total tarif yang diperlukan agar JOI-kun dapat mencapai kota $N$.

Input

Input terdiri dari $1 + N + K$ baris.

Baris ke-$1$ berisi $2$ bilangan bulat $N, K$ ($2 \le N \le 5000$, $N - 1 \le K \le 10000$) yang dipisahkan oleh spasi. Ini menyatakan bahwa negara IOI terdiri dari $N$ kota dan banyaknya jalan di negara IOI adalah $K$.

Baris ke-$i$ ($1 \le i \le N$) dari $N$ baris berikutnya berisi $2$ bilangan bulat $C_i, R_i$ ($1 \le C_i \le 10000$, $1 \le R_i \le N$) yang dipisahkan oleh spasi. Ini menyatakan bahwa tarif taksi dari perusahaan taksi $i$ adalah $C_i$, dan taksi tersebut hanya dapat melewati paling banyak $R_i$ jalan secara berturut-turut sejak dinaiki.

Baris ke-$j$ ($1 \le j \le K$) dari $K$ baris berikutnya berisi $2$ bilangan bulat berbeda $A_j, B_j$ ($1 \le A_j < B_j \le N$) yang dipisahkan oleh spasi. Ini menyatakan bahwa terdapat jalan antara kota $A_j$ dan kota $B_j$. Pasangan $(A_j, B_j)$ yang sama tidak akan tertulis $2$ kali atau lebih.

Pada data input yang diberikan, dijamin bahwa dari kota mana pun kita dapat pergi ke kota lainnya dengan berganti-ganti taksi.

Output

Keluarkan sebuah bilangan bulat yang menyatakan nilai minimum dari total tarif yang diperlukan JOI-kun untuk pergi dari kota $1$ ke kota $N$ dalam $1$ baris.

Contoh

Contoh Input 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

Contoh Output 1

700

Catatan

Contoh di atas sesuai dengan gambar berikut. Lingkaran menyatakan kota, sedangkan garis menyatakan jalan.

Pada contoh ini, agar JOI-kun mencapai kota $6$ dengan tarif minimum, ia melakukan hal berikut:

• Naik taksi dari kota $1$ menuju kota $5$. (Tarif $400$)
• Naik taksi dari kota $5$ menuju kota $6$. (Tarif $300$)

Karena total tarif ketika JOI-kun melewati rute tersebut adalah $400 + 300 = 700$, maka keluarkan $700$.