#include <iostream>
#include <fstream>
#include <vector>
#include <list>
#include <chrono>
using namespace std;

struct solution
{
    struct pair
    {
        int left, right;

        pair(int l, int r) : left(l), right(r) {}
    };

    int N, price_index_type, price_value_type;
    vector<int> inputs;
    vector<vector<int>> prices_index, prices_value;
    list<pair> swaps;
    chrono::steady_clock::time_point end_time = chrono::steady_clock::now() + chrono::milliseconds(2900);

    bool read_all(const char* fname);
    bool read_input(istream& fin);
    bool read_prices(istream& fin, int& price_type, vector<vector<int>>& prices);
    void solve();
    int solveSimpleForward();
    int solveSimpleReverse();
    int solveSimple2Forward();
    int solveSimple2Reverse();
    int solveLeastPriceForward();
    int solveLeastPriceReverse();
    int solveBiggestPriceForward();
    int solveBiggestPriceReverse();
    int solveLeastDistance();
    int solveMinTwoSwapsForward();
    int solveMinTwoSwapsReverse();
    int solveMaxTwoSwapsForward();
    int solveMaxTwoSwapsReverse();
    int solveMinTwoSwaps();
    int solveMinTwoSwaps2();
    int solveMariaForward();
    int solveMariaReverse();
    int findMin3Swaps(int i, int vi, int j, int vj, int k, int vk, int& order);
    void do3Swaps(int i, int j, int k, int order);
    void test(int(solution::*solve_func)(), list<pair>& best, int& res);
    void write_result(const char* fname);
    int total_price(int i, int j, int vj) {
        // j == v[i]
        return prices_index[i][j] + prices_value[j][vj];
    }
    int total_price(int i, int j, int vi, int vj) {
        return prices_index[i][j] + prices_value[vi][vj];
    }
    bool not_expired() const
    {
        return chrono::steady_clock::now() < end_time;
    }
};

bool solution::read_all(const char* fname) {
    ifstream fin;
    fin.open(fname);
    bool res = read_input(fin)
        && read_prices(fin, price_index_type, prices_index)
        && read_prices(fin, price_value_type, prices_value);
    fin.close();
    return res;
}

bool solution::read_input(istream& fin) {
    fin >> N;
    if (N < 2 || N > 400) {
#ifdef _DEBUG
        cerr << "Invalid permutations count " << N << endl;
#endif
        return false;
    }

    inputs.resize(N);
    for (int i = 0; i < N; i++) {
        int in;
        fin >> in;
        if (in < 1 || in > N) {
#ifdef _DEBUG
            cerr << "Invalid input number " << in << endl;
#endif
            return false;
        }

        inputs[i] = in - 1;
    }

    return true;
}

