Fire Extinguishing Optimization

Fusu was deeply moved by the story of the painter and the koi. In order to let them continue living together, he decided to return to the burning courtyard and extinguish the fire. The painter's courtyard can be abstracted as a directed graph with n vertices and m edges. Each vertex represents a burning location and has an associated fire power (weight). A directed edge \(\langle u,v\rangle\) indicates that the fire can spread from vertex \(u\) to vertex \(v\).

At any moment, Fusu is only allowed to extinguish the fire at a vertex that currently has at least one incoming edge from a vertex that is not extinguished. When a vertex is chosen and its fire extinguished, you gain its fire power, and that vertex along with all its outgoing edges are removed from the graph. Note however that the remaining vertices keep their original fire power; only the in‐degrees may change due to the removal of edges.

Fusu can extinguish the fire at at most \(k\) vertices. In this problem, you are given a directed graph with vertex weights. Initially only those vertices with at least one incoming edge (i.e. not a source) are eligible for extinguishing. You can choose at most \(k\) vertices (in some order) such that when a vertex is removed, it has at least one incoming edge from a vertex that is still present. Equivalently, if we denote by \(X\) the set of vertices you extinguish, then for every vertex \(v \in X\) it must hold that \[ \exists u \notin X \text{ such that } (u,v) \text{ is an edge.} \] Your task is to maximize the total fire power (i.e. the sum of weights) of the extinguished vertices.

Simplified Problem Statement:
Given a directed graph with n vertices and m edges, and each vertex has a weight. At any moment you may choose any vertex that currently has a nonzero in-degree, gain its weight, and remove it along with all its outgoing edges. You can do this at most \(k\) times. Compute the maximum total weight you can obtain.

inputFormat

The input begins with three integers n m k (where 1 ≤ n ≤ 20, m ≥ 0, and 1 ≤ k ≤ n). The next line contains n integers representing the weights of the vertices (1-indexed). Each of the next m lines contains two integers u v, representing a directed edge from vertex u to vertex v.

outputFormat

Output a single integer: the maximum total fire power that can be extinguished by selecting at most k vertices under the given rules.

sample

4 4 2
1 2 3 4
1 2
2 3
1 3
3 4

6