y2018-4-1-C

#include <iterator>
#include <iostream>
#include <vector>
#include <algorithm>
#include <set>

#pragma warning(disable : 4018)

#define FILL(A, c) std::generate((A).begin(), (A).end(), []() { return (c); })
#define SORT(A, c) std::sort((A).begin(), (A).end(), (c))
#define FIND(A, c) std::find((A).begin(), (A).end(), (c))

typedef unsigned uint;
typedef std::vector<bool> bvec;
typedef std::vector<unsigned> uivec;
typedef std::vector<int> ivec;
typedef std::pair<uint, uint> edge;
typedef std::vector<ivec> matr;

struct kun
{
  // public 'cause i'm too lazy to make getters
  matr G;
  static ivec weights;
  std::vector<edge> edges_list;
private:
  std::set<int> match_edges_;
  bvec verts_list_;
  static uint n, m;
  ivec matching_;
  bvec used_;
  uint match_weight_ = 0;

  friend std::ostream & operator<<(std::ostream & os, const kun & m_m)
  {
    os << m_m.match_weight_ << std::endl << m_m.match_edges_.size() << std::endl;

    for (const auto a : m_m.match_edges_)
      std::cout << a + 1 << " ";

    return os;
  }

  bool dfs(const uint v, const bool filtered)
  {
    if (used_[v] || filtered && !verts_list_[v])
      return false;

    used_[v] = true;

    for (const auto to : G[v])
      if (matching_[to] == -1 || dfs(matching_[to], filtered))
      {
        matching_[to] = v;
        return true;
      }
    return false;
  }

public:
  explicit kun(const uint _n = 0, const uint _m = 0) : G(_n + _m, ivec()), used_(_n + _m, false) { n = _n, m = _m; }

  kun & obtain_max_matching()
  {
    const auto cmp = [](const int & a, const int & b)->int { return weights[a] > weights[b]; };

    ivec order;
    matching_ = ivec(n + m, -1);
    verts_list_ = bvec(n + m, false);

    // left
    order.resize(0);
    for (uint i = 0; i < n; ++i) order.push_back(i);              // prepare order
    SORT(order, cmp);                                             // sort
    for (auto & us : G) SORT(us, cmp);                            // sort childs
    for (const auto i : order) FILL(used_, false), dfs(i, false); // Kuhn
    for (uint i = n; i < n + m; ++i)
      if (matching_[i] != -1)
        verts_list_[matching_[i]] = true;

    // right
    FILL(matching_, -1);
    order.resize(0);
    for (uint i = n; i < n + m; ++i) order.push_back(i);
    SORT(order, cmp);
    for (auto & us : G) SORT(us, cmp);
    for (const auto i : order) FILL(used_, false), dfs(i, false);
    for (uint i = 0; i < n; ++i)
      if (matching_[i] != -1)
        verts_list_[matching_[i]] = true;

    // all
    FILL(matching_, -1);
    for (uint i = 0; i < n + m; ++i)
      FILL(used_, false), dfs(i, true);

    // collect
    match_edges_.clear();
    for (int i = 0; i < n + m; ++i)
      if (matching_[i] != -1)
      {
        const auto tmp = get_edge_index(i);
        if (tmp != -1)
          match_edges_.insert(tmp);
      }

    match_weight_ = 0;
    for (const auto & e : match_edges_)
      if (e != -1)
        match_weight_ += weights[edges_list[e].first] + weights[edges_list[e].second + n];

    return *this;
  }

  [[nodiscard]] int get_edge_index(uint u) const
  {
    const edge e = edge(u, matching_[u] - n);

    for (uint i = 0; i < edges_list.size(); ++i)
      if (e == edges_list[i])
        return i;

    return -1;
  }
};
ivec kun::weights;
uint kun::n, kun::m;

int main()
{
  uint n = 0, m = 0, a = 0, b = 0, w = 0, e = 0;

  std::cin >> n >> m >> e;

  kun calculator(n, m);

  for (uint i = 0; i < n + m; i++)
    std::cin >> w, kun::weights.emplace_back(w);

  while (e--)
  {
    std::cin >> a >> b;
    calculator.edges_list.emplace_back(edge(--a, --b));
    calculator.G[a].emplace_back(b + n);
    calculator.G[b + n].emplace_back(a);
  }

  std::cout << calculator.obtain_max_matching();

  return 0;
}