#include <bits/stdc++.h>
using namespace std;
const int POCET_MIEST = 1000;
const int ZDROJ = POCET_MIEST, ODTOK = POCET_MIEST+1;
const long long NEKONECNO = 1LL << 60;
struct edge {
int source, destination;
long long capacity, residue, cost;
edge(int s, int d, long long cap, long long res, long long cost)
: source(s), destination(d), capacity(cap), residue(res), cost(cost) { }
};
void add_arc(vector<edge> &edges, int source, int destination, long long capacity, long long cost) {
edges.push_back( edge(source,destination,capacity,capacity,cost) );
edges.push_back( edge(destination,source,capacity,0,-cost) );
}
int main() {
vector<long long> mam_losov(POCET_MIEST); for (auto &x : mam_losov) cin >> x;
vector<long long> chcem_losov(POCET_MIEST); for (auto &x : chcem_losov) cin >> x;
long long dokopy_losov = accumulate( mam_losov.begin(), mam_losov.end(), 0LL );
vector<edge> edges;
// hrany zo zdroja + hrany do odtoku
for (int i=0; i<POCET_MIEST; ++i) add_arc( edges, ZDROJ, i, mam_losov[i], 0 );
for (int i=0; i<POCET_MIEST; ++i) add_arc( edges, i, ODTOK, chcem_losov[i], 0 );
// hrany medzi jednotlivymi mestami
for (int a=0; a<POCET_MIEST; ++a) for (int b=0; b<POCET_MIEST; ++b) {
long long c;
cin >> c;
if (a != b) add_arc( edges, a, b, dokopy_losov, c );
}
// dokola zlepsujeme tok, az kym sa to uz niekedy neda
long long velkost_toku = 0, cena_toku = 0;
while (true) {
// hladame najlacnejsiu zlepsujucu cestu algoritmom Bellmana a Forda
// (nie Dijkstra, lebo sice nemame zaporne cykly, ale mozeme mat zaporne hrany)
vector<long long> min_cena_cesty (POCET_MIEST+2, NEKONECNO);
vector<int> odkial(POCET_MIEST+2, -1);
min_cena_cesty[ZDROJ] = 0;
while (true) {
bool zmena = false;
for (unsigned i=0; i<edges.size(); ++i) {
edge &e = edges[i];
if (e.residue == 0) continue;
if (min_cena_cesty[e.destination] > min_cena_cesty[e.source] + e.cost) {
zmena = true;
min_cena_cesty[e.destination] = min_cena_cesty[e.source] + e.cost;
odkial[e.destination] = i;
}
}
if (!zmena) break;
}
// ak uz ziadna zlepsujuca cesta neexistovala, hotovo
if (min_cena_cesty[ODTOK] == NEKONECNO) break;
// prejdeme po zlepsujucej ceste a zozbierame hrany ktore ju tvoria
vector<int> hrany_na_ceste;
{
int kde = ODTOK;
while (kde != ZDROJ) {
hrany_na_ceste.push_back( odkial[kde] );
kde = edges[odkial[kde]].source;
}
}
// zistime, o kolko vieme zlepsit tok
long long kapacita_cesty = NEKONECNO;
for (int h : hrany_na_ceste) kapacita_cesty = min( kapacita_cesty, edges[h].residue );
// znova prejdeme po zlepsujucej ceste a upravime tok (aj na dualnych hranach)
velkost_toku += kapacita_cesty;
for (int h : hrany_na_ceste) {
cena_toku += kapacita_cesty * edges[h].cost;
edges[h].residue -= kapacita_cesty;
edges[h^1].residue += kapacita_cesty;
}
}
assert( velkost_toku == dokopy_losov );
cout << cena_toku << endl;
}
I2luY2x1ZGUgPGJpdHMvc3RkYysrLmg+CnVzaW5nIG5hbWVzcGFjZSBzdGQ7Cgpjb25zdCBpbnQgUE9DRVRfTUlFU1QgPSAxMDAwOwpjb25zdCBpbnQgWkRST0ogPSBQT0NFVF9NSUVTVCwgT0RUT0sgPSBQT0NFVF9NSUVTVCsxOwpjb25zdCBsb25nIGxvbmcgTkVLT05FQ05PID0gMUxMIDw8IDYwOwoKc3RydWN0IGVkZ2UgeyAKICAgIGludCBzb3VyY2UsIGRlc3RpbmF0aW9uOwogICAgbG9uZyBsb25nIGNhcGFjaXR5LCByZXNpZHVlLCBjb3N0OwogICAgZWRnZShpbnQgcywgaW50IGQsIGxvbmcgbG9uZyBjYXAsIGxvbmcgbG9uZyByZXMsIGxvbmcgbG9uZyBjb3N0KSAKICAgICAgICA6IHNvdXJjZShzKSwgZGVzdGluYXRpb24oZCksIGNhcGFjaXR5KGNhcCksIHJlc2lkdWUocmVzKSwgY29zdChjb3N0KSB7IH0KfTsKCnZvaWQgYWRkX2FyYyh2ZWN0b3I8ZWRnZT4gJmVkZ2VzLCBpbnQgc291cmNlLCBpbnQgZGVzdGluYXRpb24sIGxvbmcgbG9uZyBjYXBhY2l0eSwgbG9uZyBsb25nIGNvc3QpIHsKICAgIGVkZ2VzLnB1c2hfYmFjayggZWRnZShzb3VyY2UsZGVzdGluYXRpb24sY2FwYWNpdHksY2FwYWNpdHksY29zdCkgKTsKICAgIGVkZ2VzLnB1c2hfYmFjayggZWRnZShkZXN0aW5hdGlvbixzb3VyY2UsY2FwYWNpdHksMCwtY29zdCkgKTsKfQoKaW50IG1haW4oKSB7CiAgICB2ZWN0b3I8bG9uZyBsb25nPiBtYW1fbG9zb3YoUE9DRVRfTUlFU1QpOyAgIGZvciAoYXV0byAmeCA6IG1hbV9sb3NvdikgICBjaW4gPj4geDsKICAgIHZlY3Rvcjxsb25nIGxvbmc+IGNoY2VtX2xvc292KFBPQ0VUX01JRVNUKTsgZm9yIChhdXRvICZ4IDogY2hjZW1fbG9zb3YpIGNpbiA+PiB4OwoKICAgIGxvbmcgbG9uZyBkb2tvcHlfbG9zb3YgPSBhY2N1bXVsYXRlKCBtYW1fbG9zb3YuYmVnaW4oKSwgbWFtX2xvc292LmVuZCgpLCAwTEwgKTsKCiAgICB2ZWN0b3I8ZWRnZT4gZWRnZXM7CgogICAgLy8gaHJhbnkgem8gemRyb2phICsgaHJhbnkgZG8gb2R0b2t1CiAgICBmb3IgKGludCBpPTA7IGk8UE9DRVRfTUlFU1Q7ICsraSkgYWRkX2FyYyggZWRnZXMsIFpEUk9KLCBpLCBtYW1fbG9zb3ZbaV0sIDAgKTsKICAgIGZvciAoaW50IGk9MDsgaTxQT0NFVF9NSUVTVDsgKytpKSBhZGRfYXJjKCBlZGdlcywgaSwgT0RUT0ssIGNoY2VtX2xvc292W2ldLCAwICk7CgogICAgLy8gaHJhbnkgbWVkemkgamVkbm90bGl2eW1pIG1lc3RhbWkKICAgIGZvciAoaW50IGE9MDsgYTxQT0NFVF9NSUVTVDsgKythKSBmb3IgKGludCBiPTA7IGI8UE9DRVRfTUlFU1Q7ICsrYikgewogICAgICAgIGxvbmcgbG9uZyBjOwogICAgICAgIGNpbiA+PiBjOwogICAgICAgIGlmIChhICE9IGIpIGFkZF9hcmMoIGVkZ2VzLCBhLCBiLCBkb2tvcHlfbG9zb3YsIGMgKTsKICAgIH0KCiAgICAvLyBkb2tvbGEgemxlcHN1amVtZSB0b2ssIGF6IGt5bSBzYSB0byB1eiBuaWVrZWR5IG5lZGEKICAgIGxvbmcgbG9uZyB2ZWxrb3N0X3Rva3UgPSAwLCBjZW5hX3Rva3UgPSAwOwoKICAgIHdoaWxlICh0cnVlKSB7CiAgICAgICAgLy8gaGxhZGFtZSBuYWpsYWNuZWpzaXUgemxlcHN1anVjdSBjZXN0dSBhbGdvcml0bW9tIEJlbGxtYW5hIGEgRm9yZGEKICAgICAgICAvLyAobmllIERpamtzdHJhLCBsZWJvIHNpY2UgbmVtYW1lIHphcG9ybmUgY3lrbHksIGFsZSBtb3plbWUgbWF0IHphcG9ybmUgaHJhbnkpCiAgICAgICAgdmVjdG9yPGxvbmcgbG9uZz4gbWluX2NlbmFfY2VzdHkgKFBPQ0VUX01JRVNUKzIsIE5FS09ORUNOTyk7CiAgICAgICAgdmVjdG9yPGludD4gb2RraWFsKFBPQ0VUX01JRVNUKzIsIC0xKTsKICAgICAgICBtaW5fY2VuYV9jZXN0eVtaRFJPSl0gPSAwOwogICAgICAgIHdoaWxlICh0cnVlKSB7CiAgICAgICAgICAgIGJvb2wgem1lbmEgPSBmYWxzZTsKICAgICAgICAgICAgZm9yICh1bnNpZ25lZCBpPTA7IGk8ZWRnZXMuc2l6ZSgpOyArK2kpIHsKICAgICAgICAgICAgICAgIGVkZ2UgJmUgPSBlZGdlc1tpXTsKICAgICAgICAgICAgICAgIGlmIChlLnJlc2lkdWUgPT0gMCkgY29udGludWU7CiAgICAgICAgICAgICAgICBpZiAobWluX2NlbmFfY2VzdHlbZS5kZXN0aW5hdGlvbl0gPiBtaW5fY2VuYV9jZXN0eVtlLnNvdXJjZV0gKyBlLmNvc3QpIHsKICAgICAgICAgICAgICAgICAgICB6bWVuYSA9IHRydWU7CiAgICAgICAgICAgICAgICAgICAgbWluX2NlbmFfY2VzdHlbZS5kZXN0aW5hdGlvbl0gPSBtaW5fY2VuYV9jZXN0eVtlLnNvdXJjZV0gKyBlLmNvc3Q7CiAgICAgICAgICAgICAgICAgICAgb2RraWFsW2UuZGVzdGluYXRpb25dID0gaTsKICAgICAgICAgICAgICAgIH0KICAgICAgICAgICAgfQogICAgICAgICAgICBpZiAoIXptZW5hKSBicmVhazsKICAgICAgICB9CgogICAgICAgIC8vIGFrIHV6IHppYWRuYSB6bGVwc3VqdWNhIGNlc3RhIG5lZXhpc3RvdmFsYSwgaG90b3ZvCiAgICAgICAgaWYgKG1pbl9jZW5hX2Nlc3R5W09EVE9LXSA9PSBORUtPTkVDTk8pIGJyZWFrOwoKICAgICAgICAvLyBwcmVqZGVtZSBwbyB6bGVwc3VqdWNlaiBjZXN0ZSBhIHpvemJpZXJhbWUgaHJhbnkga3RvcmUganUgdHZvcmlhCiAgICAgICAgdmVjdG9yPGludD4gaHJhbnlfbmFfY2VzdGU7CiAgICAgICAgewogICAgICAgICAgICBpbnQga2RlID0gT0RUT0s7CiAgICAgICAgICAgIHdoaWxlIChrZGUgIT0gWkRST0opIHsKICAgICAgICAgICAgICAgIGhyYW55X25hX2Nlc3RlLnB1c2hfYmFjayggb2RraWFsW2tkZV0gKTsgCiAgICAgICAgICAgICAgICBrZGUgPSBlZGdlc1tvZGtpYWxba2RlXV0uc291cmNlOyAKICAgICAgICAgICAgfQogICAgICAgIH0KCiAgICAgICAgLy8gemlzdGltZSwgbyBrb2xrbyB2aWVtZSB6bGVwc2l0IHRvawogICAgICAgIGxvbmcgbG9uZyBrYXBhY2l0YV9jZXN0eSA9IE5FS09ORUNOTzsKICAgICAgICBmb3IgKGludCBoIDogaHJhbnlfbmFfY2VzdGUpIGthcGFjaXRhX2Nlc3R5ID0gbWluKCBrYXBhY2l0YV9jZXN0eSwgZWRnZXNbaF0ucmVzaWR1ZSApOwoKICAgICAgICAvLyB6bm92YSBwcmVqZGVtZSBwbyB6bGVwc3VqdWNlaiBjZXN0ZSBhIHVwcmF2aW1lIHRvayAoYWogbmEgZHVhbG55Y2ggaHJhbmFjaCkKICAgICAgICB2ZWxrb3N0X3Rva3UgKz0ga2FwYWNpdGFfY2VzdHk7CiAgICAgICAgZm9yIChpbnQgaCA6IGhyYW55X25hX2Nlc3RlKSB7CiAgICAgICAgICAgIGNlbmFfdG9rdSArPSBrYXBhY2l0YV9jZXN0eSAqIGVkZ2VzW2hdLmNvc3Q7CiAgICAgICAgICAgIGVkZ2VzW2hdLnJlc2lkdWUgLT0ga2FwYWNpdGFfY2VzdHk7CiAgICAgICAgICAgIGVkZ2VzW2heMV0ucmVzaWR1ZSArPSBrYXBhY2l0YV9jZXN0eTsKICAgICAgICB9CiAgICB9CiAgICBhc3NlcnQoIHZlbGtvc3RfdG9rdSA9PSBkb2tvcHlfbG9zb3YgKTsKICAgIGNvdXQgPDwgY2VuYV90b2t1IDw8IGVuZGw7Cn0=