#include <stdio.h>
#include <time.h>
#include <math.h>
#include <stdlib.h>
#include <string.h>
#include <map> 
#include <string>
#include <vector>  
#include <iostream> 
#include <sstream> 
#include <queue>
#include <algorithm>
#include <assert.h>
#include "kanapka.h"
#include "message.h"

using namespace std;
 
#define ll long long
#define PB 		push_back
#define FOR(a,start,end) 	for(int a=int(start); a<int(end); a++)
#define INF 		INT_MAX
#define SORT(a) 	sort(a.begin(),a.end()) 
#define CL(a,x) 		memset(a,x,sizeof(a))
#define REP(a,x)	for(int a=0;a<x;a++)
#define REP1(a,x)	for(int a=1;a<=x;a++)
#define MP 		make_pair

 
 
typedef vector<int>     vi;
typedef pair<int,int>     pii; 
typedef vector<string> vs;
typedef vector<pii> vii;
typedef vector<vector<int> > vvi;
typedef vector<vector<string> > vvs;
typedef vector<pair<string,string> > vss;
typedef pair<string,string> pss; 
typedef pair<int,pii> ppii;
typedef vector<ppii> vppii;
typedef vector<vector<pii> > vvii;
typedef vector<vvi> vvvi;


int n,z,k1;
ll i,j,k,a,b,d,a0,a1,a2,ip,np,po,ko,d0,ap,b0;
vector<ll> vk,va,vb,vc,vap,va2,vb2,vc2;

