You are given a bipartite graph: the first part of this graph contains n_1 vertices, the second part contains n_2 vertices, and there are m edges. The graph can contain multiple edges.

Initially, each edge is colorless. For each edge, you may either leave it uncolored (it is free), paint it red (it costs r coins) or paint it blue (it costs b coins). No edge can be painted red and blue simultaneously.

There are three types of vertices in this graph — colorless, red and blue. Colored vertices impose additional constraints on edges' colours:

  * for each red vertex, the number of red edges indicent to it should be strictly greater than the number of blue edges incident to it; 
  * for each blue vertex, the number of blue edges indicent to it should be strictly greater than the number of red edges incident to it. 



Colorless vertices impose no additional constraints.

Your goal is to paint some (possibly none) edges so that all constraints are met, and among all ways to do so, you should choose the one with minimum total cost. 

Input

The first line contains five integers n_1, n_2, m, r and b (1 ≤ n_1, n_2, m, r, b ≤ 200) — the number of vertices in the first part, the number of vertices in the second part, the number of edges, the amount of coins you have to pay to paint an edge red, and the amount of coins you have to pay to paint an edge blue, respectively.

The second line contains one string consisting of n_1 characters. Each character is either U, R or B. If the i-th character is U, then the i-th vertex of the first part is uncolored; R corresponds to a red vertex, and B corresponds to a blue vertex.

The third line contains one string consisting of n_2 characters. Each character is either U, R or B. This string represents the colors of vertices of the second part in the same way.

Then m lines follow, the i-th line contains two integers u_i and v_i (1 ≤ u_i ≤ n_1, 1 ≤ v_i ≤ n_2) denoting an edge connecting the vertex u_i from the first part and the vertex v_i from the second part.

The graph may contain multiple edges.

Output

If there is no coloring that meets all the constraints, print one integer -1.

Otherwise, print an integer c denoting the total cost of coloring, and a string consisting of m characters. The i-th character should be U if the i-th edge should be left uncolored, R if the i-th edge should be painted red, or B if the i-th edge should be painted blue. If there are multiple colorings with minimum possible cost, print any of them.

Examples

Input


3 2 6 10 15
RRB
UB
3 2
2 2
1 2
1 1
2 1
1 1


Output


35
BUURRU


Input


3 1 3 4 5
RRR
B
2 1
1 1
3 1


Output


-1


Input


3 1 3 4 5
URU
B
2 1
1 1
3 1


Output


