0148. Влюбленный кассир

Имя входного файла: cash.in
Имя выходного файла: cash.out
Ограничение по времени: 3 s
Ограничение по памяти: 32 megabytes

В кинотеатре m рядов по n мест в каждом. Влюбленный кассир продал nm билетов, не следя за тем, чтобы они были проданы на разные места. Определить, какое наибольшее количество зрителей можно разместить в кинотеатре так, чтобы у каждого в билете был правильно указан хотя бы один из номеров - ряда или места.

Формат входного файла

Первая строка входного файла содержит два целых числа 1 ≤ m, n ≤ 50, последующие nm строк - пары целых чисел 1 ≤ Ak ≤ m, 1 ≤ Bk ≤ n - номер ряда и номер места, указанные в билете k-го посетителя кинотеатра (1 ≤ k ≤ nm.

Формат выходного файла

Ответом является целое число - наибольшее количество зрителей, которых можно рассадить в кинотеатре в соответствии с условиями задачи.

Пример:

cash.incash.out
2 2 1 1 1 1 1 1 1 1 3


Источник: Petrozavodsk Summer 2003. Petrozavodsk SU Contest #2, Friday, August 29

Обсудить       Отправить решение



Версия для печати