Veverița

Time limit: 1s Memory limit: 256MB Input: Output:

ASG s-a jucat foarte foarte foarte mult Fortnite. S-a dus la mall și a cumpărat o pușcă NERF. Apoi, a început sa fugăreasca prin parc o veveriță cu multe nuci. Dupa ce a alergat-o prin toată Peninsula Balcanică, a ajuns la vizuina ei din Iași. Acolo, aceasta i-a spus lui ASG că-i poate da un anumit număr de nuci pentru a o lăsa in pace. Cum veverița are foarte multe nuci și ASG adoră nucile, a decis să negocieze cu ea. Până la urmă, s-au hotărât că vor scrie pe o foaie un șir aa de NN elemente ce denotă greutățile nucilor. Veverița îi va da apoi lui ASG TT intervale închise de forma [x,y][x, y], cu proprietatea că ASG poate lua câte o nucă dacă este inclusă greutatea ei in respectivul interval. Dat fiind că sunt mai multe intervale, ASG poate lua o nucă de o anumită greutate de mai multe ori. Cum veverița este magică, are un număr infinit de nuci, șirul aa exprimând doar greutățile pe care le are în stoc.

Cerință

Ajutați-l pe ASG să afle câte nuci poate lua acasă cât mai rapid, ca să plece din Iași înainte să afle Flaviu că este în același oraș cu el.

Date de intrare

Pe prima linie se găsesc două numere întregi, NN și TT.
Pe a doua linie se găsesc NN numere naturale, elementele șirului aa.
Pe urmatoarele TT linii se găsește câte o pereche de două numere naturale, xx și yy, cu semnificațiile din enunț.

Date de ieșire

Pe prima linie se va găsi un singur număr întreg, numărul de nuci pe care le ia ASG acasă.

Restricții și precizări

  • 1N,T500 0001 \leq N, T \leq 500 \ 000;
  • 0ai1 000 000 0000 \leq a_i \leq 1 \ 000 \ 000 \ 000;
  • 0x,y1 000 000 0000 \leq x, y \leq 1 \ 000 \ 000 \ 000.

Exemplul 1

stdin

5 3
1 2 3 4 5
1 3
2 4
1 5

stdout

11

Explicație

Avem 33 intervale de analizat.
în intervalul [1,3][1, 3] se află 33 numere naturale din șirul aa. (11, 22, 33);
În intervalul [2,4][2, 4] se află 33 numere naturale din șirul aa. (22, 33, 44);
În intervalul [1,5][1, 5] se afla 55 numere naturale din șirul aa. (11, 22, 33, 44, 55).
În total, avem 33 + 33 + 55, adică ASG ia acasă 1111 nuci.

Exemplul 2

stdin

1 3
4
1 3
1 4
4 4

stdout

2

Explicație

Avem 33 intervale de analizat.
în intervalul [1,3][1, 3] nu se află niciun număr din șirul aa, dat fiind că este format doar din 4.
În intervalul [1,4][1, 4] se găsește elementul 44.
În intervalul [4,4][4, 4] singurul element este 44, exact elementul din șirul aa.
În total, avem 11 + 11, adică ASG ia acasă 22 nuci.

Log in or sign up to be able to send submissions!