#include <bits/stdc++.h>
#define up(i,a,b) for (int i = (int)a; i <= (int)b; i++)
using namespace std;

mt19937_64 RNG(chrono::high_resolution_clock::now().time_since_epoch().count());
int UID(int l, int r){
    uniform_int_distribution<mt19937_64::result_type> R(l, r);
    return R(RNG);
}


const int maxn = 15;
int n,K,Q;
int d[maxn];
int c[maxn][maxn];

vector<int> x[maxn];
vector<vector<int> > x_best;

int loaded[maxn];
bool visited[maxn];

int f = 0;
int fbest = INT_MAX-1;
int cmin = INT_MAX-1;
int cmin2 = INT_MAX-1;

bool can_go_to(int car, int x){
    if (visited[x]) return false;
    if (loaded[car] + d[x] > Q) return false;
    return true;
}

void DEBUG(int num_car_using){
    cout << "STEP\n";
    for (int i = 1; i <= num_car_using; i++){
        cout << "BY CAR " << i << ": ";
        for (auto val : x[i]){
            cout << val << " ";
        }
        cout << "\n";
    }
    cout << "\n";
}

void update_best(int num_car_using){
    int true_f = f;
    for (int i = 1; i <= num_car_using; i++){
        true_f += c[x[i].back()][0];
    }
    if (fbest > true_f){
        x_best.resize(num_car_using+1);
        up(i,1,num_car_using){
            x_best[i].clear();
            x_best[i] = x[i];
        }
        fbest = true_f;
    }
//    DEBUG(num_car_using);
}

void TRY_X(int current_car, int num_car_using, int num_node_visited){
    if (num_node_visited == n){
        update_best(num_car_using);
        return;
    }

    if (current_car > num_car_using) return;

    if (f + (n + num_car_using - num_node_visited)*cmin >= fbest) return;

//    cout << "NUM_NODE_VISITED: " << num_node_visited << "\n";
//    DEBUG(num_car_using);

    TRY_X(current_car+1, num_car_using, num_node_visited);

    for (int v = 1; v <= n; v++){
        if (!can_go_to(current_car, v)) continue;

        f += c[x[current_car].back()][v];
        x[current_car].push_back(v);
        visited[v] = true;
        loaded[current_car] += d[v];

        TRY_X(current_car, num_car_using, num_node_visited+1);

        loaded[current_car] -= d[v];
        visited[v] = false;
        x[current_car].pop_back();
        f -= c[x[current_car].back()][v];
    }
}

void TRY_Y(int current_car, int num_car_using, int num_node_visited){
    if (current_car > num_car_using){
        TRY_X(1, num_car_using, num_node_visited);
        return;
    }

    if (f + (n + num_car_using - num_node_visited)*cmin >= fbest) return;

    for (int start_point = x[current_car-1].back()+1; start_point <= n; start_point++){
        if (!can_go_to(current_car, start_point)) continue;

        x[current_car].push_back(start_point);
        visited[start_point] = true;
        loaded[current_car] += d[start_point];
        f += c[0][start_point];

        TRY_Y(current_car+1, num_car_using, num_node_visited+1);

        f -= c[0][start_point];
        loaded[current_car] -= d[start_point];
        visited[start_point] = false;
        x[current_car].pop_back();
    }
}

signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    #define Task "A"
    if (fopen(Task".inp", "r")){
        freopen(Task".inp", "r", stdin);
        freopen(Task".out", "w", stdout);
    }

    int remain_packages = 0;
    cin >> n >> K >> Q;
    up(i,1,n){
        cin >> d[i];
        remain_packages += d[i];
    }
    up(i,0,n) up(j,0,n) {
        cin >> c[i][j];
        if (i != j) {
            if (c[i][j] <= cmin){
                cmin2 = cmin;
                cmin = c[i][j];
            }
            else if (c[i][j] <= cmin2){
                cmin2 = c[i][j];
            }
//            cmin = min(cmin, c[i][j]);
        }
    }

    cmin = (cmin + cmin2)/2;

    x[0].push_back(0);
    for (int num_car_using = 1; num_car_using <= K; num_car_using++){
//        cout << "PHASE " << num_car_using << "\n";
        if (Q*num_car_using < remain_packages) continue;
        TRY_Y(1, num_car_using, 0);
//        cout << "\n";
    }

    cout << fbest << "\n";


//    for (int i = 1; i < (int)x_best.size(); i++){
//        cout << "BY CAR " << i << ": ";
//        for (auto u : x_best[i]) cout << u << " ";
//        cout << "\n";
//    }
}