← 返回题目列表

Codeforces · 374/E

E. 伊娜和婴儿

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

Inna、Dima 和 Sereja 共处一间房间。外面很冷,所以塞雷贾建议玩一种叫做“宝贝”的棋盘游戏。

婴儿游戏板是一个无限平面,包含 n 个蓝色婴儿和 m 个红色婴儿。每个婴儿都是随着时间的推移而成长的一个片段。在时间时刻 t,蓝色婴儿 (x, y) 是一条蓝色线段,其端点为 (x - t, y + t)、(x + t, y - t)。类似地,在时间 t 处,红色婴儿 (x, y) 是一条红色线段,其端点位于平面的点 (x + t, y + t)、(x - t, y - t) 处。最初,在时间 t = 0 时,所有婴儿都是平面上的点。

游戏的目标是找到当平面包含非零区域的矩形且其边被一些婴儿完全覆盖时的第一个整数时刻。一侧可能被多个婴儿覆盖。更正式地说,矩形每条边的每个点都应该被至少一个任何颜色的婴儿覆盖。此时,您必须假设婴儿是闭合线段,即它们包含端点。

你会得到所有婴儿的位置 - 帮助 Inna 和 Dima 找到所需的时间。

输入

输入的第一行包含两个整数 n 和 m (1 ≤ n, m ≤ 2000)。

接下来的 n 行包含蓝色婴儿的坐标。第 i 行包含整数 xi、yi — 婴儿的坐标。接下来的 m 行包含类似形式的 m 个红色婴儿的坐标。

输入的所有坐标的绝对值不超过 106。请注意,所有婴儿都站在不同的点上。

输出

在单行中打印一个整数——问题的答案。

如果矩形从未出现在平面上,请打印“Poor Sereja!”没有引号。

示例

输入 #1

2 2
2 2
5 5
3 7
5 1

输出 #1

3

输入 #2

3 2
2 2
3 2
6 2
4 2
5 2

输出 #2

1