로건과 질의

교수 X에게 정수 $n$개로 이루어진 배열이 있다. 교수 X는 $q$개의 질의를 한다. 각 질의는 정수 $l$과 $r$로 이루어지며, 질의의 답은 원래 배열에서 인덱스가 $l$부터 $r$까지인 원소들의 합이다.

교수 X의 행복 수준은 모든 질의 답의 총합이다.

로건은 교수 X를 최대한 행복하게 만들고 싶어 한다. 이를 위해 배열의 원소 순서를 자유롭게 바꿀 수 있다. 그러나 그는 이 일을 혼자서 해내지 못해서 여러분에게 도움을 청했다.

여러분의 과제는 배열의 원소 순서를 자유롭게 바꿀 수 있을 때, 교수 X의 행복 수준이 가질 수 있는 최댓값을 구하는 것이다.

첫째 줄에 정수 $n$과 $q$가 주어진다 ($1 \leq n, q \leq 10^5$).

둘째 줄에는 배열의 원소 $a_i$가 $n$개 주어진다 ($1 \leq a_i \leq 10^8$).

이후 $q$개의 줄에 구간의 양 끝을 나타내는 정수 $l$과 $r$이 한 쌍씩 주어진다 ($1 \leq l \leq r \leq n$).

원소의 순서를 자유롭게 바꿀 수 있을 때, 교수 X의 행복 수준의 최댓값을 정수 하나로 출력한다.