#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cctype>
#define maxn 100005
#define LL long long
using namespace std;
/*

dp[i][a][b][0] = max(dp[i-1][a][b][0] , dp[i-1][a-1][b][0] + A[i]);
dp[i][a][b][1] = max(dp[i-1][a][b][1] + A[i] , dp[i-1][a][b-1][1] 
, dp[i-1][a][b][0] + A[i] , dp[i-1][a][b-1][0]);
dp[i][a][b][2] = max(dp[i-1][a][b][2] , dp[i-1][a-1][b][2] + A[i]
, dp[i-1][a][b][1] , dp[i-1][a-1][b][1] + A[i])
acquiesce length >= 1
*/

int n,k,A[maxn];
LL dp[2][12][12][3];
int g[2][12][12][3][2],c1[maxn],c2[maxn],cc1,cc2;
inline void check(LL &a,LL b,int g1[2],int g2[2],int add)
{ 
	if(a <= b)
	{
		g1[0] = g2[0] , g1[1] = g2[1];
		a = b;
		if(add != -1)
		{
			if(g1[0] == -1) g1[0] = add;
			else g1[1] = add;
		}
	}
}

inline bool cmp1(const int &u,const int &v){ return A[u] < A[v]; }
inline bool cmp2(const int &u,const int &v){ return A[u] > A[v]; }
inline bool cmp3(const int &u,const int &v){ return u > v; }

int main()
{
	scanf("%d%d",&n,&k);
	for(int i=1;i<=n;i++) scanf("%d",&A[i]);
		
	int now=1,pre=0;
	memset(dp[pre],-0x3f,sizeof dp[pre]);
	memset(g,-1,sizeof g);
	dp[pre][0][0][0] = 0;
	for(int i=1;i<=n+1;i++,swap(now,pre))
	{
		memset(dp[now],-0x3f,sizeof dp[now]);
		memset(g[now],-1,sizeof g[now]);
		for(int a=0;a<=k;a++)
			for(int b=0;b<=k;b++)
				{
					check(dp[now][a][b][0] , dp[pre][a][b][0] , g[now][a][b][0] , g[pre][a][b][0] , -1);
					if(i<=n)check(dp[now][a+1][b][0] , dp[pre][a][b][0] + A[i] , 
					g[now][a+1][b][0] , g[pre][a][b][0] , -1);
					check(dp[now][a][b][1] , dp[pre][a][b][1]+A[i] , g[now][a][b][1] , g[pre][a][b][1] , -1);
					if(i<=n)check(dp[now][a][b+1][1] , dp[pre][a][b][1] , g[now][a][b+1][1] , g[pre][a][b][1] , -1);
					check(dp[now][a][b][1] , dp[pre][a][b][0] + A[i] , g[now][a][b][1] , g[pre][a][b][0] , i);
					if(i<=n)check(dp[now][a][b+1][1] , dp[pre][a][b][0] , g[now][a][b+1][1] , g[pre][a][b][0] , i);
					check(dp[now][a][b][2] , dp[pre][a][b][2] , g[now][a][b][2] , g[pre][a][b][2] , -1);
					if(i<=n)check(dp[now][a+1][b][2] , dp[pre][a][b][2] + A[i] , g[now][a+1][b][2] , g[pre][a][b][2] , -1);
					check(dp[now][a][b][2] , dp[pre][a][b][1] , g[now][a][b][2] , g[pre][a][b][1] , i-1);
					if(i<=n)check(dp[now][a+1][b][2] , dp[pre][a][b][1] + A[i] , g[now][a+1][b][2] , g[pre][a][b][1] , i-1);
				}
	}
	
	int Minloc = 0;
	for(int i=1;i<=k;i++) 
		if(dp[pre][Minloc][Minloc][2] < dp[pre][i][i][2]) 
			Minloc = i;
	
	int l = g[pre][Minloc][Minloc][2][0] , r = g[pre][Minloc][Minloc][2][1];
	for(int i=1;i<=n;i++)
	{
		if(i>=l && i<=r) c1[cc1++] = i;
		else c2[cc2++] = i; 
	}
	
	sort(c1,c1+cc1,cmp1);
	sort(c2,c2+cc2,cmp2);
	sort(c1,c1+Minloc,cmp3);
	sort(c2,c2+Minloc,cmp3);
	printf("%lld %d\n",dp[pre][Minloc][Minloc][2] , Minloc);
	for(int i=0;i<Minloc;i++)
		printf("%d %d\n",c1[i],c2[i]);
	printf("%d %d\n",l,r);
}