Willson with his cute and fluffy baby geese.

Willson the Canada Goose is like any other Canada Goose - he now has several goslings (baby geese) to take care of!

Willson has ~N~ goslings, numbered from ~1~ to ~N~, that are currently feeding on grass. There are many patches of grass in the field that they are in, in fact, for all ~x~ from ~1~ to ~M~, there are infinitely many patches of grass containing ~x~ blades of grass.

The goslings are also bored, so they decide to play a game. The goslings will take turns eating all the blades of grass in one patch. However, each gosling must consume a patch with a strictly greater number of blades than the previous gosling. The goslings will take turns in order starting from ~1~, and will cycle around, that is, gosling ~1~ will take a turn after gosling ~N~.

However, goslings have different appetites. The ~i^\text{th}~ gosling can eat up to ~g_i~ blades of grass in total. A gosling will not eat from a patch if consuming the whole patch would result in its eating more than ~g_i~ blades in total.

The goslings agree that in the end, each gosling must consume the same number of patches. Thus, the game can only end after gosling ~N~ takes his turn. Note that the goslings must play in a way that they can always choose a patch to eat before the end of the game, and that it is possible that no gosling eats any grass.

Willson is interested in his children's game and wonders about the maximum total number of blades of grass that can be eaten by the goslings. Can you tell him?

Constraints

~2 \le N \le 2 \times 10^5~

~N \le M \le 5 \times 10^6~

Subtask	Percentage	Additional Constraints
~1~	~15~	~M \le 20~
~2~	~10~	~M \le 200~
~3~	~15~	~M \le 2\,000~
~4~	~60~	No additional constraints.

Input Specification

The first line of input will contain ~N~ and ~M~.

~N~ lines of input follow. The ~i^\text{th}~ line will contain ~g_i~. It is guaranteed that ~1 \le g_i \le \dfrac{M(M+1)}{2}~.

Output Specification

Output on a single line the maximum total number of blades of grass that can be eaten.

Sample Input

2 6
6
15

Sample Output

16

Explanation for Sample Output

The game could go like this:

• Gosling 1 eats 1 blade
• Gosling 2 eats 4 blades
• Gosling 1 eats 5 blades
• Gosling 2 eats 6 blades