CF183E.Candy Shop

The prestigious Codeforces kindergarten consists of n kids, numbered 1 through n. Each of them are given allowance in rubles by their parents.

Today, they are going to the most famous candy shop in the town. The shop sells candies in packages: for all i between 1 and m, inclusive, it sells a package containing exactly i candies. A candy costs one ruble, so a package containing x candies costs x rubles.

The kids will purchase candies in turns, starting from kid 1. In a single turn, kid i will purchase one candy package. Due to the highly competitive nature of Codeforces kindergarten, during a turn, the number of candies contained in the package purchased by the kid will always be strictly greater than the number of candies contained in the package purchased by the kid in the preceding turn (an exception is in the first turn: the first kid may purchase any package). Then, the turn proceeds to kid i + 1, or to kid 1 if it was kid n's turn. This process can be ended at any time, but at the end of the purchase process, all the kids must have the same number of candy packages. Of course, the amount spent by each kid on the candies cannot exceed their allowance.

You work at the candy shop and would like to prepare the candies for the kids. Print the maximum number of candies that can be sold by the candy shop to the kids. If the kids cannot purchase any candy (due to insufficient allowance), print 0.

著名的 Codeforces 幼儿园共有 $n$ 个孩子，编号为 $1$ 到 $n$。每个孩子都会从父母那里获得一定数额的卢布作为零花钱。

今天，他们将前往镇上最著名的糖果店。该店以“包装”形式出售糖果：对所有满足 $1 \le i \le m$ 的整数 $i$，均出售恰好包含 $i$ 颗糖果的包装。每颗糖果售价为 1 卢布，因此含 $x$ 颗糖果的包装售价为 $x$ 卢布。

孩子们将按顺序购买糖果，起始者为孩子 $1$。在单次轮次中，孩子 $i$ 将购买一个糖果包装。由于 Codeforces 幼儿园内部竞争极为激烈，在某一轮次中，孩子所购包装所含糖果数量必须严格大于前一轮次中孩子所购包装所含糖果数量（第一轮次除外：第一个孩子可任意选择包装）。随后，轮次继续传递给孩子 $i+1$；若当前是孩子 $n$ 的轮次，则下一轮次回到孩子 $1$。该过程可在任意时刻终止，但购买过程结束时，所有孩子必须拥有相同数量的糖果包装。当然，每个孩子在糖果上的总花费不能超过其零花钱。

你在这家糖果店工作，需要为孩子们提前备好糖果。请输出糖果店能售出的糖果总数的最大值。如果孩子们因零花钱不足而无法购买任何糖果，则输出 $0$。

The first line contains two space-separated integers n and m (2 ≤ n ≤ 2·105, 2 ≤ m ≤ 5·106, n ≤ m), denoting the number of kids and the maximum number of candies in a package sold by the candy shop, respectively.

Then n lines follow, each line will contain a single positive integer not exceeding denoting the allowance of a kid in rubles. The allowances are given in order from kid 1 to kid n.

Please, do not use the %lld specificator to read or write 64-bit integers in C++. It is recommended to use cin, cout streams (also you may use %I64d specificator).

第一行包含两个以空格分隔的整数 $n$ 和 $m$（$2 \leq n \leq 2\cdot10^5$，$2 \leq m \leq 5\cdot10^6$，$n \leq m$），分别表示儿童人数以及糖果店所售糖果包中糖果的最大数量。

接下来有 $n$ 行，每行包含一个不超过 的正整数，表示一名儿童的零花钱（单位：卢布）。零花钱按儿童 1 至儿童 $n$ 的顺序给出。

请注意，在 C++ 中读写 64 位整数时，请勿使用 %lld 格式说明符。建议使用 cin、cout 流（也可使用 %I64d 格式说明符）。

Print a single integer denoting the maximum number of candies that can be sold by the candy shop.

输出一个整数，表示糖果店最多可以售出的糖果数量。

For the first example, one of the scenarios that will result in 13 purchased candies is as follows.

• Turn 1. Kid 1 purchases 1 candy.
• Turn 2. Kid 2 purchases 3 candies.
• Turn 3. Kid 1 purchases 4 candies.
• Turn 4. Kid 2 purchases 5 candies.

对于第一个例子，一种将导致购买 13 颗糖果的情形如下：

• 第 1 轮：儿童 1 购买 1 颗糖果。
• 第 2 轮：儿童 2 购买 3 颗糖果。
• 第 3 轮：儿童 1 购买 4 颗糖果。
• 第 4 轮：儿童 2 购买 5 颗糖果。