TOI練習賽 2020m6a2-蛋糕(Cake)    原題連結

小明過生日，家人為他準備一個長方型的水果蛋糕，由於他是壽星，他可以先切蛋糕去吃。這個蛋糕分成 N 小塊，每塊都有一種餡料。
小明對每種餡料有不同的喜好度，喜好度數值若為正值代表喜歡，負值代表厭惡，零值為沒有感覺。 為了省時間，小明只挑連續一段蛋糕來吃，
這樣就只要切一刀或兩刀。而且，為了讓其它人也能吃到蛋糕，他「至多」只會挑 K小塊的份量吃，（可以不拿滿 K小塊分量的蛋糕，甚至是不拿）。
舉例而言：假如 N=7、K=3，每小塊蛋糕小明 給的喜好度評分如下： 3 7 -1 9 2 2 1
拿到[7, -1, 9]這三塊蛋糕的總分最高，為 15分，縱使中間的他不喜歡吃 也沒關係。雖然[9, 2, 2]這段蛋糕他全部都喜歡，不過總分只有 13分。
請你寫一個程式計算出小明能吃到的蛋糕最高總分為多少分。

範例說明 2：由於無論怎麼拿小明都不喜歡，所以乾脆不拿，輸出 0。
評分說明
此題目測資分成四組，每組測資有多筆測試資料，需答對該組所有測試資料 才能獲得該組分數，各組詳細限制如下。
第一組 (20 分)： 1<=N<=10^2，K=1
第二組 (20 分)： 1<=N<=10^2
第三組 (10 分)： 1<=N<=3 ×10^3
第四組 (50 分)： 無特別限制