Score : 800 points
Takahashi Lake has a perimeter of L. On the circumference of the lake, there is a residence of the lake's owner, Takahashi. Each point on the circumference of the lake has a coordinate between 0 and L (including 0 but not L), which is the distance from the Takahashi's residence, measured counter-clockwise.
There are N trees around the lake; the coordinate of the i-th tree is X_i. There is no tree at coordinate 0, the location of Takahashi's residence.
Starting at his residence, Takahashi will repeat the following action:
Find the longest possible total distance Takahashi walks during the process.
A partial score can be obtained in this problem:
Input is given from Standard Input in the following format:
L N X_1 : X_N
Print the longest possible total distance Takahashi walks during the process.
10 3 2 7 9
15
Takahashi walks the distance of 15 if the process goes as follows:
10 6 1 2 3 6 7 9
27
314159265 7 21662711 77271666 89022761 156626166 160332356 166902656 298992265
1204124749