一年一度的運動會即將開幕了,身為主辦者的咪口,為了增加比賽過程的趣 味性與刺激性,今年新增了趣味項目「一二三木頭人」。 「一二三木頭人」規則大致如下所述:由一個人當鬼面對牆壁,其他玩家站 在遠處的起點,玩家的目標是朝牆壁前進並觸碰到鬼;鬼可以藉由大聲喊出「一 二三木頭人」並在其之後進行「回頭」阻止玩家前進,當鬼「回頭」時玩家不能 進行任何移動,若被鬼發現玩家在「回頭」期間移動,則該名玩家需要退回起點 重新開始;最先碰到鬼的玩家獲勝。為了避免鬼過於頻繁或長時間「回頭」導致 玩家方難度過高,鬼對於「回頭」有以下兩項限制:
(1) 除第一次「回頭」之外,必須與上一次結束「回頭」間隔至少某一特定 時間才能再次「回頭」
(2) 每次「回頭」的時長不能超過某一特定時間 運動會是紅隊與白隊互相對抗的競賽,所以遊戲中鬼的角色自然是由主辦 者的咪口擔任,對於自稱菁英的咪口來說,希望在競賽時盡可能使玩家們退回 起點的次數越多越好,以此向大家展現自己菁英般的實力。
為此咪口在運動會的準備期間仔細觀察了所有參與項目選手們賽前練習時 的動作與習慣,得出了玩家們在某一時刻移動可能性的序列,移動可能性越高 代表若該時刻處於「回頭」期間使玩家退回起點的可能性越高。只要符合前述 「回頭」的規則,咪口可以在任何她想要的時刻進行「回頭」,亦可決定每次 「回頭」的時長,為了達成她菁英般的目的,咪口依照先前調查得出的移動可 能性序列來制定「回頭」的時機與時長,並且將所有「回頭」期間所對應到的 移動可能性的總和稱作整體退回程度,最終咪口希望整體退回程度越大越好, 身為咪口粉絲的你決定悄悄幫助咪口進行安排,使得咪口在大眾之下不失菁英 風範。
第一行輸入三個正整數 N (1 ≤ N ≤ 4×10^6 )、K (1 ≤ K ≤ N)、T (1 ≤ T ≤ N),分 別表示競賽共歷時 N 個時刻、除第一次「回頭」之外與上一次結束「回頭」至少 須間隔 K 個時刻、每次「回頭」時長不能超過 T 個時刻。 接下來一行包含 N 個非負整數 mi (0 ≤ mi ≤ 10^9 ),依序代表在第 i 時刻玩家們 的移動可能性。
輸出僅包含一個整數,代表在符合「一二三木頭人」的規則之下,在咪口能 夠安排的所有可能的「回頭」時機與時長之中最大的整體退回程度。
3 1 1 3 3 2
5
7 2 2 3 1 3 3 2 1 1
8
範例 1 說明: 所有符合規則的安排如下: (同個中括號內代表同一次「回頭」)
1. 在 [1] 時刻「回頭」→ 整體退回程度 = 3。
2. 在 [2] 時刻「回頭」→ 整體退回程度 = 3。
3. 在 [3] 時刻「回頭」→ 整體退回程度 = 2。
4. 在 [1], [3] 時刻「回頭」→ 整體退回程度 = 3+2 = 5。 故最大的整體退回程度為 5,故輸出 5。(注意不能安排在 [1, 2] 時刻「回 頭」,因為這樣違反「回頭」時長不超過 1 個時刻的限制)
範例 2 說明: 所有符合規則的安排中使得整體退回程度最大化的安排如下: 在 [1], [4, 5] 時刻「回頭」→ 整體退回程度 = 3+3+2 = 8。 最大的整體退回程度為 8,故輸出 8。(注意不能安排在 [1], [3, 4], [7] 時刻 「回頭」,因為這樣第二次「回頭」違反與上一次結束「回頭」須至少間隔 2 個時刻的限制)