← 返回题目列表

Codeforces · 837/C

C. 两个密封件

中文机器翻译题面 查看原题

一个非常重要的人有一张长方形 a × b 形状的纸。

另外,他有n个封印。每个印章都会在纸上留下一个尺寸为 xi × yi 的矩形印记。每个印痕必须平行于纸张的侧面(但印章可以旋转 90 度)。

一个非常重要的人想要选择两个不同的印章并给它们留下两个印象。每一个选定的印章都会给人留下完全相同的印象。印象不应重叠(但可以接触侧面),并且它们所占据的总面积应尽可能大。两个印章最多可以占据多少面积?

输入

第一行包含三个整数 n、a 和 b (1 ≤ n、a、b ≤ 100)。

接下来的 n 行每行包含两个数字 xi, yi (1 ≤ xi, yi ≤ 100)。

输出

打印两个密封件可占据的最大总面积。如果无法选择两个密封件,请打印 0。

示例

输入 #1

2 2 2
1 2
2 1

输出 #1

4

输入 #2

4 10 9
2 3
1 1
5 10
9 11

输出 #2

56

输入 #3

3 10 10
6 6
7 7
20 5

输出 #3

0

注意

在第一个示例中,您可以将第二个密封件旋转 90 度。然后将其印模放在第一个印章的印模下方。这将占据整张纸。

在第二个示例中,您无法选择最后一个密封件,因为它不合适。通过选择第一和第三个密封件,您将占据最大的面积。

在第三个示例中,没有一对密封件可以同时安装在一张纸上。