На лето родители отправили Антона к бабушке помогать ей выращивать в огороде арбузы. Чтобы они выросли большими и вкусными, требуется поливать растения каждый день, что и было поручено мальчику. Если арбуз был полит, он вырастает на один килограмм (а если не был, то остаётся прежнего размера) за каждый день.
Сам огород представляет собой прямоугольную сетку из n строк и m столбцов, в каждой ячейке которой растёт арбуз, изначально имеющий массу 0 килограмм. Антон очень не любит работать, поэтому в i-й день из всех d, что он будет гостить у бабушки, планирует поливать только арбузы, лежащие на пересечении первых xi строк и первых yi столбцов.
В конце лета за свою работу мальчик получит самый большой арбуз из имеющихся в огороде (а если их несколько, то сразу все самые большие!). Антон очень любит гигантские арбузы, поэтому просит вас определить, сколько же их в итоге ему достанется, и какого они будут веса.
Формат входных данных
Первые три строки входных данных содержат целые числа 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 первых столбцов.
Обратите внимание, что при заданных ограничениях для хранения ответов необходимо использовать 64-битный тип данных, например, long long в C++, int64 в Free Pascal, long в Java.
Формат выходных данных
Выведите два числа через пробел — количество арбузов, которые достанутся Антону, и вес каждого из них.
Пояснение
В первом примере Антон один раз поливает квадрат 2×2, поэтому ему достанется 4 арбуза массой 1 килограмм каждый.
Во втором примере будут политы 3 арбуза в первом столбце и 2 арбуза в первой строке. Тогда ровно один арбуз окажется полит дважды, его Антон и получит.
1 Ответ
Ответ:
def Minimum(A):
if len(A) <= 1:
return A[0]
else:
L = A[:len(A) // 2]
R = A[len(A) // 2:]
return min(Minimum(L), Minimum(R))
n = int(input())
m = int(input())
d = int(input())
X = []
Y = []
for i in range(d):
X.append(int(input()))
Y.append(int(input()))
ans = Minimum(X) * Minimum(Y)
print(ans, d)