Educational Codeforces Round 26 |
---|
Закончено |
У одного очень важного человека есть лист бумаги в форме прямоугольника a × b.
Также у него есть n печатей, каждая из которых оставляет на бумаге оттиск — прямоугольник размера xi × yi. Печать надо ставить параллельно сторонам листа (но можно поворачивать на 90 градусов).
Очень важный человек хочет выбрать две любые различные печати и поставить ими два оттиска. Каждая из выбранных печатей ставит ровно один оттиск. Оттиски надо поставить так, чтобы они не пересекались (но они могут касаться сторонами), а суммарная занимаемая ими площадь была наибольшей. Какую наибольшую площадь можно занять двумя печатями?
Первая строка содержит три целых числа n, a и b (1 ≤ n, a, b ≤ 100).
Каждая из следующих n строк содержит два целых числа xi, yi (1 ≤ xi, yi ≤ 100).
Выведите максимальную суммарную площадь, которую можно покрыть двумя печатями. Если две печати выбрать невозможно, выведите 0.
2 2 2
1 2
2 1
4
4 10 9
2 3
1 1
5 10
9 11
56
3 10 10
6 6
7 7
20 5
0
В первом примере можно повернуть второй оттиск на 90 градусов. Потом разместить первый оттиск сразу под вторым и занять весь лист.
Во втором примере нельзя выбрать последний оттиск, так как он не поместится. Выбрав первый и третий оттиски, мы получим максимальную площадь.
В третьем примере не существует такой пары оттисков, что они оба могут поместиться на листе.
Название |
---|