\(N\) con bò của Farmer John (\(1 \le N \le 10\,000\)) được đánh số thuận tiện từ \(1\) đến \(N\). Việc vắt sữa bò thứ \(i\) mất \(T(i)\) đơn vị thời gian. Thật không may, do cách bố trí chuồng của FJ, một số con bò phải được vắt sữa trước những con khác. Nếu bò \(A\) phải được vắt sữa trước bò \(B\), thì FJ cần hoàn tất việc vắt sữa bò \(A\) trước khi có thể bắt đầu vắt sữa bò \(B\).

Để vắt sữa đàn bò nhanh nhất có thể, FJ đã thuê rất nhiều người làm nông hỗ trợ công việc — đủ người để vắt sữa đồng thời bao nhiêu con bò cũng được. Tuy nhiên, dù các con bò có thể được vắt sữa cùng lúc, các ràng buộc yêu cầu một số con bò phải được vắt sữa trước những con khác vẫn giới hạn tốc độ hoàn thành toàn bộ quá trình. Hãy giúp FJ tính tổng thời gian tối thiểu mà quá trình vắt sữa phải mất.

Dữ liệu vào

• Dòng đầu tiên chứa hai số nguyên \(N\) (số lượng bò) và \(M\) (số lượng ràng buộc về thứ tự vắt sữa; \(1 \le M \le 50\,000\)), cách nhau bởi dấu cách.
• \(N\) dòng tiếp theo: dòng thứ \(i\) chứa giá trị \(T(i)\) (\(1 \le T(i) \le 100\,000\)).
• \(M\) dòng tiếp theo, mỗi dòng chứa hai số nguyên \(A\) và \(B\), cách nhau bởi dấu cách, cho biết bò \(A\) phải được vắt sữa xong hoàn toàn trước khi có thể bắt đầu vắt sữa bò \(B\). Các ràng buộc này không bao giờ tạo thành chu trình, vì vậy luôn tồn tại lời giải.

Dữ liệu ra

In ra lượng thời gian tối thiểu cần để vắt sữa tất cả các con bò.

Ví dụ

3 1
10
5
6
3 2

11

Nguồn

USACO 2013 February Contest, Silver — Problem 3: Milk Scheduling

Tác giả đề: Kalki Seksaria, 2013.