스터디 카페

주원이는 스터디 카페를 운영하고 있다. 스터디 카페에는 $N$개의 좌석이 있으며, $i$번째 좌석의 하루 요금은 $A_i$이다.

주원이는 최근에 새로운 아르바이트생을 고용했다. 아르바이트생에게는 이용자가 가능한 한 비싼 좌석을 이용하도록 유도하는 업무를 맡겼다. 주원이는 아르바이트생이 정말로 열심히 일하고 있는지 확인하고 싶어 한다.

스터디 카페 이용 기록이 $M$개 있다. 각 기록은 어떤 이용자가 $S_i$일부터 $E_i$일까지 스터디 카페를 이용했다는 내용이다. 이용자는 이용 기간 동안 매일 아르바이트생이 지정한 좌석 하나의 요금을 내고, 그 좌석을 하루 동안 점유한다. 이용자의 좌석은 날마다 바뀔 수 있다.

주원이는 이용 기록으로 스터디 카페가 얻을 수 있었던 최소 수익과 최대 수익을 계산해서, 아르바이트생이 얼마나 열심히 일하고 있는지 확인하려고 한다. 주원이를 도와 최소 수익과 최대 수익을 계산해 보자.

첫 번째 줄에 $N$과 $M$이 공백을 사이에 두고 주어진다.

두 번째 줄에는 $A_1, A_2, \cdots, A_N$이 공백으로 구분되어 주어진다.

세 번째 줄부터 $M$개의 줄에는 이용 기록이 주어진다. 이 중 $i$번째 줄에는 $S_i$와 $E_i$가 공백을 사이에 두고 주어진다.

주원이가 얻을 수 있었던 최소 수익과 최대 수익을 공백을 사이에 두고 출력한다.

• $1 \leq M \leq N \leq 500\,000$
• $0 \leq A_i \leq 10\,000$ ($1 \leq i \leq N$)
• $1 \leq S_i \leq E_i \leq 10^9$ ($1 \leq i \leq M$)