FC là một vương quốc giàu có, sở hữu một mạng lưới giao thông phát triển. Vương quốc gồm \(n\) thị trấn, được đánh số từ 1 đến \(n\) và \(m\) đường đi một chiều kết nối \(n\) thị trấn đó. Mỗi thị
trấn ở vương quốc này đều có một chỉ số wi đại diện cho độ quan trọng của thị trấn ấy.

Để kỷ niệm ngày Quốc Khánh, vua Kiên đã yêu cầu tổ chức một buổi diễu hành vòng quanh vương quốc. Đoàn diễu hành sẽ xuất phát từ thị trấn 1 và dừng lại ở thị trấn \(n\).

Vua Kiên muốn chọn đường đi diễu hành qua các thị trấn sao cho độ quan trọng đường đi là nhỏ nhất. Trong khi đó, Quang - vị tướng chỉ huy lại muốn độ quan trọng của đường đi là lớn nhất.
Độ quan trọng của một đường đi được tính bằng tổng độ quan trọng của các thị trấn mà đoàn diễu hành đã đi qua. Lưu ý rằng đoàn diễu hành có thể đi ngang một thị trấn nhiều hơn một lần,
nhưng độ quan trọng của thị trấn ấy chỉ được tính một lần duy nhất.

LH nhận thấy đây là một bài toán rất thú vị và quyết định dùng nó cho kỳ thi lần này. Bạn hãy giúp nhà vua và vị tướng tính độ quan trọng nhỏ nhất và lớn nhất có thể của đường đi từ thị trấn 1 đến thị trấn n nhé."

Input

• Dòng đầu tiên chứa 2 số nguyên dương \(n, m\) lần lượt là số lượng thị trấn và số lượng con
  đường một chiều trong mạng lưới giao thông (\(2 \le n \le 100000, 1 \le m \le 100000\)).
• \(n\) dòng tiếp theo chứa \(n\) số nguyên dương \(w_1, w_2, ..., w_n\) lần lượt là độ quan trọng của \(n\) thị trấn trong vương quốc \((1 \le w_i \le 1000)\).
• \(m\) dòng tiếp theo, mỗi dòng chứa hai số nguyên dương \(u, v\) miêu tả rằng có một đường một chiều kết nối giữa hai thị trấn \(u\) và \(v\) trong mạng lưới giao thông (\(u, v \le n\)).

Output

• Đưa ra 2 số nguyên trên một dòng duy nhất lần lượt là độ quan trọng nhỏ nhất và độ quan trọng lớn nhất có thể của đường đi từ thị trấn 1 đến thị trấn \(n\).
• Nếu không tồn tại bất kỳ đường đi nào từ 1 đến \(n\), bạn chỉ cần đưa ra kết quả gồm duy nhất một số \(−1\).

Scoring

• Subtask \(1\) (\(10\%\) số điểm): \(n, m \le 20\).
• Subtask \(2\) (\(20\%\) số điểm): \(n, m \le 100\).
• Subtask \(3\) (\(70\%\) số điểm): không có giới hạn gì thêm.

Example

5 6
1 1 1 1 1
1 2
3 1
2 1
2 3
3 4
2 5

3 4