Friends and Candies
All submissions for this problem are available.### Read problems statements in [Hindi](http://www.codechef.com/download/translated/COOK109/hindi/FRICAN.pdf), [Mandarin Chinese](http://www.codechef.com/download/translated/COOK109/mandarin/FRICAN.pdf), [Russian](http://www.codechef.com/download/translated/COOK109/russian/FRICAN.pdf), [Vietnamese](http://www.codechef.com/download/translated/COOK109/vietnamese/FRICAN.pdf), and [Bengali](http://www.codechef.com/download/translated/COOK109/bengali/FRICAN.pdf) as well. Hasan is preparing a party for his $M$ friends (numbered $1$ through $M$). He bought $N$ baskets of candies (numbered $1$ through $N$); for each valid $i$, the $i$-th basket contains $a_i$ candies. Each friend should get at most one candy. For each valid $i$, the $i$-th friend would like to get a candy either from one of the first $L_i$ baskets or one of the last $R_i$ baskets, i.e. a from basket $b$ ($1 \le b \le N$) such that $b \le L_i$ or $b \ge N+1-R_i$. Hasan loves his friends, so he wants as many of them as possible to get the candies they want. If he distributes the candies optimally, what is the maximum number of his friends who will get the candies they want? ### Input - The first line of the input contains a single integer $T$ denoting the number of test cases. The description of $T$ test cases follows. - The first line of each test case contains two space-separated integers $N$ and $M$. - The second line contains $N$ space-separated integers $a_1, a_2, \ldots, a_N$. - $M$ lines follow. For each $i$ ($1 \le i \le M$), the $i$-th of these lines contains two space-separated integers $L_i$ and $R_i$. ### Output For each test case, print a single line containing one integer — the maximum number of Hasan's friends who can get the candies they want. ### Constraints - $1 \le T \le 10^3$ - $1 \le N, M \le 10^6$ - $0 \le a_i \le 10^6$ for each valid $i$ - $0 \le L_i, R_i \le N$ for each valid $i$ - $0 \le L_i + R_i \le N$ for each valid $i$ - the sum of $N$ over all test cases does not exceed $10^6$ - the sum of $M$ over all test cases does not exceed $10^6$ ### Example Input ``` 2 3 3 1 1 1 0 2 1 1 0 2 3 3 1 1 1 1 1 1 1 1 1 ``` ### Example Output ``` 3 2 ``` ### Explanation **Example case 1:** We can give a candy from basket $1$ to the $2$-nd friend, a candy from basket $2$ to the $1$-st friend and a candy from basket $3$ to the $3$-rd friend.
|Tags||cook109, greedy, i_love_islam, medium, observations, taran_1407|
|Time Limit:||2 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, rust, SCALA, swift, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, kotlin, PERL6, TEXT, SCM chicken, PYP3, CLOJ, R, COB, FS|
Fetching successful submissions
If you are still having problems, see a sample solution here.