Một khu du lịch sinh thái tổ chức chuỗi sự kiện trải nghiệm kéo dài \(n\) ngày. Mỗi ngày ở khu du lịch sẽ có một hoạt động đặc sắc mang lại sự hài lòng lớn cho du khách. Theo kế hoạch, Ban quản lý dự kiến tổ chức đúng \(n\) hoạt động, mỗi hoạt động diễn ra trong đúng \(1\) ngày và không có ngày nào có \(2\) hoạt động cùng diễn ra. Theo tính toán, hoạt động thứ \(i\) có độ hấp dẫn là \(a_i\) (\(1 \le i \le n\)).

Gồm \(m\) đoàn khách đã đăng kí, đoàn thứ \(j\) (\(1 \le j \le m\)) từ ngày \(L_j\) đến hết ngày \(R_j\). Để các đoàn khách có trải nghiệm tốt nhất, Ban quản lý quyết định sắp xếp lại thứ tự các hoạt động để có tổng hiệu quả hài lòng của tất cả các đoàn đăng kí là lớn nhất. Biết hiệu quả hài lòng của mỗi đoàn khách là tổng độ hấp dẫn của các hoạt động diễn ra trong thời gian đoàn khách đó lưu trú.

Yêu cầu: Hãy xác định tổng hiệu quả hài lòng lớn nhất có thể đạt được.

Input

• Dòng đầu tiên chứa \(2\) số nguyên \(n\) và \(m\) (\(1 \le n, m \le 3 \cdot 10^5\)).
• Dòng thứ \(2\) chứa \(n\) số nguyên \(a_1, a_2, \dots, a_n\) (\(1 \le a_i \le 10^6, \forall i = 1, 2, \dots, n\)).
• Dòng thứ \(j\) trong \(m\) dòng tiếp theo chứa \(2\) số nguyên \(L_j, R_j\) (\(1 \le L_j \le R_j \le n, \forall j = 1, 2, \dots, m\)).

Output

• Ghi ra một số nguyên là tổng hiệu quả hài lòng lớn nhất có thể đạt được.

Example

3 2
70 30 10
1 2
2 3

180

3 3
10 70 30
1 3
1 2
1 1

280

Scoring

• Subtask \(1\) (\(0.3\) điểm): \(m = 1; n \le 3 \cdot 10^5; a_1 \le a_2 \le \dots \le a_n\).
• Subtask \(2\) (\(0.4\) điểm): \(m \le 100; n \le 3 \cdot 10^5; L_j = 1, \forall j = 1, 2, \dots, m\).
• Subtask \(3\) (\(0.5\) điểm): \(m \le 100; n \le 3 \cdot 10^5\).
• Subtask \(4\) (\(0.8\) điểm): Không có ràng buộc bổ sung.