Study Cafe

Interview

Time limit2sMemory limit1024 MB

Summary

Given seat fees and customer stay intervals, find the minimum and maximum total revenue when each day every active customer takes a distinct seat.

Level: Medium4 of 10
Topics: Sorting, Prefix sum, Intervals
Solved: No attempts yet

Problem

Joowon runs a study cafe. The cafe has $N$ seats, and the daily fee for the $i$ -th seat is $A_i$ .

Joowon recently hired a new part-time worker and assigned them the job of guiding customers toward the most expensive seats possible. Joowon wants to check whether the worker is really working hard.

The cafe has $M$ usage records. Each record says that a customer used the study cafe from day $S_i$ to day $E_i$ . Every day of the stay, the customer pays the fee of one seat that the part-time worker assigned and occupies that seat for the day. A customer's seat can change from day to day.

Using the records, Joowon wants to compute the minimum and maximum revenue the cafe could have earned, so he can see how hard the worker is working. Help Joowon compute the minimum and maximum revenue.

Input

The first line contains $N$ and $M$ separated by a space.

The second line contains $A_1, A_2, \cdots, A_N$ separated by spaces.

Each of the following $M$ lines contains $S_i$ and $E_i$ separated by a space.

Output

Print the minimum revenue and the maximum revenue separated by a space.

Constraints

$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$ )

Examples2

Example 1
Input
```
3 2
1 10 100
5 7
2 6
```
Expected output
```
26 620
```
Example 2
Input
```
1 1
0
1 10
```
Expected output
```
0 0
```