/*
int MyNodeId(void){

return 0;
}
int NumberOfNodes(void){

return 10;
}



static long long GetN_SmallSample() {
  return 7LL;
}

static long long GetTaste_SmallSample(long long i) {
  switch ((int)i) {
    case 0: return 10LL;
    case 1: return -2LL;
    case 2: return 5LL;
    case 3: return -4LL;
    case 4: return 3LL;
    case 5: return -5LL;
    case 6: return 1LL;
//    default: assert(0);
  }
}

static const long long M = 100000000;

static long long GetN_LargeSample() {
  return 2 * M + 2;
}

static long long GetTaste_LargeSample(long long i) {
  assert(i >= 0 && i < 2 * M + 2);
  if (i <= M) {
    if (i % 2 == 0) {
      return i;
    } else {
      return -i;
    }
  } else {
    i = 2 * M + 1 - i;
    if (i % 2 == 0) {
      return -i;
    } else {
      return i;
    }
  }
}

static int initialized = 0;
static long long (*GetN_ptr)();
static long long (*GetTaste_ptr)(long long);

static void Init() {
  int TID = 0;
  scanf("%d", &TID);
  assert(TID >= 1 && TID <= 2);
  if (TID == 1) {
    GetN_ptr = GetN_SmallSample;
    GetTaste_ptr = GetTaste_SmallSample;
  } else if (TID == 2) {
    GetN_ptr = GetN_LargeSample;
    GetTaste_ptr = GetTaste_LargeSample;
  }
  initialized = 1;
}
/*
#ifdef __cplusplus
extern "C" {
#endif
*/
/*
long long GetN() {
  if (!initialized) {
    Init();
  }
  return (*GetN_ptr)();
}

long long GetTaste(long long i) {
  if (!initialized) {
    Init();
  }
  return (*GetTaste_ptr)(i);
}
*/
int main() {  
	//freopen( "c:\\wojtek\\uva\\pa\\debug\\t1.in", "rt", stdin);  
	
	//pi=2*acos(0.0);
	 
	n=MyNodeId();
	z=NumberOfNodes();
	
	 k = GetN();
	 z=min((ll)z,k);
	 if(n>=k)
		 return 0;
	 b=k/z;
	 if(k%z>0)
		 b++;
	 b0=b;
	 if(n==z-1){
		 b=k-n*b0;
	 }
	 //ile przedziałów z każdej instancji
	 d0=1000000ll;
	 vap.assign(z,0ll);
	 if(b>d0){
		 np=b/d0;
		 if(b%d0>0)
			 np++;
	 }
	 else
		 np=1;
	 if(n>0){
		 
		 PutLL(0, np);
		  Send(0);
		  
	 }
	 else {
		  
		 vap[0]=np;
		for (int i0 = 1; i0 < z; i0++) {
			
			  Receive(i0);
			  vap[i0]=GetLL(i0);
			 
		}
		ap=0;
		for(int i0=0;i0<z;i0++){
			ap+=vap[i0];
		}
		va2.assign(ap,0ll);
		vb2.assign(ap,0ll);
		vc2.assign(ap,0ll);
		
	 }
//
	 for(ip=0;ip<np;ip++){
		 po=n*b0+ip*d0;
		 ko=min(n*b0+(ip+1)*d0,min((n+1)*b0,k));
	
		vk.clear();
		va.assign(ko-po,0ll);
		vb.assign(ko-po,0ll);
		for (i = po;i<ko; i++) {
			a=GetTaste(i);
			vk.push_back(a);
		}
		 k1=vk.size();
		va[0]=vk[0];
		vb[k1-1]=vk[k1-1];
	   for (i = 1;i<(ll)k1; i++) {
		   va[i]=va[i-1]+vk[i];
		   vb[k1-1-i]=vb[k1-i]+vk[k1-1-i];
	   }
	   a0=va[k1-1];
	   va[0]=max(va[0],0ll);
	   vb[k1-1]=max(vb[k1-1],0ll);
	   for (i = 1;i<(ll)k1; i++) {
		   va[i]=max(va[i-1],va[i]);
		   vb[k1-1-i]=max(vb[k1-i],vb[k1-1-i]);
	   }
	   a=0;
	  
	   d=0;
	   a1=0;
	   a2=0;
	   
		for (i = 0;i<(ll)k1; i++) {
			if(a+vb[i]>d){
				d=a+vb[i];
				a1=a;
				a2=vb[i];
			}
			a=va[i];
		}
		if(a>d){
			a1=a;
			a2=0ll;
		}
		
		 if (n > 0) {
			 
			   PutLL(0, a0);
			   PutLL(0, a1);
			   PutLL(0, a2);
				Send(0);
				
		 }
		 else {
			 va2[n*vap[0]+ip]=a1;
			 vb2[n*vap[0]+ip]=a2;
			 vc2[n*vap[0]+ip]=a0;
			
			for (int i0 = 1; i0 < z; i0++) {
				if(ip<vap[i0]){
					
					Receive(i0);
					  vc2[i0*vap[0]+ip]=GetLL(i0);
					  va2[i0*vap[0]+ip]=GetLL(i0);
						vb2[i0*vap[0]+ip]=GetLL(i0);
				
				//	  vc.push_back(GetLL(i0));
				//	  va.push_back(GetLL(i0));
				//	  vb.push_back(GetLL(i0));
					
				/*
					vc2[i0*vap[0]+ip]=i0;
					  va2[i0*vap[0]+ip]=i0;
						vb2[i0*vap[0]+ip]=i0;
					*/	
				}
			}
		 }
	 }

	 //koniec
	 if(n==0){
		d=0;
		a=0;
		b=0;
		a=0;
		for(i=1;i<ap;i++){
			a+=vc2[i-1];
			va2[i]=max(va2[i-1],a+va2[i]);
			va2[i]=max(0ll,va2[i]);
			b+=vc2[ap-i];
			vb2[ap-1-i]=max(vb2[ap-i],b+vb2[ap-1-i]);
			vb2[ap-1-i]=max(0ll,vb2[ap-1-i]);
		}
		d=0;
		for(int i=0;i<z;i++){
			for(int j=i;j<z;j++){
				if(va2[i]+vb2[j]>d){
					d=va2[i]+vb2[j];
				}
			}
		}
		d=max(0ll,d);
		cout<<d<<endl;
	 }
	




	
	//czas = clock() - czas;
	//printf("%lf\n",double(czas)/CLOCKS_PER_SEC);					
//}
			
	return 0;
	 
}