gistfile1.hh

#include <iostream>
#include <vector>
#include <cmath>
#include <stdio.h>
#include <deque>

using namespace std;

const int INF = (1 << 31) - 1;

struct Edge {
	int able;
	int cost;
	Edge* brother;
	int vert;

	Edge(int able, int cost, int vert) {
		this -> able = able;
		this -> cost = cost;
		this -> vert = vert;
	}
};

//vector<Edge*> graph[700];

int next[200000];
int first[700];
Edge* graph[200000];

int cnt;

int n, m;

int dist[700]; // Âåëè÷èíà êðàò÷àéøåãî ðàññòîÿíèÿ äî i-îé âåðøèíû.
int from[700]; // Èç êàêîé âåðøèíû ïðèøëè â i-óþ âåðøèíû.
Edge* fromEdge[700]; // Èç êàêîãî ðåáðà ïðèøëè.
bool mark[700]; // Ïîìå÷åíà ëè âåðøèíà â àëãîðèòìå.
int able[700]; //Ñêîëüêî íåôòè ìîæíî ïðîïóñòèòü èç èñòîêà â i-óþ âåðøèíó.
int type[700];

deque<int> q;


long long res;

int getMinVertex() {
	int res = -1;
	int curDist = INF;
	for (int i = 0; i < n + m + 2; i++) {
		if (dist[i] < curDist && !mark[i]) {
			res = i;
			curDist = dist[i];
		}
	}
}

void relaxVertex(int vert) {
	mark[vert] = true;
	for (int i = first[vert]; i != -1; i = next[i]) {
		Edge* e = graph[i];
		if (e -> able > 0 && dist[e -> vert] > dist[vert] + e -> cost) {
			dist[e -> vert]  = dist[vert] + e -> cost;
			from[e -> vert] = vert;
			fromEdge[e -> vert] = e;
			able[e -> vert] = min(e -> able, able[vert]);
		}
	}
}

void initDijkstra() {
	for (int i = 0; i < n + m + 2; i++) {
		dist[i] = INF;
		mark[i] = false;
		able[i] = INF;
		type[i] = 0;
	}
	dist[0] = 0;
}

bool runDijkstra() {
	initDijkstra();
	int vert;
	while ( (vert = getMinVertex()) != -1) {
		relaxVertex(vert);
	}
	return dist[1] != INF;
}

void fillPath() {
	int cur = 1;
	long long sumCost = 0;
	while (cur != 0) {
		Edge* e = fromEdge[cur];
		sumCost += e -> cost;
		e -> able -= able[1];
		e -> brother -> able += able[1];
		cur = from[cur];
	}
	res += sumCost * able[1];
}
	

void addEdge(int from, int to, int cost, int able) {
	Edge* e = new Edge(able, cost, to);
	Edge* broth = new Edge(0, -cost, from);
	e -> brother = broth;
	broth -> brother = e;
	//graph[from].push_back(e);
	//graph[to].push_back(broth);
	next[cnt] = first[from];
	first[from] = cnt;
	graph[cnt++] = e;
	next[cnt] = first[to];
	first[to] = cnt;
	graph[cnt++] = broth;

}

void readData() {
	scanf("%d%d",&n, &m);
	for (int i = 0; i < n; i++) {
		int able;
		scanf("%d", &able);
		addEdge(0,i + 2, 0, able);
	}
	for (int i = 0; i < m; i++) {
		int able;
		scanf("%d", &able);
		addEdge(2 + n + i, 1, 0, able);
	}
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			int cost;
			scanf("%d", &cost);
			addEdge(i + 2, j + n + 2, cost, INF);
		}
	}
}
//
//void printGraph() {
//	for (int i = 0; i < n + m + 2; i++) {
//		printf("%d\n", i);
//		for (int j = 0; j < graph[i].size(); j++) {
//			Edge* e = graph[i][j];
//			printf("ver: %d, cost: %d, able: %d\n", e -> vert, e -> cost, e -> able);
//		}
//		printf("\n");
//	}
//}


int main() {
	freopen("input.txt", "r", stdin);
	freopen("output.txt", "w", stdout);
	memset(next, -1, sizeof (next));
	memset(first, -1, sizeof (first));
	readData();
	while (runDijkstra()) {
		fillPath();
	}
	cout << res << endl;
	//printGraph();
	fclose(stdout);
	return 0;
}