Задача №3361. Bugs
Ограничение по времени – 10 секунд.
Ограничение по памяти – 64 мегабайта.
Компания Bugs начинает выпуск планки оперативной памяти Q-RAM размером 6 террабайт. Каждая планка состоит из 6 квадратных микросхем в форме прямоугольника \(3\times 2\). В результате технологического процесса, используемого в компании Bugs, получается прямоугольная область, разделенная на \(N\times M\) квадратных микросхем. После этого микросхемы тщательно проверяются и битые микросхемы помечаются черным маркером.
После этого, область разрезается на отдельные планки размером \(3\times 2\)(или \(2\times 3\)). Естественно, ни одна планка не должна содержать битых микросхем. Может возникнуть такая ситуация, что не все хорошие микросхемы войдут в какую-либо планку. Однако для снижения себестоимости компания хочет изготовить из произведенной области как можно больше планок.
На вход вашей программе будет даваться размер области и список битых микросхем на ней. Для этой области вам необходимо определить максимальное количество планок, которое можно вырезать из нее.
Первая строка содержит три целых числа \(N\), \(M\) и \(K\) (\(1\leq N\leq 150\), \(1 \leq M \leq 10\), \(0 \leq K \leq M\times N\)), где \(N\) – длина области, \(M\) – ее ширина, а \(K\) – количество битых микросхем. Следующие K строк содержат описание битых микросхем. Каждая из них содержит координаты битой микросхемы в виде двух целых чисел \(x\) и \(y\) (\(1 \leq x \leq N\), \(1 \leq y \leq M\)).
Для каждой области выведите максимальное количество планок, которое может быть вырезано из нее на отдельной строке.
6 6 5 1 4 4 6 2 2 3 6 6 4
3
6 5 4 3 3 6 1 6 2 6 4
4