Du lịch máy bay
An muốn có một thử thách du lịch liên tục qua nhiều nước bằng máy bay.
Có tất cả $N$ đất nước, được đánh số từ 1 đến $N$. Có tất cả $N-1$ chuyến bay hai chiều, chuyến thứ $i$ nối đất nước thứ $i$ với đất nước thứ $i+1$.
Ban đầu An ở đất nước thứ nhất, được giao $K$ hành trình theo thứ tự từ 1 đến $K$ và các hành trình An chọn phải đúng thứ tự đó. Với hành trình thứ $i$, An sẽ bay từ đất nước $U_i$ đến đất nước $V_i$, thông qua một chuỗi ít nhất các chuyến bay. An chỉ có thể chọn hành trình bay này nếu An đang ở đất nước $U_i$ và sau khi thực hiện xong thì An sẽ ở đất nước $V_i$. Lưu ý đối với mỗi hành trình, An có thể không thực hiện.
Tại mỗi đất nước, chương trình có phần thưởng cho mỗi lần ghé qua. Với mỗi hành trình hoàn thành, An sẽ nhận được phần thưởng là giá trị lớn nhất trong số các phần thưởng trên các đất nước đã thăm trong hành trình bay, tính cả đất nước xuất phát và kết thúc.
Hãy tính tổng giá trị phần thưởng lớn nhất mà An có thể nhận được sau $K$ hành trình.
Dữ liệu
- Dòng đầu tiên chứa hai số nguyên $N,K \ (1\le N,K \le 2\times10^5)$;
- Dòng thứ hai chứa $N$ số nguyên $W_i \ (0\le W_i \le 10^9)$ - là giá trị phần thưởng đặt tại đất nước thứ $i$;
- $K$ dòng tiếp theo, mỗi dòng chứa hai số nguyên $U_i,V_i \ (1\le U_i,V_i \le N; U_i \neq V_i)$.
Kết quả
- Kết quả bài toán.
Chấm điểm
30;$N,K\le100$. 30;$N\le10^4;K\le100$. 40;Không có giới hạn gì thêm.
Ví dụ
Ví dụ 1
input
4 4
1 2 3 4
1 3
1 2
2 3
2 4
output
6
Comments