Кольорові відрізки

Обмеження: 4 сек., 256 МіБ

«Досить з мене тих покемонів», — подумав Тарас і відкрив цікаву гру-головоломку.

Згідно з правилами цієї гри, гравцю задається набір із \(n\) різних точок на прямій \(y = 4\), пронумерованих зліва направо від 1 до \(n\) включно, а також \(m\) різних точок на прямій \(y = 7\), аналогічно пронумерованих від 1 до \(m\) включно. Деякі пари цих точок (з різних прямих) з’єднано відрізком, пофарбованим в один із двох кольорів — червоний або зелений. Завданням гравця є вибрати найбільшу множину відрізків таким чином, щоб виконувались наступні дві умови:

• Кожна з \(n+m\) точок належить не більше ніж одному відрізку.

• Не існує пари відрізків різного кольору, які перетинаються.

Допоможіть Тарасу знайти найбільшу кількість відрізків, які він може вибрати.

Вхідні дані

У першому рядку задано три цілих числа \(n\), \(m\) та \(k\).

У наступних \(k\) рядках описуються відрізки у форматі \(a_i\) \(b_i\) \(c_i\), де \(a_i\) та \(b_i\) описують індекси точок, які з’єднує відповідний відрізок, а \(c_i\) — колір відрізка, який може бути R або G (червоний та зелений відповідно).

Вихідні дані

У єдиному рядку виведіть одне ціле число — відповідь до задачі.

Обмеження

\(1 \le n, m \le 44\),

\(1 \le k \le 2500\),

\(1 \le a_i \le n\),

\(1 \le b_i \le m\).

Приклади