GukiZ and Candies

All submissions for this problem are available.
Read problems statements in Mandarin chinese , Russian and Vietnamese as well.
Professor GukiZ decided to distribute all of his candies to his $N$ students (numbered $1$ through $N$). Let's denote the number of candies GukiZ gave to the $i$th student by $p_i$. As GukiZ has a lot of students, he does not remember all the exact numbers of candies he gave to the students. He only remembers the following properties of the sequence $p$:  The numbers of candies given to each of the first $K$ students ($p_1, p_2, \dots, p_K$) are known exactly.  All elements of the sequence $p$ are distinct.  The difference between the maximum and minimum element of the sequence $p$ does not exceed $x$.  The professor gave out the biggest possible total number of candies, i.e. $S = p_1 + p_2 + p_3 + \ldots + p_N$ is maximum possible. Normally, professors never lie, so the information provided by GukiZ is valid and there is at least one sequence that satisfies all conditions. GukiZ would like to know the total number of candies $S$ he had at the beginning. Can you help him find this number? ### 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 three spaceseparated integers $N$, $K$ and $x$.  The second line contains $K$ spaceseparated integers $p_1, p_2, \dots, p_K$. ### Output For each test case, print a single line containing one integer — the number of candies GukiZ had. ### Constraints  $1 \le T \le 50$  $1 \le N \le 10^9$  $1 \le K \le \mathrm{min}(N, 2 \cdot 10^4)$  $0 \le x \le 10^9$  $1 \le p_i \le 10^9$ for each valid $i$  there is at least one valid distribution of candies to students ### Example Input ``` 2 4 3 4 2 1 5 2 2 9 3 6 ``` ### Example Output ``` 12 9 ``` ### Explanation **Example case 1:** There are four students. We know that the first student got $p_1 = 2$ candies, the second student got $p_2 = 1$ and the third got $p_3 = 5$ candies; we don't know the number of candies given to the last student. The difference between the maximum and minimum number of candies given to students is already $51 = 4 = x$, so the fourth student could only have been given between $1$ and $5$ candies. It can't be $5$ either, so we maximize the number of candies if we give $4$ candies to the fourth student. In total, there are $2 + 1 + 5 + 4 = 12$ candies. **Example case 2:** We know the number of candies given to each of the two students, so we know that GukiZ had $3 + 6 = 9$ candies.Author:  allllekssssa 
Editorial  https://discuss.codechef.com/problems/GUZAC 
Tags  allllekssssa, cookoff, cook97, greedy, math, taran_1407 
Date Added:  12082018 
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, CLOJ, COB, FS 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions