405188: GYM101821 C Eat And Walk

Eugene works at Yandex as a data scientist. Recently he decided to rest for a while so he took vacation and went to a wonderful education center on the shore of the Black sea where he teaches machine learning and data analysis to high school students.

Every evening he goes to the shore where n nice restaurants are located. Restaurants are numbered with consecutive integers 1, 2, ..., n, the i-th restaurant is located at position i. Eugene starts at position 0 and with e units of energy. Initially his stomach is empty and it takes him only one unit of energy to change his position by 1 (for example, to go from position 0 to position 1 where restaurant 1 is located). The evening will proceed as follows.

1. If at some moment of time Eugene is located at position i and he already ate x units of food during this evening, he can move to positions i - 1 or i + 1 by spending x + 1 units of energy.
2. If he is now at position i between 1 and n inclusive and he hasn't visited restaurant i during this evening, he can choose to go there. He knows that will result him eating exactly a_i units of food. This action is free in terms of units of energy (chewing is not counted).
3. If at some moment of time Eugene is at position 0 he may choose to stop at go back to educational center. This won't cost him any units of energy.

As Eugene does machine learning and all the stuff it is up to you to compute, what is the maximum number of units of food he can eat during this evening and return to educational center at position 0 if he behaves optimal?

The first line of the input contains two integers n and e (1 ≤ n ≤ 200, 000, 1 ≤ e ≤ 10⁷) — the number of restaurants along the shore and the initial amount of Eugene's energy.

The second line contains n integers a₁, a₂, ..., a_n (0 ≤ a_i ≤ 1 000 000), the i-th of them denoting the exact number of units of food Eugene will eat if he chooses to visit restaurant i.

Print one integer equal to the maximum possible number of units of food Eugene can eat this evening.

5 100
1 1 1 1 1

5

4 25
3 30 1 3

6

In the first sample Eugene has a lot of energy, so he just walks from position 0 to position 5 visiting every restaurant on his path. The he goes back to education center at position 0.

In the second sample Eugene should first go to the 4-th restaurant, then visit restaurant 1 and finally go back to position 0.