Хлопець, дівчина і кіт
Limits: 2 sec., 512 MiB
У Зеника і Марічки є \(n+m\) знайомих. Серед них \(n\) хлопців, пронумерованих цілими числами від 1 до \(n\) включно, та \(m\) дівчат, пронумерованих від \(n+1\) до \(n+m\) включно.
Також вони знають \(k\) котів, пронумерованих від 1 до \(k\) включно.
Хлопці та дівчата доволі неперебірливі один до одного, тому усім хлопцям подобаються усі дівчата, і усім дівчатам подобаються усі хлопці. Однак не все так просто з котами. Вам відомо \(p\) пар \((u_i, v_i)\), кожна з яких вказує, що знайомому \(u_i\) подобається кіт \(v_i\).
Зеник та Марічка хочуть розділити усіх знайомих та котів на якомога більшу кількість трійок (хлопець, дівчина, кіт) так, аби в кожній трійці усі подобались усім. Допоможіть їм знайти цю кількість.
Зауважте, що кожен знайомий та кіт можуть входити в не більше ніж одну трійку.
Input
У першому рядку задано чотири цілих числа \(n\), \(m\), \(k\) та \(p\) — кількість хлопців, дівчат, котів та відомих пар відповідно.
У наступних \(p\) рядках задано пари чисел \(u_i, v_i\) розділених пробілами. Кожна пара вказує, що \(u_i\)-му знайомому подобається \(v_i\)-й кіт.
Output
У єдиному рядку виведіть одне ціле число — максимальну кількість трійок.
Constraints
\(1 \le n, m, k \le 200\),
\(1 \le p \le 2000\),
\(1 \le u_i \le n+m\), \(1 \le v_i \le k\),
усі \(p\) пар — унікальні.
Samples
| Input (stdin) | Output (stdout) |
|---|---|
| 3 4 4 9 1 2 2 1 1 3 3 2 2 4 5 2 5 3 7 4 6 2 | 3 |
Notes
У першому прикладі можна утворити трійки (1, 5, 3), (3, 6, 2) та (2, 7, 4).
| Element Type | Created | Who | Problem | Compiler | Result | Time (sec.) | Memory (MiB) | # | Actions |
|---|