你需要找到一个最大的、可负担得起的地点来建造一座新金字塔。为了帮助你做出决定，你获得了一份可用土地的勘测图，该土地被方便地划分为一个 $M \times N$ 的方格网。金字塔的底座必须是一个边与网格边平行的正方形。

勘测图确定了一组 $P$ 个可能重叠的障碍物，它们被描述为网格中边与网格边平行的矩形。为了建造金字塔，其底座覆盖的所有单元格都必须清除掉任何障碍物。移除第 $i$ 个障碍物的成本为 $C_i$。每当移除一个障碍物时，必须将其完全移除，也就是说，你不能只移除障碍物的一部分。此外，请注意，移除一个障碍物不会影响与其重叠的其他任何障碍物。

任务

编写一个程序，给定勘测图的尺寸 $M$ 和 $N$、$P$ 个障碍物的描述、移除每个障碍物的成本以及你拥有的预算 $B$，求出金字塔底座可能的最大边长，使得移除障碍物的总成本不超过 $B$。

数据范围与评分

你的程序将在三组不相交的测试数据上进行评测。对于所有测试数据，满足以下约束：

$1 \le M, N \le 1,000,000$：网格的尺寸。 $1 \le C_i \le 7,000$：移除第 $i$ 个障碍物的成本。 $1 \le X_{i1} \le X_{i2} \le M$：第 $i$ 个障碍物最左侧和最右侧单元格的 $X$ 坐标。 $1 \le Y_{i1} \le Y_{i2} \le N$：第 $i$ 个障碍物最底部和最顶部单元格的 $Y$ 坐标。

第一组测试数据（35 分）： $B = 0$：你拥有的预算。（你不能移除任何障碍物。） $1 \le P \le 1,000$：网格中障碍物的数量。

第二组测试数据（35 分）： $0 < B \le 2,000,000,000$：你拥有的预算。 $1 \le P \le 30,000$：网格中障碍物的数量。

第三组测试数据（30 分）： $B = 0$：你拥有的预算。（你不能移除任何障碍物。） $1 \le P \le 400,000$：网格中障碍物的数量。

输入格式

你的程序必须从标准输入读取以下数据：

• 第 1 行包含两个由空格分隔的整数，分别代表 $M$ 和 $N$。
• 第 2 行包含整数 $B$，即你可以负担的最大成本（即你的预算）。
• 第 3 行包含整数 $P$，即勘测图中发现的障碍物数量。
• 接下来的 $P$ 行，每行描述一个障碍物。第 $i$ 行描述第 $i$ 个障碍物。每行包含 5 个由空格分隔的整数：$X_{i1}, Y_{i1}, X_{i2}, Y_{i2}$ 和 $C_i$。它们分别代表障碍物最底部最左侧单元格的坐标、最顶部最右侧单元格的坐标，以及移除该障碍物的成本。网格中最底部最左侧单元格的坐标为 $(1, 1)$，最顶部最右侧单元格的坐标为 $(M, N)$。

输出格式

你的程序必须向标准输出写入一行，包含一个整数，即可以准备的金字塔底座的最大可能边长。如果无法建造任何金字塔，你的程序应输出数字 0。

样例

样例输入 1

6 9 
42 
5 
4 1 6 3 12 
3 6 5 6 9 
1 3 3 8 24 
3 8 6 9 21 
5 1 6 2 20

样例输出 1

4

样例输入 2

13 5 
0 
8 
8 4 10 4 1 
4 3 4 4 1 
10 2 12 2 2 
8 2 8 4 3 
2 4 6 4 5 
10 3 10 4 8 
12 3 12 4 13 
2 2 4 2 21

样例输出 2

3

Figure 1. 样例 1 的障碍物分布及金字塔底座示例