|
Антон и арбузы
(Время: 2 сек. Память: 32 Мб Сложность: 15%)
На лето родители отправили Антона к бабушке помогать ей выращивать в огороде арбузы. Чтобы они выросли большими и вкусными, требуется поливать растения каждый день, что и было поручено мальчику. Если арбуз был полит, он вырастает на один килограмм (а если не был, то остаётся прежнего размера) за каждый день.
Сам огород представляет собой прямоугольную сетку из n строк и m столбцов, в каждой ячейке которой растёт арбуз, изначально имеющий массу 0 килограмм. Антон очень не любит работать, поэтому в i-й день из всех d, что он будет гостить у бабушки, планирует поливать только арбузы, лежащие на пересечении первых xi строк и первых yi столбцов.
В конце лета за свою работу мальчик получит самый большой арбуз из имеющихся в огороде (а если их несколько, то сразу все самые большие!). Антон очень любит гигантские арбузы, поэтому просит вас определить, сколько же их в итоге ему достанется, и какого они будут веса.
Входные данные
Первые три строки входного файла INPUT.TXT содержат целые числа n, m и d, именно в таком порядке – количество строк и столбцов в огороде и время пребывания Антона у бабушки (1 ≤ n, m ≤ 109, 1 ≤ d ≤ 105). Далее идут 2d чисел xi и yi, каждое в отдельной строке, обозначающих количество строк и столбцов, арбузы в которых были политы мальчиком в день i (1 ≤ xi ≤ n, 1 ≤ yi ≤ m). Уточним, что эти данные упорядочены по дням, т.е. сначала идёт пара чисел x1,y1 именно в таком порядке, затем x2,y2 и так далее.
Отметим отдельно, что бабушка пронумеровала все строки и столбцы в огороде, и Антон всегда поливает именно xi первых строк и yi первых столбцов.
Выходные данные
В выходной файл OUTPUT.TXT выведите два числа через пробел – количество арбузов, которые достанутся Антону, и вес каждого из них.
Примеры
| № | INPUT.TXT | OUTPUT.TXT |
|---|
| 1 | 3
3
1
2
2 | 4 1 |
| 2 | 4
3
2
3
1
1
2 | 1 2 |
Пояснение
В первом примере Антон один раз поливает квадрат 2×2, поэтому ему достанется 4 арбуза массой 1 килограмм каждый.
Во втором примере будут политы 3 арбуза в первом столбце и 2 арбуза в первой строке. Так ровно один арбуз окажется полит дважды, его Антон и получит.
Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!
| |
