修羅少年在魔獸帳號被砍掉之後的晚上做了一個夢:
修羅少年又夢到了自己登入了魔獸世界,他在艾爾文森林的林間小徑走著走著,在地上看到了一個閃閃發亮的物品,
正當他要拿起採礦錘去採礦的時候,他忽然發現其實那是一個錢包!打開之後裡面竟然有 5000G!這可以讓他在 8591 賺一筆了!
心情暢快不少的修羅少年又繼續在林間小徑走著,看到地上又出現了一個錢包!原來這是一條錢包的路。
是說這條傳說中的錢包的路是一條直線道路,修羅少年一登入時在道路的最左端(第一個錢包的位置),
每隔 100 碼的距離地上就會有一個錢包,每個錢包中有一定量的錢,然而這些錢包都是魔法錢包,
拿完錢後你不能把錢包拿走(不然錢包會把你吸進去),而要放在原地,當一個錢包的錢被拿走後,
由於魔法的力量會在固定的時間後恢復最初的金錢,經過修羅少年的實驗,對每個錢包,要花他不停頓地走 200 碼的時間才能復原。
雖然修羅少年不愛一百萬只愛台灣,不過他還是很好奇他可以在遊戲點數用完之前能夠拿到多少錢
(以修羅少年的腳程他不停頓地每走 100 碼的時間就要耗掉 1 點的遊戲點數,並且撿錢的時間極端可以忽略),
請你寫個程式幫他解決這個難題吧!
第一行有兩個正整數 $N, K$($N, K \leq 10 ^ 6$),代表錢包的路有 $N$ 個錢包,且修羅少年的點數還有 $K$ 點。
第二行有 $N$ 個正整數 $a_i$($a_i \leq 10 ^ 6$),表示由左至右的錢包中有多少金幣。
輸出一個整數,代表修羅少年最多可得到多少金幣。
修羅少年的走法:1-2-3-4-3,總共得到3+4+3+5+3=18的金幣
原TIOJ1636 / Problem Setter: DarkBtf
2021.02.15 Update: Added $\LaTeX$ by FHVirus
No. | Testdata Range | Score |
---|---|---|
1 | 0 | 9 |
2 | 1 | 9 |
3 | 2 | 9 |
4 | 3 | 9 |
5 | 4 | 9 |
6 | 5 | 9 |
7 | 6 | 9 |
8 | 7 | 9 |
9 | 8 | 9 |
10 | 9 | 9 |
11 | 10 | 10 |