题目描述

由于机房fake风气日愈严重，小P决定对这种行为进行制裁。他抓来了 $n$ 个壮丁，让他们在机房发生fake行为时对正在fake的人进行制♂裁。

这些壮丁会以轮流的方式决定由谁来进行制裁，例如第一次会由第一个壮丁来执行，第二次会由第二个壮丁来执行，第 $n$ 次会由第 $n$ 个壮丁来执行，而第 $n+1$ 次又会由第一个壮丁来执行。同时，为了保证公平，他们最后一次进行制裁一定是由第 $n$ 个壮丁来执行的。也就是说，他们进行制裁的总次数一定是 $n$ 的倍数。

如果壮丁决定对一个fake事件进行制裁，那么参与这个fake事件的所有人都会被制裁。但是由于壮丁的体力问题，第 $i$ 个壮丁最多只能制裁 $a_i$ 个人。现在他们知道，接下来会按时间顺序发生 $m$ 次fake事件，第 $i$ 次事件会有 $i$ 个人在fake。为了不让小P失望，他们会从这 $m$ 次事件中挑选一些来进行制裁，在保证轮流以及考虑到每个人体力问题的情况下，最大化被制裁的总人数。

输入格式

第一行两个整数 $n$ 和 $m$ ，分别表示壮丁的个数和fake事件的次数。

第二行 $n$ 个整数，其中第 $i$ 个整数 $a_i$ 表示第 $i$ 个壮丁最多只能制裁 $a_i$ 个人。

输出格式

输出一行一个整数，表示最多能制裁的人数。

样例输入

2 6
6 15

样例输出

16

样例解释

壮丁们会对第 $1,4,5,6$ 次事件进行制裁，其中第 $1$ 个壮丁制裁了 $1+5=6$ 个人，第 $2$ 个壮丁制裁了 $4+6=10$ 个人。

限制与约定

对于所有数据，保证 $1 \le n \leq 2 \times 10^5,1 \leq m \le 10^9,1 \leq a_i \leq \frac{m(m+1)}{2}$。

$subtask1(10pts):m \leq 20$；

$subtask2(10pts):m \leq 2000$；

$subtask3(20pts):n=2 \times 10^5,m \leq 2 \times 10^6$；

$subtask4(20pts):n \leq 2 \times 10^5,m \leq 2 \times 10^6$；

$subtask5(10pts):n \leq 2 \times 10^5,m \leq 3 \times 10^7$；

$subtask6(30pts):$ 无特殊限制。