20XX 年，IOI 终于要在 JOI 国的 JOI 町举行了，为了纪念这一盛事，决定举办一场派对。JOI 町里有 $A$ 只狗（编号为 $1, 2, \dots, A$）和 $B$ 只猫（编号为 $1, 2, \dots, B$）。你打算邀请这 $A+B$ 只动物全部参加派对。

狗和猫之间存在 $N$ 个“友好小组”。第 $i$ 个友好小组由编号在 $P_i$ 到 $Q_i$ 之间的 $Q_i - P_i + 1$ 只狗，以及编号在 $R_i$ 到 $S_i$ 之间的 $S_i - R_i + 1$ 只猫组成。此外，每个友好小组都有一个称为“友好度”的正整数。第 $i$ 个友好小组的友好度为 $T_i$。一只狗或一只猫可能属于多个友好小组，也可能不属于任何友好小组。

你与编号为 $C$ 的狗关系非常好，并且已经成功邀请了它。你决定通过重复以下行动来邀请剩下的狗和猫：

• 如果 $A+B$ 只动物都已经成功邀请，则结束。
• 对于每只尚未被邀请的狗或猫，考虑邀请它时的“幸福值”。幸福值定义为：在该动物所属的所有友好小组中，已经成功邀请的狗或猫（至少 1 只）所属的友好小组的最大友好度。如果不存在这样的友好小组，则幸福值为 0。
• 选择幸福值最大的狗或猫。如果存在多只这样的狗或猫，优先选择狗；如果仍然无法确定唯一的一只，则优先选择编号较小的。
• 如果选出的狗或猫的幸福值为 0，则邀请失败并结束。否则，成功邀请该狗或猫。

你决定预先计算出这种邀请方法的结果。

题目描述

给定狗的数量 $A$、猫的数量 $B$、与你关系非常好的狗的编号 $C$，以及 $N$ 个友好小组的信息，判断是否能成功邀请全部 $A+B$ 只动物。如果能成功，求出在每一步中选出的狗或猫的幸福值之和。

输入格式

从标准输入读取以下内容：

• 第 1 行包含三个整数 $A, B, C$ ($1 \le C \le A$)，分别表示狗的数量、猫的数量以及与你关系非常好的狗的编号，以空格分隔。
• 第 2 行包含一个整数 $N$，表示友好小组的数量。
• 第 $2+i$ 行 ($1 \le i \le N$) 包含五个整数 $P_i, Q_i, R_i, S_i, T_i$ ($1 \le P_i \le Q_i \le A, 1 \le R_i \le S_i \le B$)，以空格分隔，表示第 $i$ 个友好小组由编号在 $P_i$ 到 $Q_i$ 之间的狗和编号在 $R_i$ 到 $S_i$ 之间的猫组成，友好度为 $T_i$。

输出格式

输出一个整数到标准输出：

• 如果成功邀请全部 $A+B$ 只动物，输出每一步选出的狗或猫的幸福值之和。
• 如果邀请中途失败，输出 -1。

数据范围

• $1 \le A \le 1\,000\,000\,000$
• $1 \le B \le 1\,000\,000\,000$
• $1 \le N \le 100\,000$
• $1 \le T_i \le 1\,000\,000\,000$

子任务

• 对于配分 30% 的测试数据，满足 $A \le 1\,000, B \le 1\,000, N \le 2\,000$。
• 对于配分 50% 的测试数据，满足 $N \le 2\,000$。

样例

样例 1

输入：

5 6 3
4
2 4 1 3 20
1 2 2 4 40
4 5 2 3 30
4 4 4 6 10

输出：

280

样例 2

输入：

10 10 1
2
1 5 1 5 3
6 10 6 10 4

输出：

-1