Untitled

#include <iostream>
#include <vector>
#include <queue>

struct edge_type {
    int64_t flow{ 0 };
    int64_t capacity;

    edge_type(int64_t capacity): capacity(capacity) {}
};

struct vertex_type {
    uint32_t to;
    uint32_t edge;

    vertex_type(uint32_t to, uint32_t edge): to(to), edge(edge) {}
};

struct graph_type {
    uint32_t s;
    uint32_t t;

    std::vector<std::vector<vertex_type>> vertexes;
    std::vector<edge_type> edges;
    std::vector<int> level;
    std::vector<uint32_t> path;
    std::vector<uint32_t> queue;

    void add_edge(uint32_t from, uint32_t to, int64_t capacity) {
        uint32_t direct_edge = edges.size();
        edges.emplace_back(capacity);
        vertexes[from].emplace_back(to, direct_edge);

        uint32_t reverse_edge = edges.size();
        edges.emplace_back(0);
        vertexes[to].emplace_back(from, reverse_edge);
    }

    bool bfs() {
        uint32_t r = 0;
        uint32_t l = 0;
        queue[r] = s;
        ++r;

        std::fill(level.begin(), level.end(), -1);
        level[s] = 0;

        while (l < r) {
            uint32_t v = queue[l];
            ++l;

            for (const auto& vertex : vertexes[v]) {
                const auto& edge = edges[vertex.edge];

                if (level[vertex.to] == -1 
                        && (edge.capacity - edge.flow) > 0) {

                    queue[r] = vertex.to;
                    ++r;

                    level[vertex.to] = level[v] + 1;
                }
            }
        }

        return level[t] != -1;
    }

    int64_t push_flow (uint32_t v, int64_t flow) {
        if (flow == 0 || v == t) {
            return flow;
        }

        uint32_t vertex_count = vertexes[v].size();

        for (auto& i = path[v]; i < vertex_count; ++i) {
            const auto& vertex  = vertexes[v][i];
            auto& edge = edges[vertex.edge];

            if (level[v] + 1 != level[vertex.to] 
                || (edge.capacity - edge.flow) < 1) {
                continue;
            }

            int64_t pushed_flow = push_flow(vertex.to, std::min(flow, edge.capacity - edge.flow));
            
            if (pushed_flow == 0) {
                continue;
            }
    
            edge.flow += pushed_flow;
            edges[vertex.edge ^ 1].flow -= pushed_flow;
            return pushed_flow;
        }

        return 0;
    }

    int64_t dinic() {
        int64_t flow = 0;
        
        while (true) {
            if (!bfs()) {
                break;
            }

            int64_t pushed_flow = 0;
            std::fill(path.begin(), path.end(), 0);

            do {
                pushed_flow = push_flow(s, INT64_MAX);

                if (pushed_flow > 0) {
                    flow += pushed_flow;
                }
            } while (pushed_flow != 0);
        }

        return flow;
    }

};


// void stdio_init(graph_type& graph) {
//     int n, m;
//     std::cin >> n;
//     std::cin >> m;

//     graph.level.resize(n, 0);
//     graph.queue.resize(n, 0);
//     graph.path.resize(n, 0);

//     graph.s = 0;
//     graph.t = n - 1;
//     graph.vertexes.resize(n, std::vector<vertex_type>());

//     int from, to, capacity;
//     for (int i = 0; i < m; ++i) {
//         std::cin >> from;
//         std::cin >> to;
//         std::cin >> capacity;

//         graph.add_edge(from - 1, to - 1, capacity);
//     }
// }

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);


    int n, k;
    std::cin >> n;
    std::cin >> k;

    int vertex_count = 2*n + 2;
    graph_type graph;
    graph.level.resize(vertex_count, 0);
    graph.queue.resize(vertex_count, 0);
    graph.path.resize(vertex_count, 0);

    graph.s = 0;
    graph.t = vertex_count - 1;
    graph.vertexes.resize(vertex_count, std::vector<vertex_type>());

    int64_t capacity;
    for (int i = 0; i < n; ++i) {
        std::cin >> capacity;
        graph.add_edge(0, i + 1, capacity);
    }

    uint32_t vertex_number = n + 1;
    uint32_t t = vertex_count - 1;

    for (; vertex_number < t; ++vertex_number) {
        std::cin >> capacity;
        graph.add_edge(vertex_number, t, capacity);
    }

    uint32_t from, to;
    for (int i = 0; i < k; ++i) {
        std::cin >> from;
        std::cin >> to;

        to += n;

        graph.add_edge(from, to, 1000000);
    } 


    std::cout << graph.dinic() << "\n";

    return 0;
}