#include <iostream>
#include <iomanip>
#include <fstream>
#include <cstring>
#include <string>
#include <functional>
#include <cmath>
#include<algorithm>
typedef long long ll;
using namespace std;
int a[1000][1000], n;
ll dp[1002][1002];
ll solve(int x, int y){
	if (x >= n || y >= n){
		return 0;
	}
	ll ret = 0;
	if (dp[x][y] != -1)return dp[x][y];
	ret += a[x][y]+max(solve(x + 1, y), solve(x, y + 1));
	dp[x][y] = ret;
	return ret;

}
bool check(int x, int y){
	return x < n&&y < n;
}
void outputcord(int x,int y){
	if (x == n-1&&y == -1+n)return;
	if ( dp[x][y + 1] >= dp[x + 1][y]){
		cout << x + 1 << ' ' << y + 2<<'\n';
		return outputcord(x, y + 1);
	}
	else{
		cout << x + 2 << ' ' << y + 1<<'\n';
		return outputcord(x + 1, y) ;
	}
}
int main()
{
	cin >> n;
	for (int i = 0; i < n;i++)
	for (int k = 0; k < n; k++)
		cin >> a[i][k];
	memset(dp, -1, sizeof dp);
	cout << solve(0, 0) << '\n';
	cout << 1 << ' ' << 1 << '\n';
	outputcord(0,0);

//cout << n << ' ' << n << '\n';


}