Có \(N\) chương trình cần phải thực hiện. Các chương trình này được đánh số từ \(1\) đến \(N\). Chương trình thứ \(i\) cần \(T_{i}\) đơn vị thời gian để hoàn thành. Tuy vậy có một số chương trình bắt buộc phải thực hiện sau một số chương trình khác (do nó cần số liệu từ các chương trình này để thực hiện). Nếu chương trình \(B\) cần số liệu của chương trình \(A\) thì chỉ khi chương trình \(A\) thực hiện xong, chương trình \(B\) mới có thể bắt đầu.

Trung tâm máy tính của công ty có thể huy động các máy tính để thực hiện số lượng tùy ý các chương trình đồng thời (khi không có quan hệ với nhau). Thời gian chuyển giao thực hiện chương trình trên một máy cũng như thời gian trao đổi dữ liệu giữa các chương trình trên các máy khác nhau có thể xem như bằng \(0\).

Hãy tính xem cần tối thiểu bao nhiêu thời gian để thực hiện \(N\) chương trình trên.

Input

• Dòng đầu tiên ghi hai số nguyên \(N\) và \(M\) \((1 \leq N \leq 10000, 1 \leq M \leq 50000)\). Ở đây \(M\) là số mỗi quan hệ trước-sau cần phải tuân thủ.
• \(N\) dòng tiếp theo, dòng thứ \(i\) ghi \(T_{i}\) \((1 \leq T_{i} \leq 10^{5})\).
• \(M\) dòng tiếp theo, mỗi dòng ghi hai số nguyên \(A\) và \(B\) với ý nghĩa là chương trình \(A\) phải được thực hiện xong trước khi thực hiện chương trình \(B\). Dữ liệu đảm bảo luôn có phương án thực hiện hết các chương trình (không xảy ra quan hệ vòng)

Output

• Một số nguyên duy nhất là thời gian nhỏ nhất tìm được.

Example

3 1
10
5
6
3 2

11