送福利啦 图的最短路 边为有向的，无向自己改一下

//**spfa算法 
#include<bits/stdc++.h>
using namespace std;
const int N=1010;
int cnt=0,head[N],dist[N],n,m;
struct stu{
	int nxt,to,w;
}e[N];
bool vis[N];
void add(int u,int v,int w){
	e[++cnt].to=v;
	e[cnt].w=w;
	e[cnt].nxt=head[u];
	head[u]=cnt;
}
priority_queue<int>q;
void spfa(){
	q.push(1);
	dist[1]=0;
	while(!q.empty()){
		int u=q.top();
		q.pop();
		for(int i=head[u];i;i=e[i].nxt){
			if(dist[u]+e[i].w<dist[e[i].to]){
				dist[e[i].to]=dist[u]+e[i].w;
				q.push(e[i].to);
			}
		}
	}	
}
int main() {
	memset(dist,0x3f3f3f,sizeof(dist));
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;i++){
		int a,b,c;
		scanf("%d%d%d",&a,&b,&c);
		add(a,b,c);/
	}
	spfa();
	for(int i=1;i<=n;i++) cout<<dist[i]<<" ";
	return 0;
}



//**floyd算法 
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
int n,m,dp[N][N];
void floyd(){
	for(int k=1;k<=n;k++){
		for(int i=1;i<=n;i++){
			for(int j=1;j<=n;j++){
				if(dp[i][j]>dp[i][k]+dp[k][j])
				dp[i][j]=dp[i][k]+dp[k][j];
			}
		}
	}
}
int main(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++){
		int a,b,c;
		scanf("%d%d%d",&a,&b,&c);
		dp[a][b]=c;
	}
	printf("%d",dp[n][m]);
	return 0;
}

