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+1R_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 spaceseparated integers $N$ and $M$.  The second line contains $N$ spaceseparated 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 spaceseparated 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.Author:  i_love_islam 
Editorial  https://discuss.codechef.com/problems/FRICAN 
Tags  cook109, greedy, i_love_islam, medium, observations, taran_1407 
Date Added:  17082019 
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, SQL, kotlin, PERL6, TEXT, SCM chicken, PYP3, CLOJ, R, COB, FS 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions
HELP
If you are still having problems, see a sample solution here. 