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