Drink Slush

All submissions for this problem are available.
### Read problems statements in [Hindi](http://www.codechef.com/download/translated/COOK107/hindi/SLUSH.pdf), [Mandarin Chinese](http://www.codechef.com/download/translated/COOK107/mandarin/SLUSH.pdf), [Russian](http://www.codechef.com/download/translated/COOK107/russian/SLUSH.pdf), [Vietnamese](http://www.codechef.com/download/translated/COOK107/vietnamese/SLUSH.pdf), and [Bengali](http://www.codechef.com/download/translated/COOK107/bengali/SLUSH.pdf) as well. Chef is operating a slush machine. The machine produces slush drinks with $M$ flavors (numbered $1$ through $M$); for each valid $i$, the maximum number of drinks with flavour $i$ the machine can produce is $C_i$. Chef expects $N$ customers to come buy slush drinks today. The customers are numbered $1$ through $N$ in the order in which they buy the drinks. For each valid $i$, the favorite flavour of the $i$th customer is $D_i$ and this customer is willing to pay $F_i$ units of money for a drink with this flavour, or $B_i$ units of money for a drink with any other flavuor. Whenever a customer wants to buy a drink:  if it is possible to sell this customer a drink with their favourite flavour, Chef must sell them a drink with this flavour  otherwise, Chef must sell this customer a drink, but he may choose its flavour Chef wants to make the maximum possible profit. He is asking you to help him decide the flavours of the drinks he should sell to the customers in order to maximise the profit. ### 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 $M$ spaceseparated integers $C_1, C_2, \ldots, C_M$.  $N$ lines follow. For each valid $i$, the $i$th of these lines contains three spaceseparated integers $D_i$, $F_i$ and $B_i$. ### Output For each test case, print two lines:  The first of these lines should contain a single integer — the maximum profit.  The second line should contain $N$ spaceseparated integers denoting the flavours of the drinks Chef should sell, in this order. If there are multiple solutions, you may find any one. ### Constraints  $1 \le T \le 1,000$  $2 \le N, M \le 10^5$  $1 \le D_i \le M$ for each valid $i$  $1 \le C_i \le N$ for each valid $i$  $1 \le B_i \lt F_i \le 10^9$ for each valid $i$  $C_1+C_2+\ldots+C_M \ge N$  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 ``` 1 5 3 1 2 3 2 6 3 2 10 7 2 50 3 1 10 5 1 7 4 ``` ### Example Output ``` 33 2 2 3 1 3 ```Author:  kingofnumbers 
Editorial  https://discuss.codechef.com/problems/SLUSH 
Tags  cookoff, cook107, kingofnumbers 
Date Added:  19062019 
Time Limit:  1 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 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions