- В период, когда действовали ограничения, направленные на предотвращение распространения новой инфекции, при продаже мест в кинотеатрах оставляли по одному свободному месту между зрителями. Места, расположенные рядом, можно было купить только одновременно, т.е. одна семья (или компания друзей) могла сидеть вместе при одновременной покупке билетов.
Известно, что кинозал имеет N рядов по M мест в каждом. Места и ряды нумеруются по порядку, начиная с единицы. Известно, что K мест уже выкуплены (заняты). По приведенным данным о уже занятых местах требуется определить
а) какое наибольшее количество мест сможет продать кинотеатр при условии соблюдения ограничений;
б) в каком ряду количество мест, которое сможет продать кинотеатр, будет наибольшим. Если таких рядов несколько, требуется указать наименьший номер ряда.
Входные данные представлены в файле 26-106.txt следующим образом. В первой строке файла через пробел записаны три натуральных числа: N – количество рядов в кинотеатре (1 ≤ N ≤ 10 000), M – количество мест в ряду (1 ≤ M ≤ 10 000), K – количество занятых мест (1 ≤ K ≤ 10 000). Далее в файле записаны K строк, по два числа в каждой. Первое число в паре означает номер ряда, второе – номер занятого места в этом ряду.
Пример входного файла:
3 10 4
1 3
1 4
1 7
2 5
Наибольшее количество мест удастся продать, если билеты будут покупать большие компании людей, тогда их можно будет посадить рядом.
| |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
| 1 |
|
|
|
|
|
|
|
|
|
|
| 2 |
|
|
|
|
|
|
|
|
|
|
| 3 |
|
|
|
|
|
|
|
|
|
|
Для наглядности на рисунке серым цветом обозначены уже занятые места, желтым цветом – места, билеты на которые удастся продать в наиболее благоприятном случае. Максимальное количество проданных билетов для приведенного примера будет равно 20. Номер ряда, где удастся продать максимальное количество билетов – 3. Ответ: 20 3.