Misha installed a new game "Memtest 2k17" on his phone. It provides daily rewards for visiting. Rewards come in n levels. The type of reward depends on the reward for the previous day, namely:
if the player did not visit the game the previous day, then for today's visit he will receive a level 1 reward;
if a player entered the game the previous day and received a level k reward ( k ≠ n ), then for today's visit he will receive a level k reward + 1 ;
if a player entered the game the previous day and received a level n reward, then for today's visit he will receive a level 1 reward.
At the Forum for Cool Programmers, Misha found out that the rewards of each of the levels are respectively a 1 , a 2 , ..., a n gold coins.
In m days, there will be a Memtest 2k17 tournament, for which Misha wants to collect as many gold coins as possible. Help him plan visits to the game during the m days left before the tournament. Find the most gold coins he can get from daily rewards during this period. We can assume that the game was installed on the first of these m days, that is, Misha has never logged into it before.
Input
The first line of the input contains natural numbers n and m ( 1 ≤ n , m ≤ 1000 ) — number of reward levels and days before the tournament.
The second line of the input contains n integers a 1 , a 2 , ..., a n ( 1 ≤ a i ≤ 1000 ), where a i — the value of the i-th level reward in gold coins.
Imprint
Print one natural number — the most gold coins that Misha can get before the tournament.
Note
In the first test from the example, it is profitable for Misha to enter the game every day. Then he will get 1 + 2 + 4 = 7 gold coins.
In the second test from the example, it is profitable for Misha to enter the game on the first and third days, receiving 4 coins on each of them, then he will receive 8 coins in total.
Examples
| # |
Input |
Output |
| 1 |
3 3
1 2 4
| 7 |
| 2 |
3 3
4 2 1
| 8 |