TopCoder

Thumb   5
Y(OwO)Y
真実より 優しい嘘をプリーズ

User's AC Ratio

92.6% (25/27)

Submission's AC Ratio

27.8% (37/133)

Tags

Description

修羅少年在魔獸帳號被砍掉之後的晚上做了一個夢:

修羅少年又夢到了自己登入了魔獸世界,他在艾爾文森林的林間小徑走著走著,在地上看到了一個閃閃發亮的物品,
正當他要拿起採礦錘去採礦的時候,他忽然發現其實那是一個錢包!打開之後裡面竟然有5000G!這可以讓他在8591賺一筆了!

心情暢快不少的修羅少年又繼續在林間小徑走著,看到地上又出現了一個錢包!原來這是一條錢包的路。

是說這條傳說中的錢包的路是一條直線道路,修羅少年一登入時在道路的最左端(第一個錢包的位置),
每隔100碼的距離地上就會有一個錢包,每個錢包中有一定量的錢,然而這些錢包都是魔法錢包,
拿完錢後你不能把錢包拿走(不然錢包會把你吸進去),而要放在原地,當一個錢包的錢被拿走後,
由於魔法的力量會在固定的時間後恢復最初的金錢,經過修羅少年的實驗,對每個錢包,要花他不停頓地走200碼的時間才能復原。

雖然修羅少年不愛一百萬只愛台灣,不過他還是很好奇他可以在遊戲點數用完之前能夠拿到多少錢
(以修羅少年的腳程他不停頓地每走100碼的時間就要耗掉1點的遊戲點數,並且撿錢的時間極端可以忽略),
請你寫個程式幫他解決這個難題吧!

Input Format

第一行有兩個正整數N,K (N, K <= 1,000,000 ),代表錢包的路有N個錢包,且修羅少年的點數還有K點。

第二行有N個正整數ai (ai <=1,000,000),表示由左至右的錢包中有多少金幣。

Output Format

輸出一個整數,代表修羅少年最多可得到多少金幣。

Sample Input

5 4
3 4 3 5 1

Sample Output

18

Hints

修羅少年的走法:1-2-3-4-3,總共得到3+4+3+5+3=18的金幣

Problem Source

原TIOJ1636 / Problem Setter: DarkBtf

Subtasks

For Testdata: 0 ~ 0, Score: 9
For Testdata: 1 ~ 1, Score: 9
For Testdata: 2 ~ 2, Score: 9
For Testdata: 3 ~ 3, Score: 9
For Testdata: 4 ~ 4, Score: 9
For Testdata: 5 ~ 5, Score: 9
For Testdata: 6 ~ 6, Score: 9
For Testdata: 7 ~ 7, Score: 9
For Testdata: 8 ~ 8, Score: 9
For Testdata: 9 ~ 9, Score: 9
For Testdata: 10 ~ 10, Score: 10
No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB)
0 10000 65536 65536
1 10000 65536 65536
2 10000 65536 65536
3 10000 65536 65536
4 10000 65536 65536
5 10000 65536 65536
6 10000 65536 65536
7 10000 65536 65536
8 10000 65536 65536
9 10000 65536 65536
10 10000 65536 65536