#include<bits/stdc++.h>

using namespace std;

#define pb push_back

const int maxim  = 1e6 + 1000;
const int maxN = 1010;
mt19937 rng(time(0));
int a[maxN][maxN];
int n, m, k;
int h[maxim];
vector<pair<int,int>> ans, currentAns, currentAns1;
map<int, int> mp;
int ob[maxN][maxN];
int bit[maxim];
long long bestAns = 0;
int dx[4] = {1, -1, 0, 0};
int dy[4]= {0, 0, -1, 1};
int maxi;
int neg[maxN][maxN];
int firstTime;
pair<int, int> pr[maxN][maxN];
int furX, furY;
int maxLen;

clock_t begin_t;

bool inside(int x, int y)
{
    return (x>=1 && x<=n && y>=1 && y<=m);
}

int isShitty(int xi, int yi)
{
    return neg[xi][yi];
}

int get(int poz)
{
    int ans = 0;

    for (int i = poz; i>0; i-=i&(-i))
        ans=max(bit[i], ans);

    return ans;
}

void update(int poz, int val)
{
    for (int i = poz; i< n*m; i+=i&(-i))
        bit[i]= max(bit[i], val);
}

void reset()
{
    for (int i = 1; i<maxi; i++)
        bit[i] = 0;
    for (int i=1; i<=n; i++)
        for (int j=1; j<=m; j++)
        {
            pr[i][j] = {-1, -1};
            if (!a[i][j]) ob[i][j] = 1;
            else
                ob[i][j] = 0;

            for (int w = 0; w < 4; w++)
                if (inside(i+dx[w], j + dy[w]) && !ob[i+dx[w]][j+dy[w]])
                    neg[i][j]++;

        }
    currentAns.clear();
    currentAns1.clear();
}


void print_data()
{
    freopen("path.out", "w",stdout);
    printf("%d\n",ans.size());

    for (auto i: ans)
        printf("%d %d\n",i.first, i.second);
    cout<<bestAns<<endl;

    fclose(stdout);
}

void read_data()
{
    freopen("path.in","r",stdin);
    scanf("%d%d",&n,&m);

    for (int i=1; i<=n; i++)
        for (int j=1; j<=m; j++)
            scanf("%d",&a[i][j]);

    scanf("%d",&k);

    maxi = n*m+10;
    fclose(stdin);

}

void compress_data()
{
    int cur = 0;
    for (int i = 1; i<=n; i++)
        for (int j=1; j<=m; j++)
            h[++cur] = a[i][j];

    int cnt = -1;

    sort(h+1, h+cur+1);

    for (int i=1; i<=cur; i++)
        if (h[i]!=h[i-1])
        {
            if (cnt==-1 && h[i]!=-1) cnt++;
            mp[h[i]]=++cnt;
        }

    for (int i=1; i<=n; i++)
        for (int j=1; j<=m; j++)
            a[i][j] = mp[a[i][j]];
}

int calc_lis(int *a, int n)
{
    int ans = 0;
    for (int i=1; i<=n; i++)
    {
        int val = get(a[i]-1) + 1;
        update(a[i], val);
        ans = max (ans, val);
    }

    return ans;
}

long long calc_ans(vector<pair<int,int>> &currentAns)
{
    long long ans = 1;
    int t = 2;

    while(t--)
    {

        int cur = 0;
        for (auto i: currentAns)
            h[++cur] = a[i.first][i.second];

        ans*=calc_lis(h, currentAns.size());

        for (int i=1; i<maxi; i++)
            bit[i] = 0;

        reverse(currentAns.begin(), currentAns.end());
    }

    return ans;
}

void change_res(vector<pair<int,int>> &currentAns)
{
    ans.clear();
    for (auto i:currentAns)
        ans.pb(i);
}

void remove_nei(int x, int y)
{
    for (int w = 0; w < 4; w++)
        if (inside(x+dx[w], y + dy[w]) && !ob[x+dx[w]][y+dy[w]])
            neg[x + dx[w]][y + dy[w]]--;
}

