農(nóng)夫約翰是一個(gè)精明的會(huì)計(jì)師。他意識(shí)到自己可能沒(méi)有足夠的錢來(lái)維持農(nóng)場(chǎng)的運(yùn)轉(zhuǎn)了。他計(jì)算出并記錄下了接下來(lái) N (1 ≤ N ≤ 100,000) 天里每天需要的開(kāi)銷。

約翰打算為連續(xù)的M (1 ≤ M ≤ N) 個(gè)財(cái)政周期創(chuàng)建預(yù)算案，他把一個(gè)財(cái)政周期命名為fajo月。每個(gè)fajo月包含一天或連續(xù)的多天，每天被恰好包含在一個(gè)fajo月里。

約翰的目標(biāo)是合理安排每個(gè)fajo月包含的天數(shù)，使得開(kāi)銷最多的fajo月的開(kāi)銷盡可能少。

第一行包含兩個(gè)整數(shù)N,M，用單個(gè)空格隔開(kāi)。

接下來(lái)N行，每行包含一個(gè)1到10000之間的整數(shù)，按順序給出接下來(lái)N天里每天的開(kāi)銷。

零基礎(chǔ)同學(xué)可以先學(xué)習(xí)視頻課程，包含C/C++、Python、百練、藍(lán)橋杯輔導(dǎo)、算法數(shù)據(jù)結(jié)構(gòu)等課程，提供視頻講解以及配套習(xí)題，還有老師答疑，點(diǎn)擊這里了解課程詳情

信息學(xué)一本通 動(dòng)態(tài)規(guī)劃 分治