XYZ is a stingy employer who wants to maximize his profits by minimizing the salaries of his employees. Now he has to give appraisal to his employees based on their performance rating. Higher the performance rating higher the salary. The appraisal to be given for each employee should be a multiple of n. Assume that each employee knows the performance rating of his neighbour only. That is, i th employee knows the performance rating of i-1 and i+1. (The first and last employees are not considered as neighbours). So if the performance rating of the i-1 th employee or the i+1th employee is less than the ith then, their salary should be less than i's by at least n and vice versa.

Given N employees, their performance rating (P[N]) and the multiple n, find out the minimum total expenditure for the employer.

Input

The first line contains the multiple n (0 <= n <= 150). The second line contains the number of employees N following which is the performance rating of N employees. (0 <= N <= 60000)

Output

The minimum expenditure.

Example

Input:
10
4
1
4
6
2

Output:
70

Input:
50
10
4
8
13
21
15
1
13
67
8
94

Output:
1050

Explanation

1. The appraisal for each person would be 10, 20, 30, 10 respectively.
2. The appraisal for each person would be 50, 100, 150, 200, 100, 50, 100, 150, 50, 100 respectively.