Хлопець, дівчина і кіт

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) сopy	Output (stdout) сopy
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).