//BISMILLAHIRRAHMANIRRAHIM//#pragma warning (disable: 4786)//#pragma comment (linker, "/STACK:0x800000")//#define _CRT_SECURE_NO_WARNINGS 1#include <cassert>#include <cctype>#include <climits>#include <cmath>#include <cstdio>#include <cstdlib>#include <cstring>#include <iostream>#include <sstream>#include <iomanip>#include <string>#include <vector>#include <list>#include <set>#include <map>#include <stack>#include <queue>#include <algorithm>#include <iterator>#include <utility>using namespace std;template< class T > T _abs(T n) { return (n < 0 ? -n : n); }template< class T > T _max(T a, T b) { return (!(a < b) ? a : b); }template< class T > T _min(T a, T b) { return (a < b ? a : b); }template< class T > T sq(T x) { return x * x; }#define ALL(p) p.begin(),p.end()#define MP(x, y) make_pair(x, y)#define SET(p) memset(p, -1, sizeof(p))#define CLR(p) memset(p, 0, sizeof(p))#define MEM(p, v) memset(p, v, sizeof(p))#define CPY(d, s) memcpy(d, s, sizeof(s))#define SZ(c) (int)c.size()#define PB(x) push_back(x)#define ff first#define ss second#define i64 long long#define ld long double#define pii pair< int, int >#define psi pair< string, int >const double EPS = 1e-9;const int INF = 0x7f7f7f7f;const int MAXN = 2048;const int MAXE = 1 << 20;int src, snk, nNode, nEdge;int fin[MAXN], pre[MAXN], dist[MAXN];int cap[MAXE], cost[MAXE], next[MAXE], to[MAXE], from[MAXE];inline void init(int _src, int _snk, int nodes) {SET(fin);nNode = nodes, nEdge = 0;src = _src, snk = _snk;}inline void addEdge(int u, int v, int _cap, int _cost) {from[nEdge] = u, to[nEdge] = v, cap[nEdge] = _cap, cost[nEdge] = _cost;next[nEdge] = fin[u], fin[u] = nEdge++;from[nEdge] = v, to[nEdge] = u, cap[nEdge] = 0, cost[nEdge] = -(_cost);next[nEdge] = fin[v], fin[v] = nEdge++;}bool bellman() {int iter, u, v, i;bool flag = true;MEM(dist, 0x7f);SET(pre);dist[src] = 0;for(iter = 1; iter < nNode && flag; iter++) {flag = false;for(u = 0; u < nNode; u++) {for(i = fin[u]; i >= 0; i = next[i]) {v = to[i];if(cap[i] && dist[v] > dist[u] + cost[i]) {dist[v] = dist[u] + cost[i];pre[v] = i;flag = true;}}}}return (dist[snk] < INF);}int mcmf(int &fcost, int q) {int netflow, i, bot, u;netflow = fcost = 0;while(q-- && bellman()) {bot = INF;for(u = pre[snk]; u >= 0; u = pre[from[u]]) bot = min(bot, cap[u]);for(u = pre[snk]; u >= 0; u = pre[from[u]]) {cap[u] -= bot;cap[u^1] += bot;fcost += bot * cost[u];}netflow += bot;}return netflow;}int main() {int n, e, q, u, v, f, c, i;int w[1024];while(scanf("%d", &n) == 1) { init(1, 2*n, 2*n); for(i = 1; i <= n; i++) { scanf("%d", &w[i]); } scanf("%d", &e); for(i = 0; i < e; i++) { scanf("%d %d", &u, &v); addEdge(2*u, 2*v-1, INF, 0); } scanf("%d", &q); if(q == 0) { printf("0n"); continue; } if(n == 1) { printf("%dn", w[1]); continue; } for(i = 1; i <= n; i++) { addEdge(2*i - 1, 2*i, (i > 1 && i < n) ? INF : q, 0); if(i > 1 && i < n) addEdge(2*i - 1, 2*i, 1, -w[i]); } f = mcmf(c, q); printf("%dn", -c + w[1] + w[n]);}return 0;}