bool solution::read_prices(istream& fin, int& price_type, vector<vector<int>>& prices) {
    fin >> price_type;
    if (price_type < 0 || price_type > 4) {
#ifdef _DEBUG
        cerr << "Invalid price type";
#endif
        return false;
    }
    prices.resize(N);
    for (int i = 0; i < N; i++) {
        prices[i].resize(N);
        for (int j = 0; j < N; j++) {
            int in;
            fin >> in;
            if (in < 0) {
#ifdef _DEBUG
                cerr << "Invalid price[" << i << "][" << j << "]=" << in << endl;
#endif
                return false;
            }
            prices[i][j] = in;
        }
    }
    return true;
}
// direct by increasing index
int solution::solveSimpleForward() {
    swaps.clear();
    int total = 0;
    vector<int> sorted(inputs);
    for (int i = 0; i < N - 1; i++) {
        int vi = sorted[i];
        if (vi != i) {
            total += total_price(i, vi, sorted[vi]);
            sorted[i] = sorted[vi];
            sorted[vi] = vi;
            swaps.push_back(pair(i, vi));
            i--;
        }
    }
    return total;
}
// direct by increasing index
int solution::solveSimple2Forward() {
    swaps.clear();
    int total = 0;
    vector<int> sorted(inputs);
    for (int i = 0; i < N - 1; i++) {
        int vi = sorted[i];
        if (vi != i) {
            int j = i + 1;
            while (j < N && sorted[j] != i) j++;
            total += total_price(j, i, vi);
            sorted[j] = vi;
            sorted[i] = i;
            swaps.push_back(pair(i, j));
        }
    }
    return total;
}
// direct by decreasing index
int solution::solveSimpleReverse() {
    swaps.clear();
    int total = 0;
    vector<int> sorted(inputs);
    for (int i = N - 1; i > 0; i--) {
        int vi = sorted[i];
        if (vi != i) {
            total += total_price(i, vi, sorted[vi]);
            sorted[i] = sorted[vi];
            sorted[vi] = vi;
            swaps.push_back(pair(i, vi));
            i++;
        }
    }
    return total;
}
// direct by decreasing index
int solution::solveSimple2Reverse() {
    swaps.clear();
    int total = 0;
    vector<int> sorted(inputs);
    for (int i = N - 1; i > 0; i--) {
        int vi = sorted[i];
        if (vi != i) {
            int j = 0;
            while (sorted[j] != i) j++;

            total += total_price(j, i, vi);
            sorted[j] = vi;
            sorted[i] = i;
            swaps.push_back(pair(i, j));
        }
    }
    return total;
}
// find swap with least price and increasing index
int solution::solveLeastPriceForward() {
    swaps.clear();
    int total = 0;
    vector<int> sorted(inputs);
    for (int i = 0; i < N; i++) {
        int ii = sorted[i];
        if (ii != i) {
            int minPrice = total_price(i, ii, sorted[ii]), k = i, kk = ii;
            for (int j = i + 1; j < N; j++) {
                int jj = sorted[j];
                if (jj != j && jj != i) {
                    int pricej = total_price(j, jj, sorted[jj]);
                    if (pricej < minPrice) {
                        minPrice = pricej;
                        k = j;
                        kk = jj;
                    }
                }
            }
            total += minPrice;
            sorted[k] = sorted[kk];
            sorted[kk] = kk;
            swaps.push_back(pair(k, kk));
            i--;
        }
    }
    return total;
}
// find least price and decreasing index
int solution::solveLeastPriceReverse() {
    swaps.clear();
    int total = 0;
    vector<int> sorted(inputs);
    for (int i = N - 1; i > 0; i--) {
        int vi = sorted[i];
        if (vi != i) {
            int minPrice = total_price(i, vi, sorted[vi]), k = i, vk = vi;
            for (int j = i - 1; j >= 0; j--) {
                int vj = sorted[j];
                if (vj != j && vj != i) {
                    int pricej = total_price(j, vj, sorted[vj]);
                    if (pricej < minPrice) {
                        minPrice = pricej;
                        k = j;
                        vk = vj;
                    }
                }
            }
            total += minPrice;
            sorted[k] = sorted[vk];
            sorted[vk] = vk;
            swaps.push_back(pair(k, vk));
            i++;
        }
    }
    return total;
}
// find swap with biggest price and increasing index
int solution::solveBiggestPriceForward() {
    swaps.clear();
    int total = 0;
    vector<int> sorted(inputs);
    for (int i = 0; i < N; i++) {
        int vi = sorted[i];
        if (vi != i) {
            int maxPrice = total_price(i, vi, sorted[vi]), k = i, vk = vi;
            for (int j = i + 1; j < N; j++) {
                int vj = sorted[j];
                if (vj != j && vj != i) {
                    int pricej = total_price(j, vj, sorted[vj]);
                    if (pricej > maxPrice) {
                        maxPrice = pricej;
                        k = j;
                        vk = vj;
                    }
                }
            }
            total += maxPrice;
            sorted[k] = sorted[vk];
            sorted[vk] = vk;
            swaps.push_back(pair(k, vk));
            i--;
        }
    }
    return total;
}
// find swap with biggest price and decreasing index
int solution::solveBiggestPriceReverse() {
    swaps.clear();
    int total = 0;
    vector<int> sorted(inputs);
    for (int i = N - 1; i > 0; i--) {
        int vi = sorted[i];
        if (vi != i) {
            int maxPrice = total_price(i, vi, sorted[vi]), k = i, vk = vi;
            for (int j = i - 1; j >= 0; j--) {
                int vj = sorted[j];
                if (vj != j && vj != i) {
                    int pricej = total_price(j, vj, sorted[vj]);
                    if (pricej > maxPrice) {
                        maxPrice = pricej;
                        k = j;
                        vk = vj;
                    }
                }
            }
            total += maxPrice;
            sorted[k] = sorted[vk];
            sorted[vk] = vk;
            swaps.push_back(pair(k, vk));
            i++;
        }
    }
    return total;
}
// search nearest swap until all sorted
int solution::solveLeastDistance() {
    swaps.clear();
    int total = 0;
    vector<int> sorted(inputs);

    bool swapFound = true;
    while (swapFound) {
        swapFound = false;
        int i, j, minPrice;
        for (int k = 1; k < N - 1; k++) {
            minPrice = INT32_MAX;
            for (int l = 0; l < N - k; l++) {
                int vl = sorted[l];
                int vlk = sorted[l + k];
                if (vlk < vl) {
                    int price = total_price(l + k, l, vlk, vl);
                    if (price < minPrice) {
                        minPrice = price;
                        i = l + k;
                        j = l;
                        swapFound = true;
                    }
                }
            }
            if (swapFound) {
                total += minPrice;
                int s = sorted[i];
                sorted[i] = sorted[j];
                sorted[j] = s;
                swaps.push_back(pair(i, j));
                break;
            }
        }
    }
    return total;
}

