Кольорові відрізки
Limits: 4 sec., 256 MiB
«Досить з мене тих покемонів», — подумав Тарас і відкрив цікаву гру-головоломку.
Згідно з правилами цієї гри, гравцю задається набір із \(n\) різних точок на прямій \(y = 4\), пронумерованих зліва направо від 1 до \(n\) включно, а також \(m\) різних точок на прямій \(y = 7\), аналогічно пронумерованих від 1 до \(m\) включно. Деякі пари цих точок (з різних прямих) з’єднано відрізком, пофарбованим в один із двох кольорів — червоний або зелений. Завданням гравця є вибрати найбільшу множину відрізків таким чином, щоб виконувались наступні дві умови:
Кожна з \(n+m\) точок належить не більше ніж одному відрізку.
Не існує пари відрізків різного кольору, які перетинаються.
Допоможіть Тарасу знайти найбільшу кількість відрізків, які він може вибрати.
Input
У першому рядку задано три цілих числа \(n\), \(m\) та \(k\).
У наступних \(k\) рядках описуються
відрізки у форматі \(a_i\) \(b_i\) \(c_i\), де \(a_i\) та \(b_i\) описують індекси точок, які з’єднує
відповідний відрізок, а \(c_i\) — колір
відрізка, який може бути R
або G
(червоний та
зелений відповідно).
Output
У єдиному рядку виведіть одне ціле число — відповідь до задачі.
Constraints
\(1 \le n, m \le 44\),
\(1 \le k \le 2500\),
\(1 \le a_i \le n\),
\(1 \le b_i \le m\).
Samples
Input (stdin) | Output (stdout) |
---|---|
2 2 2 1 2 R 2 1 G | 1 |
Submit a solution
Element Type | Created | Who | Problem | Compiler | Result | Time (sec.) | Memory (MiB) | # | Actions |
---|
Element Type | Created | Who | Problem | Compiler | Result | Time (sec.) | Memory (MiB) | # | Actions |
---|