Đất nước IOI gồm $N$ thị trấn được đánh số từ thị trấn $1$ đến thị trấn $N$, và các thị trấn được nối với nhau bằng các con đường. Ở đất nước IOI có $K$ con đường, mỗi con đường nối $2$ thị trấn khác nhau. Xe cộ có thể di chuyển tự do theo cả hai chiều trên đường, nhưng không thể đi từ một thị trấn đến một thị trấn khác mà không đi qua đường.

JOI-kun, người sống ở thị trấn $1$ của đất nước IOI, quyết định đi taxi đến nhà bà ngoại sống ở thị trấn $N$. Ở đất nước IOI có $N$ hãng taxi được đánh số từ hãng taxi $1$ đến hãng taxi $N$. Các hãng taxi ở đất nước IOI có những quy tắc hơi đặc biệt như sau:

• Xe taxi của hãng taxi $i$ chỉ có thể đón khách tại thị trấn $i$.
• Giá cước của xe taxi thuộc hãng taxi $i$ luôn là $C_i$ bất kể quãng đường đã đi.
• Xe taxi của hãng taxi $i$ chỉ có thể đi qua liên tiếp tối đa $R_i$ con đường kể từ khi đón khách.

Ví dụ, khi $R_1 = 2$, nếu lên xe taxi của hãng taxi $1$ từ thị trấn $1$, xe chỉ có thể đi qua tối đa $2$ con đường, vì vậy để đi qua từ $3$ con đường trở lên thì cần phải đổi xe taxi ở một thị trấn trung gian.

JOI-kun không thể lên hoặc xuống taxi ở bất kỳ địa điểm nào ngoài các thị trấn. Cậu cũng không thể sử dụng bất kỳ phương tiện giao thông nào khác ngoài taxi. Hãy viết chương trình tìm giá trị nhỏ nhất của tổng chi phí cần thiết để JOI-kun đến được thị trấn $N$.

Dữ liệu vào

Dữ liệu vào gồm $1 + N + K$ dòng.

Dòng thứ $1$ chứa $2$ số nguyên $N, K$ ($2 \le N \le 5000$, $N - 1 \le K \le 10000$) cách nhau bởi dấu cách. Điều này cho biết đất nước IOI gồm $N$ thị trấn và số lượng con đường ở đất nước IOI là $K$.

Dòng thứ $i$ ($1 \le i \le N$) trong $N$ dòng tiếp theo chứa $2$ số nguyên $C_i, R_i$ ($1 \le C_i \le 10000$, $1 \le R_i \le N$) cách nhau bởi dấu cách. Điều này cho biết giá cước taxi của hãng taxi $i$ là $C_i$, và xe chỉ có thể đi qua liên tiếp tối đa $R_i$ con đường kể từ khi đón khách.

Dòng thứ $j$ ($1 \le j \le K$) trong $K$ dòng tiếp theo chứa $2$ số nguyên khác nhau $A_j, B_j$ ($1 \le A_j < B_j \le N$) cách nhau bởi dấu cách. Điều này cho biết có một con đường nối giữa thị trấn $A_j$ và thị trấn $B_j$. Không có cặp $(A_j, B_j)$ giống nhau nào xuất hiện từ $2$ lần trở lên.

Trong dữ liệu vào được cho, đảm bảo rằng từ bất kỳ thị trấn nào cũng có thể đi đến bất kỳ thị trấn nào khác bằng cách chuyển tiếp taxi.

Dữ liệu ra

In ra trên $1$ dòng một số nguyên biểu thị giá trị nhỏ nhất của tổng chi phí cần thiết để JOI-kun đi từ thị trấn $1$ đến thị trấn $N$.

Ví dụ

Ví dụ 1 - Dữ liệu vào

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

Ví dụ 1 - Dữ liệu ra

700

Ghi chú

Ví dụ trên tương ứng với hình vẽ dưới đây. Các hình tròn biểu thị các thị trấn, và các đoạn thẳng biểu thị các con đường.

Trong ví dụ này, để JOI-kun đến được thị trấn $6$ với chi phí nhỏ nhất, cậu thực hiện như sau:

• Bắt taxi từ thị trấn $1$ đi đến thị trấn $5$. (Giá cước $400$)
• Bắt taxi từ thị trấn $5$ đi đến thị trấn $6$. (Giá cước $300$)

Tổng chi phí khi JOI-kun đi theo lộ trình như vậy là $400 + 300 = 700$, do đó in ra $700$.