int solution::solveMinTwoSwapsForward()
{
    swaps.clear();
    int total = 0;
    vector<int> sorted(inputs);
    for (int i = 0; i < N - 1; i++) {
        int vi = sorted[i];
        if (vi != i) {
            int minPrice = total_price(i, vi, sorted[vi]), k = i, vk = vi;
            for (int j = i + 1; j < N; j++) {
                int vj = sorted[j];
                if (vj != j && vj != i) {
                    int pricej = total_price(j, vj, sorted[vj]);
                    if (pricej < minPrice) {
                        minPrice = pricej;
                        k = j;
                        vk = vj;
                    }
                }
            }
            int min_j = 0, min_order = 0, vkk = sorted[vk];
            for (int j = 0; j < N; j++) {
                if (j != k && j != vk) {
                    int vj = sorted[j], order;
                    int dualPrice = findMin3Swaps(k, vk, j, vj, vk, vkk, order);
                    if (dualPrice < minPrice) {
                        minPrice = dualPrice;
                        min_order = order;
                        min_j = j;
                    }
                }
            }
            total += minPrice;
            sorted[k] = vkk;
            sorted[vk] = vk;
            do3Swaps(k, min_j, vk, min_order);
            i--;
        }
    }
    return total;
}

int solution::solveMinTwoSwapsReverse()
{
    swaps.clear();
    int total = 0;
    vector<int> sorted(inputs);
    for (int i = N - 1; i > 0; i--) {
        int vi = sorted[i];
        if (vi != i) {
            int minPrice = total_price(i, vi, sorted[vi]), k = i, vk = vi;
            for (int j = i - 1; j >= 0; j--) {
                int vj = sorted[j];
                if (vj != j && vj != i) {
                    int pricej = total_price(j, vj, sorted[vj]);
                    if (pricej < minPrice) {
                        minPrice = pricej;
                        k = j;
                        vk = vj;
                    }
                }
            }
            int min_j = 0, min_order = 0, vkk = sorted[vk];
            for (int j = 0; j < N; j++) {
                if (j != k && j != vk) {
                    int vj = sorted[j], order;
                    int dualPrice = findMin3Swaps(k, vk, j, vj, vk, vkk, order);
                    if (dualPrice < minPrice) {
                        minPrice = dualPrice;
                        min_order = order;
                        min_j = j;
                    }
                }
            }
            total += minPrice;
            sorted[k] = vkk;
            sorted[vk] = vk;
            do3Swaps(k, min_j, vk, min_order);
            i++;
        }
    }
    return total;
}

int solution::solveMaxTwoSwapsForward()
{
    swaps.clear();
    int total = 0;
    vector<int> sorted(inputs);
    for (int i = 0; i < N - 1; i++) {
        int vi = sorted[i];
        if (vi != i) {
            int maxPrice = total_price(i, vi, sorted[vi]), k = i, vk = vi;
            for (int j = i + 1; j < N; j++) {
                int vj = sorted[j];
                if (vj != j && vj != i) {
                    int pricej = total_price(j, vj, sorted[vj]);
                    if (pricej > maxPrice) {
                        maxPrice = pricej;
                        k = j;
                        vk = vj;
                    }
                }
            }
            int min_j = 0, min_order = 0, vkk = sorted[vk];
            for (int j = 0; j < N; j++) {
                if (j != k && j != vk) {
                    int vj = sorted[j], order;
                    int dualPrice = findMin3Swaps(k, vk, j, vj, vk, vkk, order);
                    if (dualPrice < maxPrice) {
                        maxPrice = dualPrice;
                        min_order = order;
                        min_j = j;
                    }
                }
            }
            total += maxPrice;
            sorted[k] = vkk;
            sorted[vk] = vk;
            do3Swaps(k, min_j, vk, min_order);
            i--;
        }
    }
    return total;
}

