{"code":"maxsumquery","name":"Tổng truy vấn lớn nhất","description":"Cho một mảng gồm $n$ phần tử và $q$ truy vấn, mỗi truy vấn được định nghĩa bởi một cặp số nguyên $l_i,r_i(1\\le l_i\\le r_i\\le n)$ và nhiệm vụ của ta là ứng với mỗi truy vấn, ta cần tìm tổng các phần tử của mảng từ $l_i$ đến $r_i$. (bao gồm cả $l_i,r_i$)\r\n\r\nNhưng có một điều đặc biệt là trước khi thực hiện $q$ truy vấn này, ta cần phải sắp xếp lại mảng theo thứ tự nào đó sao cho tổng tất cả các kết quả của $q$ truy vấn nhận được là lớn nhất có thể, và tổng kết quả lớn nhất đó chính là kết quả cần tìm.\r\n\r\n

Input

\r\n\r\n+ Dòng thứ nhất chứa hai số nguyên $n,q(1\\le n\\le 200000,1\\le q\\le 200000)$ \r\n\r\n+ $q$ dòng tiếp theo, mỗi dòng chứa cặp số nguyên $l_i,r_i(1\\le l_i\\le r_i\\le n)$\r\n\r\n

Output

\r\n\r\n+ In ra giá trị cần tìm\r\n\r\n

Example

\r\n\r\n!!! question \"Test 1\"\r\n\r\n ???+ \"Input\"\r\n\r\n ```sample\r\n 5 3\r\n 3 2 1 5 4\r\n 1 2\r\n 1 3\r\n 2 3\r\n ```\r\n\r\n ???+ success \"Output\"\r\n\r\n ```sample\r\n 29\r\n ```\r\n \r\n ??? warning \"Note\"\r\n\r\n Đầu tiên ta sắp xếp mảng đã cho lại thành: $3,5,4,1,2$. Khi đó: Ta có tổng lớn nhất cần tìm là: $8+12+9=29$","points":350.0,"partial":false,"time_limit":1.0,"memory_limit":262144,"short_circuit":false,"allowed_languages":[3,4,34,36,37,5,6,11,12,14,28,2,38,39,9,18,17,29,23,27,35,25,26,10,7,19,32,1,8,15,16,24,20,33,13,41,21,40],"is_public":true,"is_manually_managed":false,"permissions":{"can_edit":false}}