#include<iostream>
#include<vector>
using namespace std;
struct Thing//¶¨ÒåÒ»¸öÎïÆ·½á¹¹Ìå°üÀ¨ÎïÆ·ÊôÐÔÌå»ýºÍ¼ÛÖµ 
{
	int vi;
	int wi;
};
/*¶¨ÒåÒÔÏÂÈ«¾Ö±äÁ¿*/ 
vector< vector<int> >tree;//¶¨ÒåÒ»¸ö¶þάÊý×é´æ´¢¸÷¸ö½ÚµãµÄ×Ó½ÚµãÐÅÏ¢ 
vector<Thing>things; //¶¨ÒåÎïÆ·Êý×é´æ´¢ÎïÆ·µÄÐÅÏ¢ 
int N,V;//¶¨ÒåÎïÆ·µÄÊýÁ¿ºÍ±³°üµÄÌå»ý 
int ans[110][110]; //¶¨Òå¶þάÊý×é´æ´¢´ð°¸ans[i][j]±íʾÔÚÑ¡½ÚµãiÇÒÌå»ý²»³¬¹ýjµÄÇ°ÌáÏÂËùÄܵõ½µÄ×î´ó¼ÛÖµ 
void dfs(int Node)
{/*´Ëº¯ÊýµÄ¹¦ÄÜÊÇÔڵõ½Ò»¸ö½ÚµãºóÎÒÃÇÒª°ÑÔÚÑ¡Õâ¸ö½ÚµãµÄÇé¿öÏÂ
   µÄÿһÌå»ýϵÄ×î´óÖµ¶¼Çó³öÀ´²¢´æÈëansÊý×éÖÐ */
	if(things[Node].vi <= V)//ÏÈÅжϱ³°üÄÜ·ñ·Åϸýڵã´ú±íµÄÎïÆ·Èç¹û¿ÉÒÔÔò½øÈëÅÐ¶Ï 
	{
		if(tree[Node].size()==0||things[Node].vi == V)
    	{/*ÅжÏÈç¹û¸Ã½ÚµãûÓÐ×Ó½Úµã»òÆä´ú±íµÄÎïÆ·Ìå»ýÇ¡ºÃµÈÓÚ±³°üÌå»ý
		   ÔÚÕâÁ½ÖÖÇé¿ö϶¼²»±ØÔÙÈ¥¿¼ÂǸýڵãµÄ×Ó½ÚµãÔõôѡÔñÖ±½Ó¸³Öµ*/ 
    		for(int i=things[Node].vi;i<=V;i++)
    		{/*½«´óÓÚ»òµÈÓÚ¸ÃÎïÆ·µÄ¸÷¸öÌå»ýÈ«¸³Îª¸ÃÎïÆ·µÄ¼ÛÖµ
			   ²¢½«ÆäËûÌå»ýÈ«¸³ÖµÎª0ÕâÀïÒòΪansΪȫ¾Ö±äÁ¿ËùÒÔ
			   ¸÷µã±¾Éí¾ÍÒÔ¸³³õֵΪ0ÔÚÕâÀï¾Í²»ÔÙ½øÐÐÕâÒ»²Ù×÷*/
    			ans[Node][i]=things[Node].wi;
    		}	
    	}
    	else//·ñÔòÎÒÃÇÐèÒª¿¼ÂÇÆä×Ó½ÚµãµÄÑ¡ÔñÇé¿ö 
    	{
    		for(int k=0;k<tree[Node].size();k++)//ÎÒÃÇÒª±éÀú¸÷¸ö×Ó½Úµã 
    		{
				dfs(tree[Node][k]);//Ê×ÏÈÎÒÃÇÇó³öÑ¡Õâ¸ö×Ó½ÚµãµÄÇé¿öϸ÷Ìå»ýϵÄ×îÓŽâ 
    			for(int i=V-things[Node].vi;i>=0;i--)
    			{/*ÎÒÃÇ¿ªÊ¼ÇóÑ¡µ±Ç°½ÚµãµÄÇé¿öϸ÷Ìå»ýϵÄ×îÓŽâ
				   ÎÒÃǵÄÌå»ý´ÓV-things[Node].vi¿ªÊ¼µ½0ÒòΪÎÒÃÇ
				   È·¶¨ÁËÑ¡µ±Ç°ÎïÆ·ËùÒÔҪΪËûÁô³ö¿Õ¼ä£¬Ìå»ý´Ó´ó
				   µ½Ð¡ÊÇÒòΪºÍ01±³°üÒ»Ñù×Ó½ÚµãµÄÿÖÖÌå»ýÖÁ¶à¿ÉÒÔÑ¡Ò»±é*/
    				for(int j=0;j<=i;j++)//µ±Ç°0µ½iÕâ¸ö·¶Î§¾ÍÊÇÕâ¸ö×Ó½ÚµãÒÔÏÂËùÄÜÕ¼ÓõÄÌå»ýÎÒÃÇÒª´ÓÕâЩÌå»ýÖÐÑ¡³ö×îÓŵÄÄǸöÌå»ý 
    					ans[Node][i] = max(ans[Node][i],ans[Node][i-j]+ans[tree[Node][k]][j]);
						/*״̬תÒÆÎÒÃÇÒªÓÃÔÚ²»Ñ¡¡¢ÒÔ¼°·Ö±ð´ÓÕâ¸ö×Ó½ÚµãÒÔÏÂÑ¡×ÜÌå»ýΪ1¡¢2¡­¡­iµÄÎïÆ·ÖÐ
						  Ñ¡ÔñÒ»¸ö×î¼Ñ¾ö²ß£¬¼´±È½Ïµ±Ç°¼ÛÖµºÍÑ¡²»Í¬Ìå»ýϵļÛÖµ·Ö±ð×÷±È½Ï*/
    			}
    		}
    		for(int i=V;i>=things[Node].vi;i--)//×îºóÎÒÃÇÒª½«ÎÒÃǵĸù½ÚµãµÄ¼ÛÖµ¼ÓÈë¼´¿ªÊ¼ÎÒÃÇΪ֮¿Õ³öµÄÌå»ý 
    		{//ÔÚÕâ¸öÌå»ýÒÔÉϵÄÈ«²¿¼ÓÉÏÕâ¸ö½Úµã´ú±íµÄÎïÆ·µÄ¼ÛÖµ 
    			ans[Node][i] = ans[Node][i-things[Node].vi] + things[Node].wi;
    		}
    		for(int i = 0;i < things[Node].vi;i++ )
			{/*Õâ¸öÌå»ýÒÔϵĴú±íÕâ¸ö½Úµã²»ÄÜÑ¡Õâ¸ö½Úµã²»ÄÜÑ¡ÄÇôËûËùÓеÄ×Ó½ÚµãÒ²²»ÄÜÑ¡ËùÒÔÈ«²¿¸³³õֵΪ0
			   ÕâÀïÐèÒª¸³ÖµÊÇÒòΪÎÒÃÇÔÚÉÏÃæµÄÇó´óÌå»ý×îÓŽâµÄʱºòÓõ½ÁËÕâ¿éÌå»ýÎÒÃÇÒѾ­ÎªËûÃǸ³ÉÏÖµÁË
			   ËüÃÇÒѾ­²»ÊÇ0ÁËËùÒÔÕâÀïµÄ¸³0²»ÄÜÊ¡*/
				ans[Node][i]=0;
			}
    	}
	}
}
int main()
{
	int root;      //¶¨ÒåÒ»¸ö±äÁ¿Ò»»á´¢´æ¸ù½Úµã 
	cin>>N>>V;     //ÊäÈëÎïÆ·ÊýºÍ±³°üÌå»ý 
	tree.resize(N);//¿ª±Ù¿Õ¼äÒ»¸öÊý×é´¢´æ¸÷½ÚµãµÄ×Ó½ÚµãÐÅÏ¢´Ó¶ø´¢´æÕû¿ÃÊ÷µÄ½áµã¹Øϵ 
	for(int i=0;i<N;i++)//±éÀúÊäÈëÎïÆ·ÐÅÏ¢ 
	{
		int v,w,f;
		cin>>v>>w>>f;
		things.push_back({v,w});//½«ÎïÆ·ÐÅÏ¢·ÅÈëÎïÆ·Êý×éthings 
		if(f==-1)//¼ì²é¸Ã½ÚµãµÄ¸¸½ÚµãÊÇÄÄÒ»¸öÈç¹ûËüÊǸ¸½ÚµãÔò¼Ç¼Ëü 
		{
			root=i;
		}
		else//Èç¹û²»ÊǸ¸½ÚµãÔÚÔÚÆ丸½Úµã´ú±íµÄһάÊý×éÖдæÈë¸Ã½Úµã 
		{
			tree[f-1].push_back(i);//ÎÒÃǵĽڵãϱê´Ó0µ½n-1ÊäÈëµÄ¸¸½ÚµãÊÇ1µ½nËùÒÔÈÃÊäÈëµÄf¼õÈ¥1¼´ÎÒÃÇÒªÕҵĸ¸½Úµã 
		}
	}
	dfs(root);//´Ó¸ù½Úµãµ÷Óõݹ麯Êý 
	cout<<ans[root][V]<<endl;//Êä³ö×îÖÕ½á¹û 
	return 0;
} 

//https://zhuanlan.zhihu.com/p/648341058

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+10;
int n,m,a[N],dp[N];
int main() {
	scanf("%d%d",&n,&m);
	for(int i=1; i<=n; i++) scanf("%d",&a[i]);
	int sum=INT_MIN;
	for(int i=1;i<=n-m+1;i++){
		int ans=0;
		for(int j=i;j<=m+i-1;j++){
			dp[j]=max(a[j],dp[j-1]+a[j]);
			ans=max(ans,dp[j]);
			sum=max(sum,ans);
		}
	}
	cout<<sum;
	return 0;
}