描述

遇难者鲁滨逊·克鲁索独自生活在一个偏远的岛屿上。有一天，一艘载有皇家图书馆藏书的船只在附近失事。通常情况下，鲁滨逊会从失事船只上带回任何有用的东西到他的岛上，这次他带回了一个装满书籍的大箱子。

鲁滨逊决定为这些书建造一个书架，以创建他自己的图书馆。为此，他在岩石上凿出了一个矩形壁龛，钉入了木钉，并在每对高度相同的木钉上放置了木板，这样所有的木板都水平放置，可作为书架使用。

不幸的是，鲁滨逊发现有一本特别古老且很大的书籍放不进他的书架。他测量了这本书的高度和宽度，并决定重新设计他的书架，以便在考虑到其他书架的位置和壁龛尺寸的情况下，将这本书完全放在其中一个书架上。对于书架上的每个书架，应进行以下操作之一：

1. 将书架留在其原来的位置。 2. 将书架向左或向右移动。 3. 通过切掉木板的一部分来缩短书架，并可选择将其向左或向右移动。 4. 将其中一个木钉移到相同高度的不同位置，并将书架向左或向右移动。 5. 通过切掉木板的一部分来缩短书架，将其中一个木钉移到相同高度的不同位置，并可选择将缩短后的书架向左或向右移动。 6. 连同两个支撑木钉一起从书架上移除该书架。

我们说，如果恰好有两个不同的木钉支撑着书架，并且书架的中心在其木钉之间或与其中一个木钉重合，那么这个书架就被其木钉正确支撑。鲁滨逊图书馆的原始设计中，所有书架都被其木钉正确支撑，并且所有书架的长度都是整数英寸。鲁滨逊只能从木板上切掉整数英寸的长度，因为他没有更精确测量的工具。重新设计后，所有剩余的书架都必须被其木钉正确支撑。

你需要找到一种方法来重新设计鲁滨逊的图书馆，以便放入这本特别的旧书，同时又不会过多改变原始设计。你必须使在重新设计过程中从其原始位置移除的木钉数量最小化（操作 $4$ 和 $5$ 移除一个木钉，操作 $6$ 移除两个木钉）。如果有不同的方法来解决这个问题，那么你需要找到使切掉的木板总长度最小的方法（操作 $3$ 和 $5$ 涉及从木板上切掉一些东西，操作 $6$ 相当于切掉整个木板）。木板的宽度和木钉的直径应视为零。

这本书不能旋转。这本书应该完全（就其整个宽度而言）放在其中一个书架上，并且只能接触其他书架、它们的木钉或壁龛的边缘。

输入

输入文件的第一行包含四个用空格分隔的整数 $X_N$、$Y_N$、$X_T$ 和 $Y_T$。它们分别是壁龛的宽度和高度，以及这本旧书的宽度和高度（单位：英寸，$1 \leq X_N, Y_N, X_T, Y_T \leq 1000$）。

输入文件的第二行包含一个整数 $N$（$1 \leq N \leq 100$），表示书架的数量。然后接下来有 $N$ 行。每行表示一个单独的书架及其两个支撑木钉，并包含五个用空格分隔的整数 $y_i$、$x_i$、$l_i$、$x_{1i}$、$x_{2i}$，其中：

• $y_i$（$0 < y_i < Y_N$） - 第 $i$ 个书架距离壁龛底部的高度（单位：英寸）。
• $x_i$（$0 \leq x_i < X_N$） - 第 $i$ 个书架的左端与壁龛左边缘之间的距离（单位：英寸）。
• $l_i$（$0 < l_i \leq X_N - x_i$） - 第 $i$ 个书架的长度（单位：英寸）。
• $x_{1i}$（$0 \leq x_{1i} \leq l_i/2$） - 第 $i$ 个书架的左端与其最左边支撑木钉之间的距离（单位：英寸）。
• $x_{2i}$（$l_i/2 \leq x_{2i} \leq l_i$；$x_{1i} < x_{2i}$） - 第 $i$ 个书架的左端与其最右边支撑木钉之间的距离（单位：英寸）。

所有书架都处于不同的高度，并且都被其木钉正确支撑。对于输入数据，保证存在解决方案。

输出

输出文件应包含两个用空格分隔的整数。第一个整数是鲁滨逊为了放置这本书而从其原始位置移除的木钉的最小数量。第二个整数是在移除最少数量木钉的重新设计过程中，切掉的木板总长度的最小英寸数。

输入示例

11 8 4 6
4
1 1 7 1 4
4 3 7 1 6
7 2 6 3 4
2 0 3 0 3

输出示例

1 3

来源

2001年东北欧地区竞赛