Công ty NIV đang nghiên cứu \(n\) dự án. Qua khảo sát, dự án thứ \(i\) nếu thực hiện xong sẽ mang về lợi nhuận \(p_i\ (\mid p_i\mid \leq 10^9)\). Tuy nhiên, không thể chọn chỉ làm các dự án lãi. Ví dụ dự án xây dựng khu đô thị phải kèm theo việc phải thực hiện xây dựng các dự án hệ thống cơ sở hạ tầng giao thông kết nối xung quanh. Có \(m\) ràng buộc về việc triển khai dự án có dạng \((u,\ v)(u < v\leq u+10)\) cho biết để thực hiện dự án \(v\), cần thực hiện dự án \(u\) trước.

Yêu cầu: Hãy cho biết với cách lựa chọn dự án tối ưu, công ty có thể thu về lợi nhuận tối đa là bao nhiêu?

Input:

• Dòng đầu tiên chứa \(2\) số nguyên dương \(n,\ m\ (n\leq 10^5;\ m\leq 10^6)\)
• Dòng thứ \(2\) chứa \(n\) số nguyên \(p_1,\ p_2,\ldots ,\ p_n\) xác định lợi nhuận thu được khi làm dự án \(i\)
• \(m\) dòng tiếp, dòng thứ \(i\) chứa \(2\) số \(u_i\) và \(v_i\) cho biết muốn thực hiện dự án \(v_i\) cần thực hiện dự án \(u_i\) trước

Output: Một số nguyên duy nhất là lợi nhuận lớn nhất thu được trong trường hợp chọn tối ưu.

Ví dụ:

SAMPLE INPUT

6 4
-5 3 -1 -7 10 4
1 5
2 5
3 5
4 6

SAMPLE OUTPUT

7

Ràng buộc:

• \(20\%\) số test tương ứng \(20\%\) số điểm có \(n\leq 15\)
• \(20\%\) số test khác tương ứng \(20\%\) số điểm có \(v_i = u_i + 1\) với mọi cạnh \((u_i,\ v_i)\)
• \(20\%\) số test khác tương ứng \(20\%\) số điểm có \(v_i\leq u_i + 2\) với mọi cạnh \((u_i,\ v_i)\)
• \(40\%\) số test còn lại tương ứng \(40\%\) số điểm không có ràng buộc bổ sung.