F. Красно-синий граф
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вам задан двудольный граф: первая доля графа содержит $$$n_1$$$ вершин, вторая — $$$n_2$$$ вершин, а также в графе $$$m$$$ ребер. Граф может содержать кратные ребра.

Первоначально, все ребра графа бесцветные. Каждое ребро вы можете либо оставить бесцветным (это бесплатно), либо покрасить в красный (стоимость данного действия $$$r$$$ монет), либо покрасить в синий (за $$$b$$$ монет). Никакое ребро не может быть покрашено в оба цвета одновременно.

Также в графе вершины разбиваются на три типа — бесцветные, красные и синие. Цветные вершины добавляют дополнительные ограничения на раскраску ребер:

  • у каждой красной вершины количество смежных с ней красных ребер должно быть строго больше, чем смежных с ней синих ребер;
  • у каждой синей вершины количество смежных с ней синих ребер должно быть строго больше, чем смежных с ней красных ребер.

Бесцветные вершины не накладывают никаких ограничений.

Ваша задача — раскрасить некоторые (возможно, никакие) ребра так, чтобы выполнялись заданные ограничения, и среди всех возможных раскрасок выбрать такую, суммарная стоимость которой минимальна.

Входные данные

В первой строке заданы пять целых чисел $$$n_1$$$, $$$n_2$$$, $$$m$$$, $$$r$$$ и $$$b$$$ ($$$1 \le n_1, n_2, m, r, b \le 200$$$) — количество вершин в первой доле, количество вершин во второй доле, количество ребер, стоимость покраски одного ребра в красный и стоимость покраски в синий соответственно.

Во второй строке задана одна строка из $$$n_1$$$ символов. Каждый символ — это U, R или B. Если $$$i$$$-й символ — это U, то $$$i$$$-я вершина первой доли бесцветная; R соответствует красной вершине, а B — синей вершине.

В третьей строке задана строка из $$$n_2$$$ символов. Каждый символ — это также U, R или B. Данная строка задает цвета вершин второй доли аналогичным образом.

Далее следуют $$$m$$$ строк: в $$$i$$$-й строке заданы два целых числа $$$u_i$$$ и $$$v_i$$$ ($$$1 \le u_i \le n_1$$$, $$$1 \le v_i \le n_2$$$), задающие ребро между вершиной $$$u_i$$$ из первой доли и вершиной $$$v_i$$$ из второй доли.

Граф может содержать кратные ребра.

Выходные данные

Если не существует раскраски ребер, которая удовлетворяет всем заданным ограничениям, — выведите $$$-1$$$.

Иначе, выведите число $$$c$$$, обозначающее минимальную суммарную стоимость раскраски, и строку из $$$m$$$ символов. $$$i$$$-й символ должен быть U, если $$$i$$$-е ребро осталось бесцветным, R, если $$$i$$$-е ребро покрашено в красный, или B, если $$$i$$$-е ребро покрашено в синий. Если существует несколько оптимальных раскрасок — выведите любое.

Примеры
Входные данные
3 2 6 10 15
RRB
UB
3 2
2 2
1 2
1 1
2 1
1 1
Выходные данные
35
BUURRU
Входные данные
3 1 3 4 5
RRR
B
2 1
1 1
3 1
Выходные данные
-1
Входные данные
3 1 3 4 5
URU
B
2 1
1 1
3 1
Выходные данные
14
RBB