int solution::solveMaxTwoSwapsReverse()
{
    swaps.clear();
    int total = 0;
    vector<int> sorted(inputs);
    for (int i = N - 1; i > 0; i--) {
        int vi = sorted[i];
        if (vi != i) {
            int maxPrice = total_price(i, vi, sorted[vi]), k = i, vk = vi;
            for (int j = i - 1; j >= 0; j--) {
                int vj = sorted[j];
                if (vj != j && vj != i) {
                    int pricej = total_price(j, vj, sorted[vj]);
                    if (pricej < maxPrice) {
                        maxPrice = pricej;
                        k = j;
                        vk = vj;
                    }
                }
            }
            int min_j = 0, min_order = 0, vkk = sorted[vk];
            for (int j = 0; j < N; j++) {
                if (j != k && j != vk) {
                    int vj = sorted[j], order;
                    int dualPrice = findMin3Swaps(k, vk, j, vj, vk, vkk, order);
                    if (dualPrice < maxPrice) {
                        maxPrice = dualPrice;
                        min_order = order;
                        min_j = j;
                    }
                }
            }
            total += maxPrice;
            sorted[k] = vkk;
            sorted[vk] = vk;
            do3Swaps(k, min_j, vk, min_order);
            i++;
        }
    }
    return total;
}

int solution::solveMinTwoSwaps()
{
    swaps.clear();
    int total = 0;
    vector<int> sorted(inputs);
    for (int i = 0; i < N - 1; i++) {
        int vi = sorted[i];
        if (vi != i) {
            int min_j = 0, vk = sorted[vi];
            int minPrice = total_price(i, vi, vk);
            int min_order = 0;
            for (int j = 0; j < N; j++) {
                if (j != i && j != vi) {
                    int vj = sorted[j], order;
                    int dualPrice = findMin3Swaps(i, vi, j, vj, vi, vk, order);
                    if (dualPrice < minPrice) {
                        minPrice = dualPrice;
                        min_order = order;
                        min_j = j;
                    }
                }
            }
            total += minPrice;
            sorted[i] = vk;
            sorted[vi] = vi;
            do3Swaps(i, min_j, vi, min_order);
            i--;
        }
    }
    return total;
}

int solution::solveMinTwoSwaps2()
{
    swaps.clear();
    int total = 0;
    vector<int> sorted(inputs);
    while (not_expired())
    {
        int minPrice = INT32_MIN, min_i = -1, min_j = -1, min_k = -1, min_order = -1;
        for (int i = 0; i < N - 1; i++) {
            int vi = sorted[i];
            if (vi != i) {
                int vk = sorted[vi];
                min_i = i;
                min_j = i;
                min_k = vi;
                min_order = 0;
                minPrice = total_price(i, vi, vk);
                for (int j = 0; j < N; j++) {
                    if (j != i && j != vi) {
                        int vj = sorted[j], order;
                        int dualPrice = findMin3Swaps(i, vi, j, vj, vi, vk, order);
                        if (dualPrice < minPrice) {
                            minPrice = dualPrice;
                            min_order = order;
                            min_i = i;
                            min_j = j;
                            min_k = vi;
                        }
                    }
                }
            }
        }
        if (min_i >= 0)
        {
            total += minPrice;
            sorted[min_i] = sorted[min_k];
            sorted[min_k] = min_k;
            do3Swaps(min_i, min_j, min_k, min_order);
        }
        else
            break;
    }
    return total;
}

int solution::solveMariaForward()
{
    swaps.clear();
    int total = 0;
    vector<int> sorted(inputs);
    for (int i = 0; i < N - 1; i++) {
        int vi = sorted[i];
        if (vi != i) {
            int j = i;
            bool cont = true;
            while (cont) {
                cont = false;
                for (int k = j + 1; k < N; k++) {
                    int vk = sorted[k];
                    if (vk != k && vk <= j) {
                        total += total_price(k, j, vk, vi);
                        swaps.push_back(pair(k, j));
                        sorted[j] = vk;
                        sorted[k] = vi;
                        j = k;
                        cont = true;
                    }
                }
            }
            if (sorted[i] != i) i--;
        }
    }
    return total;
}

