Background

为了构建鼠类命运共同体

高贵的土拨鼠与愚蠢的人类展开了新一轮的征战.

Description

愚蠢的人类向我们发起了进攻, 毫无疑问, 进攻软弱的像一坨屎.

我们的防御圈可以看作是一个周长为$c$的圆, 在圆上有$n$个火力输出点.

从圆上某一个位置出发, 在行走$a_i$距离后, 会有一个火力点$i$.

$a_i$表示从出发点到$i$点的距离

现在你可以从圆上任意一点出发, 请问你能否找到一条最短的路径, 使得每个节点都访问一次? 这个最短的路径是多少.

Format

Input

第1行两个整数$c, n$, $c$表示圆的周长, $n$表示节点个数

第2行输入$n$个整数$a_i$, 表示你从某一点出发后, 遇到的每个火力点距离你出发点的位置.

注意: 顺序有可能混乱

Output

输出一个整数, 表示你可以访问的最短路径

Samples

20 3
10 15 5

10

样例解释

你可以选则从3点出发, 走到1点, 再走到2点, 一共经历10的路程

Limitation

$2 <= c <= 10^9$

$2 <= n <= 2*10^5$

$(0 <= a_i < c)$