Approaching his eighties, Mr. Ben ran out of things to do, so he decided to open another business. This time, he placed soda machines across the nearest mall, numbered from to . Each of the soda machines can hold up to dollars, and in some of them, Mr. Ben already put some cash in order to give out change. In particular, the soda machine with number (1 \leq i \leq n) already has a_i (0 \leq a_i < x) cash in it.
For the next 10^{100} days, at the end of each day, the following happens:
The amount of cash in each soda machine increases by .
If after the increase the amount of cash in a soda machine becomes at least , then Mr. Ben's assistant will take out all the cash from this machine, so it becomes dollars.
As Mr. Ben's accountant, your job is now to find the maximal total cash contained in all soda machines after days, for some integer (1 \leq t \leq 10^{100}).
The first line of the input contains two integers (1 \leq n \leq 2 \cdot 10^5, 2 \leq x \leq 10^{12}) — the amount of soda machines and the maximum cash capacity, respectively.
The second line of the input contains integers a_1, a_2, \ldots, a_n (0 \leq a_i < x) — the initial amount of cash in each soda machine.
Output a single integer — the maximum total cash contained in all of the soda machines after some day.
Example 1
Example 2
In the first example, after day the amounts of cash in the machines are (), so the total cash is 1+2+2=5, which is the maximum over all days.
In the second example, after day the amounts of cash in the machines are (2,2,2,5,5,5,6,6), so the total cash is , which is the maximum over all days. For instance, after other days the amounts of cash in the machines are the following:
After day the amounts of cash are (6,6,6,2,2,2,3,3), so the total cash is .
After day the amounts of cash are (1,1,1,4,4,4,5,5), so the total cash is .
After day the amounts of cash are (4,4,4,0,0,0,1,1), so the total cash is .
( points) x = 2;
( points) n \leq 1000, x \leq 1000;
( points) n \leq 100;
( points) x \leq 10^5;
( points) no additional restrictions.