Một dự án phần mềm của Tý gồm \(N\) công việc (được đánh số từ \(1\) đến \(N\)). Công việc \(i\) cần thời gian hoàn thành liên tục là \(D[i]\) ngày.

Có \(M\) điều kiện phụ thuộc có hướng giữa các công việc, công việc \(u\) phải hoàn thành trước công việc \(v\). Nhiều công việc có thể làm song song nếu không có quan hệ phụ thuộc.

Hãy tìm thời gian tối thiểu để hoàn thành toàn bộ dự án (tổng thời gian hoàn thành dãy công việc găng nhất).

Định dạng đầu vào

• Dòng đầu chứa hai số nguyên \(N\) và \(M\) (\(1 \le N \le 10^5\), \(0 \le M \le 2 \cdot 10^5\)).
• Dòng thứ hai chứa \(N\) số nguyên \(D[1], D[2], \dots, D[N]\) (\(1 \le D[i] \le 10^4\)).
• \(M\) dòng tiếp theo, mỗi dòng chứa hai số nguyên \(u, v\) (\(1 \le u, v \le N\)) mô tả việc \(u\) phải làm trước \(v\). Bản đồ phụ thuộc bảo đảm không có chu trình.

Định dạng đầu ra

• Một số nguyên duy nhất là số ngày tối thiểu để hoàn thành dự án.

Ràng buộc

Ví dụ

Input:

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

Output:

12

(Giải thích ví dụ: Con đường dài nhất (đường găng) là 1 -> 3 -> 4 có tổng thời gian là D[1] + D[3] + D[4] = 3 + 4 + 5 = 12 ngày).