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 <stdio.h>
#include <cmath>
#include <algorithm>
#include <cfloat>
#include <stack>
#include <queue>
#include <vector>
#include <string>
#include <iostream>
#include <set>
#include <map>
#include <time.h>
typedef long long int ll;
typedef unsigned long long int ull;
#define BIG_NUM 2000000000
#define MOD 1000000007
#define EPS 0.000000001
using namespace std;


#define NUM 250


//辺を表す構造体{行先、容量、コスト、逆辺のインデックス}
struct Edge{
	Edge(int arg_to,int arg_capacity,int arg_cost,int arg_rev_index){
		to = arg_to;
		capacity = arg_capacity;
		cost = arg_cost;
		rev_index = arg_rev_index;
	}

	int to,capacity,cost,rev_index;
};

int V; //頂点数
vector<Edge> G[NUM]; //グラフの隣接リスト表現
int dist[NUM]; //最短距離
int pre_node[NUM],pre_edge[NUM]; //直前の頂点と辺
int A[101],B[101][101],T[101];


//fromからtoへ向かう容量capacity,コストcostの辺をグラフに追加する
void add_edge(int from,int to,int capacity,int cost){
	G[from].push_back(Edge(to,capacity,cost,G[to].size()));
	G[to].push_back(Edge(from,0,-cost,G[from].size()-1));
}

//sourceからsinkへの、流量flowの最小費用流を求める
//流せない場合は-1を返す
int min_cost_flow(int source,int sink,int flow){
	int ret = 0;
	while(flow > 0){
		//ベルマンフォード方により、source-sink間最短経路を求める
		for(int i = 0; i < V; i++)dist[i] = BIG_NUM;
		dist[source] = 0;
		bool update = true;
		while(update){
			update = false;
			for(int node_id = 0; node_id < V; node_id++){
				if(dist[node_id] == BIG_NUM)continue;
				for(int i = 0; i < G[node_id].size(); i++){
					Edge &e = G[node_id][i];
					if(e.capacity > 0 && dist[e.to] > dist[node_id]+e.cost){
						dist[e.to] = dist[node_id]+e.cost; //node_idを経由した方が早い場合
						pre_node[e.to] = node_id;
						pre_edge[e.to] = i;
						update = true;
					}
				}
			}
		}

		if(dist[sink] == BIG_NUM){
			//これ以上流せない
			return -1;
		}

		//source-sink間最短路に沿って目いっぱい流す
		int tmp_flow = flow;
		for(int node_id = sink; node_id != source; node_id = pre_node[node_id]){
			tmp_flow = min(tmp_flow,G[pre_node[node_id]][pre_edge[node_id]].capacity);
		}
		flow -= tmp_flow;
		ret += tmp_flow*dist[sink];
		for(int node_id = sink; node_id != source; node_id = pre_node[node_id]){
			Edge &e = G[pre_node[node_id]][pre_edge[node_id]];
			e.capacity -= tmp_flow;
			G[node_id][e.rev_index].capacity += tmp_flow;
		}
	}
	return ret;
}

int main(){

	int N,M,K;
	scanf("%d %d %d",&N,&M,&K);

	for(int i = 0; i < N; i++)scanf("%d",&A[i]);

	for(int i = 0; i < M; i++){
		for(int k = 0; k < N; k++)scanf("%d",&B[i][k]);
	}

	for(int i = 0; i < M; i++)scanf("%d",&T[i]);

	int source = 0,sink = 1,first_branch = 2,second_branch = 3,me = 4,index = 5;

	add_edge(source,first_branch,N,0); //全体の流量をNに設定する
	add_edge(first_branch,me,N,0); //自分に最大N流せるようにする
	add_edge(first_branch,second_branch,N-K,0); //最大でも友達にはN-Kしか流せないようにする

	int friend_index[M],report_index[N];

	for(int i = 0; i < M; i++){
		friend_index[i] = index++;
		add_edge(second_branch,friend_index[i],T[i],0); //友達iに流量T[i]の辺を張る
	}

	for(int i = 0; i < N; i++){
		report_index[i] = index++;
		add_edge(report_index[i],sink,1,0); //レポートからsinkへ辺を張る
	}

	for(int i = 0; i < N; i++){
		add_edge(me,report_index[i],1,-A[i]); //自分からレポートに、負のコストの辺を張る
	}

	for(int i = 0; i < M; i++){
		for(int k = 0; k < N; k++){
			add_edge(friend_index[i],report_index[k],1,-B[i][k]); //友達iからレポートkに、負のコストの辺を張る
		}
	}

	V = index;

	printf("%d\n",-min_cost_flow(source,sink,N));

	return 0;
}