Problem: problem

AOR Ika-chan is taking a class where grades are determined only by the score of the $ N $ report. AOR Ika-chan has $ M $ friends who are taking the same class, and if you have a report on a theme that you are not good at, you can get the same score as that friend by copying the report of a friend who is good at that theme. .. However, the teacher should not be aware that you are copying someone else's report, so you have to finish the report yourself, not copying someone else's report at least $ K $ out of $ N $ times. Also, AOR Ika didn't want to bother her friends, so she decided to copy the report to her friend $ i $ less than $ T_i $ times. Answer the maximum total score that AOR Ika can get when given the score when AOR Ika finishes the report by herself and the score when her friend finishes the report.



input

Input is given from standard input in the following format.

$ N \ M \ K $
$ a_1 \ \ cdots \ a_N $
$ b_ {11} \ \ cdots \ b_ {1N} $
$ \ vdots $
$ b_ {M1} \ \ cdots \ b_ {MN} $
$ T_1 \ \ cdots \ T_M $

$ a_i $ is the score when AOR Ika finishes the $ i $ th report, and $ b_ {ij} $ is the score when friend $ i $ finishes the $ j $ th report.

output

Output the maximum total score that AOR Ika can get. Also, output a line break at the end.

Example

Input

3 2 2
50 65 70
80 100 80
90 65 45
1 1


Output

225

Solution (in CPP):

Solution:
#include "bits/stdc++.h"
using namespace std;



#define REP(i,n) for(int i=0;i<(int)n;++i)
#define FOR(i,c) for(auto i=(c).begin();i!=(c).end();++i)
#define ALL(c) (c).begin(), (c).end()



typedef int Weight;
typedef int Cap;
const Weight W_INF = INT_MAX;
const Weight W_ZERO = 0;
const Cap C_INF = INT_MAX;
const Cap C_ZERO = 0;

struct Edge {
	int src, dst;
	Cap capacity;
	Weight cost;
	Edge(int src, int dst, const Cap& acap, const Weight& acost) :
		src(src), dst(dst), capacity(acap), cost(acost) {
	}
};
bool operator < (const Edge &e, const Edge &f) {
	return e.cost > f.cost;
}
typedef vector<Edge> Edges;
typedef vector<Edges> Graph;


#define RESIDUE(s,t) (capacity[s][t]-flow[s][t])
#define RCOST(u,v) (cost[u][v] + h[u] - h[v])

//??°?????????????????§???????????????????????¨?????????

//Graph &ag
//????????§???????????????(u, v, capacity, cost) ??????????????????(u, v, 0, -cost) ???????????°????????????????????¶?????????????????§????´???°????????§???????????°???????????????
//int s, int t
//?????????????§??????¨?????????
//?????????
//?????¨??¨????????????????????????
pair<Weight, Cap> minimumCostFlow(const Graph &ag, int s, int t) {
	//check???????´???°??????????????£???????????????
	Graph g(ag);
	for (int i = 0; i < ag.size(); ++i) {
		for (int j = 0; j < ag[i].size(); ++j) {
			int d = ag[i][j].dst;
			int s = ag[i][j].src;

			bool ok = false;
			for (int k = 0; k < ag[d].size(); ++k) {
				if (ag[d][k].src == s) {
					ok = true;
					break;
				}
			}
			if (!ok) {
				g[d].push_back(Edge(d, s, C_ZERO, -ag[i][j].cost));
			}
		}
	}
	const int n = g.size();
	vector<vector<Cap>> capacity(n, vector<Cap>(n)), flow(n, vector<Cap>(n));
	vector<vector<Weight>>cost(n, vector<Weight>(n));
	for (int u = 0; u < n; ++u) {
		for (auto e : g[u]) {
			capacity[e.src][e.dst] = capacity[e.src][e.dst] + e.capacity;
			cost[e.src][e.dst] = cost[e.src][e.dst] + e.cost;
		}
	}
	pair<Weight, Cap> total; // (cost, flow)
	vector<Weight> h(n);

	for (Cap F = C_INF; F > 0; ) { // residual flow
		vector<Weight> d(n, W_INF); d[s] = W_ZERO;
		vector<int> p(n, -1);
		priority_queue<Edge> Q; // "e < f" <=> "e.cost > f.cost"
		for (Q.push(Edge(-2, s, C_ZERO, W_ZERO)); !Q.empty(); ) {
			Edge e = Q.top(); Q.pop();
			if (p[e.dst] != -1) continue;
			p[e.dst] = e.src;
			FOR(f, g[e.dst]) {
				if (RESIDUE(f->src, f->dst) > 0) {
					if (d[f->dst] > d[f->src] + RCOST(f->src, f->dst)) {
						d[f->dst] = d[f->src] + RCOST(f->src, f->dst);
						Q.push(Edge(f->src, f->dst, 0, d[f->dst]));
					}
				}
			}
		}
		if (p[t] == -1) {
			break;
		}

		Cap f = F;
		for (int u = t; u != s; u = p[u]) {
			f = min(f, RESIDUE(p[u], u));
		}
		for (int u = t; u != s; u = p[u]) {
			total.first = total.first + f * cost[p[u]][u];
			flow[p[u]][u] = flow[p[u]][u] + f; flow[u][p[u]] = flow[u][p[u]] - f;
		}
		F = F - f;
		total.second = total.second + f;
		for (int u = 0; u < n; ++u) {
			h[u] = h[u] + d[u];
		}
	}
	return total;
}
void add_edge(Graph&g, const int from, const int to, const Cap& cap, const Weight& weight) {
	g[from].push_back(Edge(from, to, cap, weight));
}

int main() {
	int N, M, K; cin >> N >> M >> K;
	vector<int>myscores(N);
	vector<vector<int>>friscores(M, vector<int>(N));
	vector<int>cancheat(M);
	for (int i = 0; i < N; ++i) {
		cin >> myscores[i];
	}
	for (int i = 0; i < M; ++i) {
		for (int j = 0; j < N; ++j) {
			cin >> friscores[i][j];
		}
	}
	for (int i = 0; i < M; ++i) {
		cin >> cancheat[i];
	}

	const int start = 0;
	const int report = start + 1;
	const int my = report + N;
	const int fr_in = my + 1;
	const int fr_assemble = fr_in + M;
	const int goal = fr_assemble + 1;
	Graph g(goal+1);
	for (int i = 0; i < N; ++i) {
		add_edge(g, start, report + i, 1, 0);
	}
	for (int i = 0; i < N; ++i) {
		for (int j = 0; j < M; ++j) {
			add_edge(g, report + i, fr_in + j, 1, 100-friscores[j][i]);
		}
		add_edge(g, report + i, my, 1, 100-myscores[i]);
	}
	for (int j = 0; j < M; ++j) {
		add_edge(g, fr_in + j, fr_assemble, cancheat[j], 0);
	}
	add_edge(g, fr_assemble,goal, N - K, 0);
	add_edge(g, my, goal, N, 0);
	auto ans = minimumCostFlow(g, start, goal);
	cout << 100*N-ans.first<< endl;
	return 0;
}