14
RBB
#include <bits/stdc++.h>
using namespace std;
template <class FLOWTYPE, class COSTTYPE>
struct Edge {
  int rev, from, to, id;
  FLOWTYPE cap, icap;
  COSTTYPE cost;
  Edge(int r, int f, int t, FLOWTYPE ca, COSTTYPE co, int id = -1)
      : rev(r), from(f), to(t), cap(ca), icap(ca), cost(co), id(id) {}
  friend ostream& operator<<(ostream& s, const Edge& E) {
    if (E.cap > 0)
      return s << E.from << "->" << E.to << '(' << E.cap << ',' << E.cost
               << ')';
    else
      return s;
  }
};
template <class FLOWTYPE, class COSTTYPE>
struct Graph {
  vector<vector<Edge<FLOWTYPE, COSTTYPE> > > list;
  Graph(int n = 0) : list(n) {}
  void init(int n = 0) {
    list.clear();
    list.resize(n);
  }
  void reset() {
    for (int i = 0; i < (int)list.size(); ++i)
      for (int j = 0; j < list[i].size(); ++j) list[i][j].cap = list[i][j].icap;
  }
  inline vector<Edge<FLOWTYPE, COSTTYPE> >& operator[](int i) {
    return list[i];
  }
  inline const size_t size() const { return list.size(); }
  inline Edge<FLOWTYPE, COSTTYPE>& redge(const Edge<FLOWTYPE, COSTTYPE>& e) {
    if (e.from != e.to)
      return list[e.to][e.rev];
    else
      return list[e.to][e.rev + 1];
  }
  void addedge(int from, int to, FLOWTYPE cap, COSTTYPE cost, int id = -1) {
    list[from].push_back(Edge<FLOWTYPE, COSTTYPE>((int)list[to].size(), from,
                                                  to, cap, cost, id));
    list[to].push_back(Edge<FLOWTYPE, COSTTYPE>((int)list[from].size() - 1, to,
                                                from, 0, -cost));
  }
  void add_undirected_edge(int from, int to, FLOWTYPE cap, COSTTYPE cost,
                           int id = -1) {
    list[from].push_back(Edge<FLOWTYPE, COSTTYPE>((int)list[to].size(), from,
                                                  to, cap, cost, id));
    list[to].push_back(Edge<FLOWTYPE, COSTTYPE>((int)list[from].size() - 1, to,
                                                from, cap, cost, id));
  }
  friend ostream& operator<<(ostream& s, const Graph& G) {
    s << endl;
    for (int i = 0; i < G.size(); ++i) {
      s << i << ":";
      for (auto e : G.list[i]) s << " " << e;
      s << endl;
    }
    return s;
  }
};
template <class FLOWTYPE, class COSTTYPE>
COSTTYPE MinCostFlow(Graph<FLOWTYPE, COSTTYPE>& G, int s, int t, FLOWTYPE f) {
  int n = (int)G.size();
  vector<COSTTYPE> pot(n, 0), dist(n, -1);
  vector<int> prevv(n), preve(n);
  COSTTYPE res = 0;
  while (f > 0) {
    priority_queue<pair<COSTTYPE, int>, vector<pair<COSTTYPE, int> >,
                   greater<pair<COSTTYPE, int> > >
        que;
    dist.assign(n, -1);
    dist[s] = 0;
    que.push(make_pair(0, s));
    while (!que.empty()) {
      pair<COSTTYPE, int> p = que.top();
      que.pop();
      int v = p.second;
      if (dist[v] < p.first) continue;
      for (int i = 0; i < G[v].size(); ++i) {
        auto e = G[v][i];
        if (e.cap > 0 && (dist[e.to] < 0 ||
                          dist[e.to] > dist[v] + e.cost + pot[v] - pot[e.to])) {
          dist[e.to] = dist[v] + e.cost + pot[v] - pot[e.to];
          prevv[e.to] = v;
          preve[e.to] = i;
          que.push(make_pair(dist[e.to], e.to));
        }
      }
    }
    if (dist[t] < 0) return -1;
    for (int v = 0; v < n; ++v) pot[v] += dist[v];
    FLOWTYPE d = f;
    for (int v = t; v != s; v = prevv[v]) {
      d = min(d, G[prevv[v]][preve[v]].cap);
    }
    f -= d;
    res += pot[t] * d;
    for (int v = t; v != s; v = prevv[v]) {
      Edge<FLOWTYPE, COSTTYPE>& e = G[prevv[v]][preve[v]];
      Edge<FLOWTYPE, COSTTYPE>& re = G.redge(e);
      e.cap -= d;
      re.cap += d;
    }
  }
  return res;
}
int main() {
  int N1, N2, M;
  long long r, b;
  cin >> N1 >> N2 >> M >> r >> b;
  string ls, rs;
  cin >> ls >> rs;
  const long long INF = 1 << 29;
  Graph<long long, long long> G(N1 + N2 + 4);
  int s = N1 + N2, t = N1 + N2 + 1, ss = N1 + N2 + 2, tt = N1 + N2 + 3;
  long long nS = 0, nT = 0;
  for (int v = 0; v < N1; ++v) {
    if (ls[v] == 'R') {
      ++nS;
      G.addedge(s, v, INF, 0);
      G.addedge(ss, v, 1, 0);
    } else if (ls[v] == 'B') {
      ++nT;
      G.addedge(v, t, INF, 0);
      G.addedge(v, tt, 1, 0);
    } else {
      G.addedge(s, v, INF, 0);
      G.addedge(v, t, INF, 0);
    }
  }
  for (int v = 0; v < N2; ++v) {
    if (rs[v] == 'B') {
      ++nS;
      G.addedge(s, v + N1, INF, 0);
      G.addedge(ss, v + N1, 1, 0);
    } else if (rs[v] == 'R') {
      ++nT;
      G.addedge(v + N1, t, INF, 0);
      G.addedge(v + N1, tt, 1, 0);
    } else {
      G.addedge(s, v + N1, INF, 0);
      G.addedge(v + N1, t, INF, 0);
    }
  }
  G.addedge(s, tt, nS, 0);
  G.addedge(ss, t, nT, 0);
  for (int i = 0; i < M; ++i) {
    int x, y;
    cin >> x >> y;
    --x, --y;
    G.addedge(x, y + N1, 1, r, i);
    G.addedge(y + N1, x, 1, b, i);
  }
  G.addedge(t, s, INF, 0);
  auto res = MinCostFlow(G, ss, tt, nS + nT);
  cout << res << endl;
  if (res == -1) return 0;
  string ans(M, 'U');
  for (int v = 0; v < N1; ++v) {
    for (auto e : G[v]) {
      if (e.id == -1) continue;
      if (e.cap == 0 && e.icap == 1) ans[e.id] = 'R';
    }
  }
  for (int v = 0; v < N2; ++v) {
    for (auto e : G[v + N1]) {
      if (e.id == -1) continue;
      if (e.cap == 0 && e.icap == 1) ans[e.id] = 'B';
    }
  }
  cout << ans << endl;
}