int solution::solveMariaReverse()
{
    swaps.clear();
    int total = 0;
    vector<int> sorted(inputs);
    for (int i = N - 1; i > 0; i--) {
        int vi = sorted[i];
        if (vi != i) {
            int j = i;
            bool cont = true;
            while (cont) {
                cont = false;
                for (int k = j - 1; k >= 0; k--) {
                    int vk = sorted[k];
                    if (vk != k && vk <= j) {
                        total += total_price(k, j, vk, vi);
                        swaps.push_back(pair(k, j));
                        sorted[j] = vk;
                        sorted[k] = vi;
                        j = k;
                        cont = true;
                    }
                }
            }
            if (sorted[i] != i) i++;
        }
    }
    return total;
}

int solution::findMin3Swaps(int i, int vi, int j, int vj, int k, int vk, int& order)
{
    int minPrice = total_price(i, k, vi, vk);
    order = 0;
    int dualPrice = total_price(i, j, vj, vi) +
                    total_price(j, k, vk, vi) +
                    total_price(i, j, vk, vj);
    if (dualPrice < minPrice) {
        minPrice = dualPrice;
        order = 1;
    }
    dualPrice = total_price(i, j, vj, vi) +
                total_price(i, k, vk, vj) +
                total_price(k, j, vi, vj);
    if (dualPrice < minPrice) {
        minPrice = dualPrice;
        order = 2;
    }
    dualPrice = total_price(k, j, vj, vk) +
                total_price(i, j, vk, vi) +
                total_price(k, j, vi, vj);
    if (dualPrice < minPrice) {
        minPrice = dualPrice;
        order = 3;
    }
    dualPrice = total_price(k, j, vj, vk) +
                total_price(i, k, vj, vi) +
                total_price(i, j, vk, vj);
    if (dualPrice < minPrice) {
        minPrice = dualPrice;
        order = 4;
    }
    return minPrice;
}

void solution::do3Swaps(int i, int j, int k, int order)
{
    switch (order)
    {
    case 0:
        swaps.push_back(pair(i, k));
        break;
    case 1:
        swaps.push_back(pair(i, j));
        swaps.push_back(pair(j, k));
        swaps.push_back(pair(i, j));
        break;
    case 2:
        swaps.push_back(pair(i, j));
        swaps.push_back(pair(i, k));
        swaps.push_back(pair(k, j));
        break;
    case 3:
        swaps.push_back(pair(k, j));
        swaps.push_back(pair(i, j));
        swaps.push_back(pair(k, j));
        break;
    case 4:
        swaps.push_back(pair(k, j));
        swaps.push_back(pair(i, k));
        swaps.push_back(pair(i, j));
        break;
    default:
        break;
    }
}

void solution::test(int(solution::*solve_func)(), list<pair>& best, int& res) {
    int newRes = (this->*solve_func)();
    if (newRes < res && not_expired()) {
        res = newRes;
        best = move(swaps);
    }
}

void solution::solve() {
    list<pair> best;
    int res = INT32_MAX;
    test(&solution::solveSimpleForward, best, res);
    test(&solution::solveSimpleReverse, best, res);
    test(&solution::solveSimple2Forward, best, res);
    test(&solution::solveSimple2Reverse, best, res);
    test(&solution::solveLeastPriceForward, best, res);
    test(&solution::solveLeastPriceReverse, best, res);
    test(&solution::solveBiggestPriceForward, best, res);
    test(&solution::solveBiggestPriceReverse, best, res);
    test(&solution::solveLeastDistance, best, res);
    test(&solution::solveMinTwoSwapsForward, best, res);
    test(&solution::solveMinTwoSwapsReverse, best, res);
    test(&solution::solveMaxTwoSwapsForward, best, res);
    test(&solution::solveMaxTwoSwapsReverse, best, res);
    test(&solution::solveMinTwoSwaps, best, res);
    //test(&solution::solveMinTwoSwaps2, best, res);
    test(&solution::solveMariaForward, best, res);
    test(&solution::solveMariaReverse, best, res);
    swaps = move(best);
}

void solution::write_result(const char* fname) {
    ofstream fout;
    fout.open(fname);
    int count = swaps.size();
    fout << count << endl;
    for (list<pair>::iterator it(swaps.begin()), en(swaps.end()); it != en; it++) {
        fout << it->left + 1 << " " << it->right + 1 << endl;
    }
    fout.close();
}

#ifdef _DEBUG
#define fname "sorting.02"
#else
#define fname "sorting"
#endif

int main()
{
    solution sol;
    if (!sol.read_all(fname ".in"))
        return 1;

    sol.solve();

    sol.write_result(fname ".out");

    return 0;
}