E. Tree Counting
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Green Street is a street with $$$N$$$ blocks labeled from $$$1$$$ to $$$N$$$, and block $$$i$$$ has $$$T_i$$$ trees on the block. Clare goes on $$$M$$$ walks labeled from $$$1$$$ to $$$M$$$, and walk $$$i$$$ is between blocks $$$A_i$$$ and $$$B_i$$$ inclusive. How many trees does Clare walk past?

Input

Line $$$1$$$: Two space separated integers $$$N$$$ ($$$1 \le N \le 200$$$) and $$$M$$$ ($$$1 \le M \le 10^4$$$).

Line $$$2$$$: $$$N$$$ space separated integers $$$T_i$$$ ($$$1 \le T_i \le 20$$$).

Lines $$$3...M+2$$$: Two space separated integers $$$A_i$$$ and $$$B_i$$$ ($$$1 \le A_i, B_i \le N$$$).

Output

Line $$$1$$$: The number of trees Clare walks past.

Example
Input
4 2
2 1 6 1
1 2
2 4
Output
11
Note

$$$1 \le N \le 200$$$

$$$1 \le M \le 10^4$$$

$$$1 \le T_i \le 20$$$

$$$1 \le A_i, B_i \le N$$$