After experiencing so many events in the Blue Planet, Yunyan'd like to make a summary and write them all in his Abyss Log.

Yunyan wrote diary in a weird way. It's made up of many articles. Each article had n events, and it must be written with the order from the 1-st event to the n-th event.

He would wrote for m periods. For each period he would only wrote 1 specific kind of event for all the existing articles. In the 1-st period he wrote 1-st event for all the articles. In the next period he wrote the next kind of event. Specially, if in one day he's writing the n-th event, then in the next day he'd write the 1-st event again.

At first there's no article to write. At the beginning of the i-th period he'd get a_i new articles to write. At one period, he would write articles as much as possible. If one article can't be written at current period because the previous events aren't written, it will be hanged out until the previous events can be written in the future period. When all the events are written, the article is finished.

Please calculate how many pages he need within the m periods.

The first line contains two integer n,m(1\le n,m\le10^3) .

The second line contains m integers, the i-th integer is a_i(0\le a_i\le10^3) .

Output a single line with an integer denoting the total pages he used.

Here're what happened in the first example:

In the 1st period the 1st article appears, he writes the 1st event of the 1st article, 1 page is used;

In the 2nd period the 2nd article appears, 2nd article can't be written, he writes the 2nd event of the 1st article, 1 page is used;

In the 3rd period the 3rd, 4th, 5th, 6th article appear, all articles from 2nd to 6th can't be written, he writes the 3rd event of the 1st article, and 1st article is finished, 1 page is used;

In the 4th period, the 7th, 8th, 9th, 10th, 11st article appear, he writes the 1st event of all the article from 2nd to 11st, 10 pages is used;

In the 5th period, the 12nd article appears, 12nd article can't be written, he writes the 2nd event of all the article from 2nd to 11st, 10 pages is used;

In the 6th period, the 13rd, 14th, 15th, 16th article appear, all articles from 12nd to 16th can't be written, he writes the 3rd event of all the article from 2nd to 11st, and all of them is finished, 10 pages is used;

So he used 33 pages in total.