大家是否知道 2014 年曾经风靡一时的游戏《Flappy Bird》？这是一款让不断向前飞行的鸟通过反复上升和下降，避免飞出屏幕或撞到管道，从而尽可能飞得更远的游戏。

《Flappy Bird》游戏中出现的鸟，其实是教俊养的宠物鸟“安娜”。

生活在二维世界的教俊和安娜，今天也在玩一个类似于《Flappy Bird》的游戏。安娜在空中飞行并穿过线段时，可以获得等于这些线段权重之和的分数。

该游戏的规则严谨描述如下：

在二维平面上有 $N$ 条与 $x$ 轴或 $y$ 轴平行的线段。第 $i$ 条线段的权重为 $A_i$，两个端点的坐标为 $(X_{1,i}, Y_{1,i})$ 和 $(X_{2,i}, Y_{2,i})$（$0 \le i \le N - 1$）。

安娜从直线 $x = 0$ 上的任意一点开始向 $+x$ 方向飞行，当到达直线 $x = W$ 时结束飞行。出于安全考虑，安娜不能在 $y < 0$ 或 $y > H$ 的区域飞行。也就是说，安娜只能在 $0 \le x \le W, 0 \le y \le H$ 的区域内飞行。

由于安娜是平行于 $x$ 轴飞行的，因此在飞行过程中不能改变自己的 $y$ 坐标。但是，安娜可以在教俊的帮助下，在飞行途中进行一次平行于 $y$ 轴的上升或下降，从而改变自己的 $y$ 坐标。在上升或下降的过程中，安娜的 $x$ 坐标保持不变。请注意，上升和下降不能同时进行。

安娜获得的分数是其移动路径与至少一个点重合的所有线段的权重之和。

例如，假设 $W = 5, H = 4$ 且有 $N = 7$ 条线段，布局如下：

蓝色实线表示线段，虚线表示安娜的移动路径。圆圈内的数字表示线段编号，带符号的数字表示权重。

如果安娜从 $(0, 1)$ 开始飞行，在 $(2, 1)$ 处上升至 $(2, 4)$，然后在 $(5, 4)$ 处结束飞行，则会经过 0 号、1 号、2 号、4 号和 6 号线段，获得 $(-5) + (-1) + 5 + 3 + (-4) = -2$ 分。

如果安娜从 $(0, 3.4)$ 开始飞行，在 $(1.6, 3.4)$ 处下降至 $(1.6, 0.5)$，然后在 $(5, 0.5)$ 处结束飞行，则会经过 0 号、2 号和 5 号线段，获得 $(-5) + 5 + 1 = 1$ 分。

给定 $N$ 条线段的信息，请编写一个程序来计算安娜能获得的最大分数。

函数实现

你需要实现以下函数：

long long get_max_score(int W, int H, vector<int> A, vector<int> X1,
vector<int> Y1, vector<int> X2, vector<int> Y2)

• 该函数仅会被调用一次。
• 作为参数传入的整数数组 A, X1, Y1, X2, Y2 的大小均为 $N$。数组的每个元素 A[i], X1[i], Y1[i], X2[i], Y2[i] 分别表示 $A_i, X_{1,i}, Y_{1,i}, X_{2,i}, Y_{2,i}$（$0 \le i \le N - 1$）。
• 该函数应返回安娜能获得的最大分数。
• 提交的源代码中不得执行任何输入输出函数。

数据范围

• 输入的所有数字均为整数。
• $2 \le W \le 100\,000$
• $1 \le H \le 100\,000$
• $1 \le N \le 250\,000$
• $1 \le X_{i,j} \le W - 1$ ($i \in \{1, 2\}, 0 \le j \le N - 1$)
• $0 \le Y_{i,j} \le H$ ($i \in \{1, 2\}, 0 \le j \le N - 1$)
• $-1\,000\,000\,000 \le A_i \le 1\,000\,000\,000$ ($0 \le i \le N - 1$)
• 对于所有 $0 \le i \le N - 1$，满足 $X_{1,i} = X_{2,i}$ 或 $Y_{1,i} = Y_{2,i}$。
• 所有线段的长度均为正数。即对于所有 $0 \le i \le N - 1$，$(X_{1,i}, Y_{1,i}) \neq (X_{2,i}, Y_{2,i})$。

子任务

1. (7分)
   • $W \le 50$
   • $H \le 50$
   • $N \le 50$
2. (8分)
   • $W \le 50$
   • $H \le 50$
3. (10分)
   • $N \le 500$
4. (14分)
   • $N \le 8\,000$
5. (15分)
   • $X_{1,i} = X_{2,i}$ ($0 \le i \le N - 1$)
6. (10分)
   • $Y_{1,i} = Y_{2,i}$ ($0 \le i \le N - 1$)
7. (36分)
   • 无额外限制。

评分标准

请注意，每个子任务的分数是该子任务所有测试数据得分中的最小值。

样例

输入格式 1

get_max_score(2, 1, [6, -10], [1, 1], [0, 0], [1, 1], [1, 1])

输出格式 1

-4

说明 1

安娜从 $(0, 1)$ 开始飞行，不进行上升或下降，在 $(2, 1)$ 处结束，获得 0 号和 1 号线段的分数，总计 $6 + (-10) = -4$ 分。该示例满足子任务 1, 2, 3, 4, 5, 7 的条件。

输入格式 2

get_max_score(5, 4, [1, 1, 1, 1, -1], [1, 2, 3, 1, 2], [0, 1, 1, 3, 1], [1, 2, 3, 4, 4], [2, 2, 4, 3, 1])

输出格式 2

4

说明 2

该示例满足子任务 1, 2, 3, 4, 7 的条件。

输入格式 3

get_max_score(11, 8, [1, -3, 0, -2, 2, 7, -1, -1, -1, -2, -1], [5, 2, 10, 3, 2, 7, 4, 8, 7, 7, 10], [5, 4, 1, 3, 0, 8, 2, 3, 8, 5, 5], [5, 10, 8, 3, 2, 10, 1, 8, 10, 7, 8], [1, 4, 1, 7, 4, 8, 2, 8, 8, 6, 5])

输出格式 3

5

说明 3

该示例满足子任务 1, 2, 3, 4, 7 的条件。