스터디 카페

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

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

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

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

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

두 번째 줄에는 $A\_1, A\_2, \cdots, A\_N$이 공백으로 구분되어 주어진다.

세 번째 줄부터 $M$개의 줄에는 이용 기록이 주어지는데, 이 중 $i(1 \leq i \leq M)$번째 줄에는 $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$)