lenes

#include <cstdio>
#include <cstring>
#include <algorithm>
#define NMax 1010
#define VMax 1010
#define oo 0x3f3f3f3f
using namespace std;
const char IN[] = "lenes.in", OUT[] = "lenes.out";
int Case, N, M, k1, k2;
int Mat[NMax][NMax];
int Sum[NMax], V[NMax], left[NMax], right[NMax];

int get_line_sum( int lin, int k, bool up = true, bool down = true )
{

    int res = Sum[lin];

    static int v[VMax];
    memset(v, 0, sizeof(v));

    for ( int i = 1; i <= M; ++ i ) {
        if ( up )
            ++ v[ Mat[lin - 1][i] ];
        if ( down )
            ++ v[ Mat[lin + 1][i] ];
    }

    for ( int i = 0; i < VMax && k ; ++ i )
        if ( k >= v[i] ) {
            res += i * v[i];
            k -= v[i];
        } else if ( v[i] ) {
            res += k * i;
            k = 0;
        }

    return res;
}

int case1()
{

    int ret = get_line_sum(1, k1);

    for ( int i = 1; i <= N; ++ i )
        ret = min( ret, get_line_sum(i, k1));

    return ret;
}

int case2()
{

    int ret = oo;

    for ( int i = 1; i <= N; ++ i )
        V[i] = get_line_sum(i, k2);

    left[1] = V[1];
    for ( int i = 2; i <= N; ++ i )
        left[i] = min(V[i], left[i - 1]);

    right[N] = V[N];
    for ( int i = N - 1; i > 0; -- i )
        right[i] = min(V[i], right[i + 1]);


    // computing distant lines
    for ( int i = 1; i <= N; ++ i ) {
        int r = get_line_sum(i, k1);
        int other = oo;

        if ( i > 3 ) other = min(other, left[i - 3]);
        if ( i < N - 2) other = min(other, right[i + 3]);

        ret = min(ret, r + other);
    }

    // computing adiacent lines
    for ( int i = 1; i < N; ++ i ) {

        int r1 = get_line_sum(i, k1    , true, false);
        int r2 = get_line_sum(i + 1, k2, false, true);

        ret = min( ret, r1 + r2 );

        r1 = get_line_sum(i, k2    , true, false);
        r2 = get_line_sum(i + 1, k1, false, true);

        ret = min( ret, r1 + r2 );
    }

    //fprintf(stderr, "%d\n", ret);
    // computing common margin lines

    bool parity = true;

    for ( int i = 1; i < N - 1; ++ i ) {

        int sum = Sum[i] + Sum[i + 2];
        int up = i - 1;
        int mid = i + 1;
        int down = i + 3;
        int index_up = 1;
        int index_down = 1;

        for ( int j = 1; j <= M && j <= k1 + k2; ++ j )
            sum += Mat[mid][j];

        // adding extra elements
        for ( int j = M + 1; j <= k1 + k2; ++ j ) {
            if ( index_up <= k1 && Mat[up][index_up] <= Mat[down][index_down] || index_down > k2 ) {
                sum += Mat[up][index_up];
                ++ index_up;
            } else {
                sum += Mat[down][index_down];
                ++ index_down;
            }
        }

        ret = min(ret, sum);
        //fprintf(stderr, "begining with: (%d, %d, %d)\n", index_up - 1, min(M, k1 + k2), index_down - 1);
        for ( int j = min(M, k1 + k2); j > 0; -- j ) {
            sum -= Mat[mid][j];
            if ( index_up <= k1 && Mat[up][index_up] <= Mat[down][index_down] || index_down > k2  ) {
                sum += Mat[up][index_up];
                ++ index_up;
            } else {
                sum += Mat[down][index_down];
                ++ index_down;
            }

            ret = min( ret, sum );
            if ( ret == sum ) {
                //fprintf(stderr, "(up: %d, mid: %d, down: %d -> %d\n", index_up - 1, j - 1, index_down - 1, ret);
            }
        }

        if ( parity ) {
            parity = false;
            -- i;
        } else {
            parity = true;
        }

        swap( k1, k2 );

    }

    return ret;
}

int (*Work[])() = { case1, case2 };

int main()
{

    freopen(IN, "r", stdin);
    freopen(OUT, "w", stdout);

    scanf("%d%d%d%d%d", &Case, &N, &M, &k1, &k2);

    for ( int i = 1; i <= N; ++ i)
        for ( int j = 1; j <= M; ++ j )
            scanf("%d", &Mat[j][i]);

    swap(N, M);

    for ( int i = 1; i <= N; ++ i )
        for ( int j = 1; j <= M; ++ j )
            Sum[i] += Mat[i][j];

    for ( int i = 1; i <= M; ++ i )
        Mat[0][i] = Mat[N + 1][i] = VMax - 1;

    for ( int i = 1; i <= N; ++ i )
        sort( Mat[i] + 1, Mat[i] + M + 1);

    printf("%d\n", Work[Case - 1]());

    return 0;
}