Đất nước IOI gồm \(N\) thị trấn, được đánh số từ \(1\) đến \(N\), nối với nhau bằng các con đường. Có \(K\) con đường, mỗi con đường nối hai thị trấn khác nhau. Xe có thể đi theo cả hai chiều trên mỗi con đường, nhưng không thể đi từ thị trấn này sang thị trấn khác mà không đi theo các con đường.

JOI sống ở thị trấn \(1\) và quyết định đi taxi đến nhà bà ở thị trấn \(N\). Đất nước IOI có \(N\) hãng taxi, được đánh số từ \(1\) đến \(N\). Các hãng taxi có những quy định hơi đặc biệt sau:

• Chỉ có thể lên taxi của hãng \(i\) tại thị trấn \(i\).
• Cước phí cho một chuyến taxi của hãng \(i\) là \(C_i\), không phụ thuộc vào quãng đường đã đi.
• Sau khi đón khách, taxi của hãng \(i\) chỉ có thể đi liên tiếp qua nhiều nhất \(R_i\) con đường.

Ví dụ, nếu \(R_1 = 2\), khi lên taxi của hãng \(1\) tại thị trấn \(1\), JOI chỉ có thể đi qua tối đa \(2\) con đường bằng chiếc taxi đó. Để đi qua từ \(3\) con đường trở lên, JOI phải đổi taxi tại một thị trấn trên đường đi.

JOI chỉ được lên hoặc xuống taxi tại các thị trấn, và không được sử dụng phương tiện di chuyển nào khác. Hãy viết chương trình tìm tổng cước phí nhỏ nhất để JOI đi đến thị trấn \(N\).

Dữ liệu vào

Dữ liệu vào gồm \(1 + N + K\) dòng:

• Dòng đầu tiên chứa hai số nguyên \(N, K\), cách nhau bởi dấu cách, lần lượt là số thị trấn và số con đường của đất nước IOI.
• Dòng thứ \(i\) trong \(N\) dòng tiếp theo (\(1 \le i \le N\)) chứa hai số nguyên \(C_i, R_i\), cách nhau bởi dấu cách. Taxi của hãng \(i\) có cước phí \(C_i\) và được đi qua nhiều nhất \(R_i\) con đường sau khi đón khách.
• Dòng thứ \(j\) trong \(K\) dòng tiếp theo (\(1 \le j \le K\)) chứa hai số nguyên khác nhau \(A_j, B_j\), cách nhau bởi dấu cách, cho biết có một con đường nối thị trấn \(A_j\) và thị trấn \(B_j\).

Dữ liệu ra

In ra một dòng chứa một số nguyên là tổng cước phí nhỏ nhất để JOI đi từ thị trấn \(1\) đến thị trấn \(N\).

Ràng buộc

• \(2 \le N \le 5000\).
• \(N - 1 \le K \le 10000\).
• \(1 \le C_i \le 10000\) và \(1 \le R_i \le N\) với mọi \(1 \le i \le N\).
• \(1 \le A_j < B_j \le N\) với mọi \(1 \le j \le K\).
• Không có cặp \((A_j, B_j)\) nào xuất hiện từ hai lần trở lên.
• Bảo đảm có thể đi từ bất kỳ thị trấn nào đến bất kỳ thị trấn nào khác bằng cách đi và đổi taxi.

Ví dụ

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

700

(5)---(1)---(2)---(4)
             |     |
            (3)---(6)