Time limit 2000/4000/4000/4000 ms. Memory limit 65000/65000/65000/65000 Kb.
manyQ
Поскольку складывать квадраты из прямоугольников Артём Евгеньевич научился, ему предлагается задача посложнее.
Теперь прямоугольников много - N штук. Из них надо сложить как можно больше квадратов - каждый из пары прямоугольников. Один прямоугольник может входить только в один квадрат.
Входные данные. В первой строке натуральное число N - количество прямоугольников. Их может быть довольно много - до 10 тысяч. Далее следуют N строк со сторонами прямоугольников, в каждой - два натуральных числа через пробел.
Выходные данные. Целое число - количество квадратов, которые можно сложить из данного набора прямоугольников.
Пример. При следующих входных данных
7
5 5
11 5
5 3
5 1
6 11
2 5
5 4
программа должна вывести 3.
Для отправки решений необходимо выполнить вход.
|