/*
sum[i][j]从1,1到i,j组成的矩形的和
sum[i][j] = sum[i-1][j] + sum[i][j-1] - sum[i-1][j-1]+a[i][j]

r*c 的区域
ans[i][j]以ij点结尾的r*c的区域的和
ans[i][j] = sum[i][j]-sum[i-r][j]-sum[i][j-c]+sum[i-r][j-c]

*/
#include <bits/stdc++.h>
using namespace std;
#define int long long
int n,m,c,a[1005][1005];
int sum[1005][1005],res=-1e18;
signed main(){
	cin>>n>>m>>c;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			cin>>a[i][j];
			sum[i][j] = sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1]+a[i][j];
		}
	}
	int idx,idy;
	for(int i=c;i<=n;i++){
		for(int j=c;j<=m;j++){
			int T = sum[i][j]-sum[i-c][j]-sum[i][j-c]+sum[i-c][j-c];
			if(T>res){
				idx=i-c+1;
				idy=j-c+1;
				res = T;
			}
		}
	}
	cout<<idx<<" "<<idy<<endl;
	return 0;
}

#include <bits/stdc++.h>
using namespace std;
const int N = 5005;
int a[N][N];
int n,m,sum[N][N];
int main(){
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		int x,y,z;
		cin>>x>>y>>z;
		x++;y++;
		a[x][y] += z;
	}
	for(int i=1;i<=5001;i++){
		for(int j=1;j<=5001;j++){
			sum[i][j] = a[i][j]+sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1];
		}
	}
	int res = 0;
	for(int i=m;i<=5001;i++){
		for(int j=m;j<=5001;j++){
			res = max(res,sum[i][j]-sum[i-m][j]-sum[i][j-m]+sum[i-m][j-m]);
		}
	}
	cout<<res<<endl;
	return 0;
}

#include <bits/stdc++.h>
using namespace std;
const int N = 5e6+5;
int n,p,a[N],b[N];
int main(){
	cin>>n>>p;
	for(int i=1;i<=n;i++){
		cin>>a[i];
		b[i] = a[i] - a[i-1];
	}
	for(int i=1;i<=p;i++){
		int x,y,z;
		cin>>x>>y>>z;
		b[x]+=z;
		b[y+1]-=z;
	}
	int res = 1e9;
	for(int i=1;i<=n;i++){
		b[i]+=b[i-1];
		res = min(res,b[i]);
	}
	cout<<res<<endl;
	return 0;
}

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5+5;
#define int long long
int n,m,p[N],a[N];
int A[N],B[N],C[N];
signed main(){
	cin>>n>>m;
	for(int i=1;i<=m;i++){
		cin>>p[i];
	}
	for(int i=2;i<=n;i++){
		cin>>A[i]>>B[i]>>C[i];
	}
	for(int i=2;i<=m;i++){
		//从p[i-1]到p[i]
		int x = p[i-1],y=p[i];
		if(x>y)swap(x,y);
		a[x+1]++;
		a[y+1]--;
	}
	int cost = 0;
	for(int i=2;i<=n;i++){
		a[i]+=a[i-1];
		if(a[i]*A[i]>C[i]+a[i]*B[i]){
			cost+=C[i]+a[i]*B[i];
		}
		else cost+=a[i]*A[i];
	}
	cout<<cost<<endl;
	return 0;
}

/*
k个任务无法完成，k+1个任务无法完成 
*/
#include <bits/stdc++.h>
using namespace std;
const int N = 1e6+5;
#define int long long
int n,a[N],m,b[N];
struct node{
	int d,s,t;
}p[N];
int check(int x)
{
	//只想尝试前x个任务
	memset(b,0,sizeof(b));
	for(int i=1;i<=x;i++){
		b[p[i].s]+=p[i].d;
		b[p[i].t+1]-=p[i].d;
	}
	for(int i=1;i<=n;i++){
		b[i]+=b[i-1];
		if(b[i]>a[i]){
			return 0;
		}
	}
	return 1;
}
signed main(){
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		cin>>a[i];
	}
	for(int i=1;i<=m;i++){
		cin>>p[i].d>>p[i].s>>p[i].t;
	}
	int l=0,r=m;
	int res = -1;
	while(l<=r){
		int mid = (l+r)>>1;
		if(check(mid)){
			res = mid;
			l = mid+1;
		}
		else r = mid-1;
	}
	if(res==m)cout<<0<<endl;
	else{
		cout<<-1<<endl;
		cout<<res+1<<endl;
	}
	//cout<<res<<endl;
	return 0;
}