void greedy_dfs(int xi, int yi, int type,vector<pair<int,int>> &currentAns)
{
    int steps = k - 1;

    currentAns.pb({xi,yi});
    ob[xi][yi] = 1;

    if (!firstTime)
        remove_nei(xi, yi);

    while(steps--)
    {
        int value = 0;
        int pozX = 0;
        int pozY = 0;

        for (int i=0; i<4; i++)
            if (inside(xi+dx[i], yi+dy[i]) && !ob[xi+dx[i]][yi+dy[i]] && !isShitty(xi+dx[i], yi+dy[i]))
            {
                if (type && (!value || (a[xi+dx[i]][yi + dy[i]]>a[xi][yi] && value>a[xi+dx[i]][yi + dy[i]])))
                {
                    pozX = xi + dx[i];
                    pozY = yi + dy[i];
                    value = a[xi+dx[i]][yi + dy[i]];
                }
                else if (!type && (!value || (a[xi+dx[i]][yi + dy[i]]<a[xi][yi] && value<a[xi+dx[i]][yi + dy[i]])))
                {
                    pozX = xi + dx[i];
                    pozY = yi + dy[i];
                    value = a[xi+dx[i]][yi + dy[i]];
                }
            }

        if (!value)
        {
            for (int i=0; i<4; i++)
                if (inside(xi+dx[i], yi+dy[i]) && !ob[xi+dx[i]][yi+dy[i]])
                {
                    if (type && (!value || (a[xi+dx[i]][yi + dy[i]]>a[xi][yi] && value>a[xi+dx[i]][yi + dy[i]])))
                    {
                        pozX = xi + dx[i];
                        pozY = yi + dy[i];
                        value = a[xi+dx[i]][yi + dy[i]];
                    }
                    else if (!type && (!value || (a[xi+dx[i]][yi + dy[i]]<a[xi][yi] && value<a[xi+dx[i]][yi + dy[i]])))
                    {
                        pozX = xi + dx[i];
                        pozY = yi + dy[i];
                        value = a[xi+dx[i]][yi + dy[i]];
                    }
                }
        }
        //type^=1;
        if (!value) break;
        currentAns.pb({pozX,pozY});
        ob[pozX][pozY] = 1;
        xi = pozX;
        yi = pozY;

        remove_nei(pozX, pozY);
    }

}
void solve1()
{
    while(clock()- begin_t<= CLOCKS_PER_SEC *1.5)
    {
        reset();
        int xi = 0;
        int yi = 0;
        int type = rng()%2;

        while(!a[xi][yi])
        {
            xi = rng()%n + 1;
            yi = rng()%m + 1;
        }

        firstTime = 0;
        greedy_dfs(xi,yi, type, currentAns);

        firstTime = 1;
        greedy_dfs(xi, yi, type^1, currentAns1);


        vector<pair<int,int>> resV;
        resV.clear();

        for (int i = currentAns1.size()-1 ; i>=0; i--)
            resV.pb(currentAns1[i]);

        for (int i = 1 ; i<currentAns.size() && resV.size()<k; i++)
            resV.pb(currentAns[i]);

        long long value = calc_ans(resV);

        if (value > bestAns)
        {
            bestAns = value;
            change_res(resV);
        }

    }

}

void dfs(int x, int y, int prX, int prY, int len)
{
    ob[x][y] = 1;
    pr[x][y] = {prX,prY};
    remove_nei(x,y);

    len++;

    if (len>maxLen)
    {
        maxLen = len;
        furX = x;
        furY = y;
    }

    for (int i=1;i<=5;i++)
    {
        int fr = rng()%4;
        int sc = rng()%4;
        swap(dx[fr], dx[sc]);
        swap(dy[fr], dy[sc]);
    }
    for (int i=0; i<4; i++)
        if (inside(x+dx[i], y+dy[i]) && !ob[x+dx[i]][y+dy[i]] && !isShitty(x+dx[i], y+dy[i]))
            dfs(x + dx[i], y + dy[i], x, y, len);

    for (int i=0; i<4; i++)
        if (inside(x+dx[i], y+dy[i]) && !ob[x+dx[i]][y+dy[i]])
            dfs(x + dx[i], y + dy[i], x, y, len);

}
void solve2() //just long path
{

    while(clock()- begin_t<= CLOCKS_PER_SEC *4.4)
    {
        reset();
        int xi = 0;
        int yi = 0;
        maxLen = 0;

        while(!a[xi][yi])
        {
            xi = rng()%n + 1;
            yi = rng()%m + 1;
        }

        dfs(xi,yi, -1,-1, 0);
        int steps = 0;

        while(pr[furX][furY].first!=-1 && steps<k)
        {
            currentAns.pb({furX, furY});
            int x = pr[furX][furY].first;
            int y = pr[furX][furY].second;
            furX = x;
            furY = y;
            steps++;
        }

        long long value = calc_ans(currentAns);

        if (value > bestAns)
        {
            bestAns = value;
            change_res(currentAns);
        }
    }
}
void solve()
{
    solve1();
    solve2();
}
int main()
{

    read_data();
    compress_data();
    solve();
    print_data();

    return 0;
}