Một dự án nghiên cứu gồm \(N\) công việc, mỗi công việc có thể mang lại lợi nhuận (số dương) hoặc gây tổn thất (số âm). Giữa các công việc có mối quan hệ phụ thuộc: nếu công việc \(u\) phải được thực hiện trước công việc \(v\), thì khi chọn \(v\) bắt buộc phải chọn \(u\).

Chọn một tập hợp các công việc sao cho nếu một công việc được chọn thì tất cả công việc tiên quyết của nó cũng phải được chọn (tập đóng), và tổng lợi nhuận là lớn nhất.

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

• Dòng đầu chứa hai số nguyên \(N\), \(M\) (\(1 \le N \le 500\), \(0 \le M \le 10000\)).
• Dòng thứ hai chứa \(N\) số nguyên \(w_i\) (\(-10^4 \le w_i \le 10^4\)) là lợi nhuận/tổn thất của từng công việc.
• \(M\) dòng tiếp theo, mỗi dòng chứa hai số nguyên \(u\), \(v\) (\(1 \le u, v \le N\), \(u \neq v\)) cho biết \(u\) là tiên quyết của \(v\) (chọn \(v\) phải chọn \(u\)).

Định dạng đầu ra

• Một số nguyên duy nhất là tổng lợi nhuận lớn nhất.

Ví dụ

Input:

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

Output:

10