龙国国庆之际，国王邀请 位大臣参与一起玩一个游戏。国王与每位大臣都会在左、右手各写一整数：国王分别写下了 ；此后第 位大臣写下 。 现在国王站在最前方，其余大臣依次排成一行。排定顺序后，第 位大臣（排在队伍中的相对顺序）能得到的金币数为 ，其中 表示国王左手的数字。 国王希望通过调整大臣的站位顺序（相对顺序可任意改变，国王位置固定在最前），使得 获得金币最多 的大臣得到的金币数尽可能小。

输入描述:

第一行输入整数 ——大臣人数。第二行输入两个整数 ——国王左、右手的数字。随后 行，第 行输入两个整数 ——第 位大臣左、右手的数字。

输出描述:

输出一个整数，表示在最优站位下，获奖最多的大臣所能获得的最小金币数。数据保证答案不超过 ；