题目描述

一个“fantastic IS”是一个整数序列，长度为$N$，其中每个元素都在$1$到$M$之间（包括边界值），满足以下条件。

• 对于每个整数$i$，$1 \\le i \\le K$，以下条件之一成立：
  • $A_{P_i} < X_i$ 并且 $A_{Q_i} < Y_i$；
  • $A_{P_i} = X_i$ 并且 $A_{Q_i} = Y_i$；
  • $A_{P_i} > X_i$ 并且 $A_{Q_i} > Y_i$。

判断是否存在一个“fantastic IS”。如果存在，则找出“fantastic IS”中元素的最小可能和。

约束条件

• $1 \\le N,M,K \\le 2 \\times 10^5$
• $1 \\le P_i,Q_i \\le N$
• $1 \\le X_i,Y_i \\le M$
• $P_i \\neq Q_i$
• 输入中的所有值均为整数。

输入

输入数据从标准输入读取，输入格式如下：

$N$ $M$ $K$ $P_1$ $X_1$ $Q_1$ $Y_1$ $P_2$ $X_2$ $Q_2$ $Y_2$ $\\vdots$ $P_K$ $X_K$ $Q_K$ $Y_K$

输出

如果存在一个“fantastic IS”，则输出“fantastic IS”中元素的最小可能和；否则输出$-1$。

示例输入1

3 4 3
3 1 1 2
1 1 2 2
3 4 1 4

示例输出1

6

$A=(2,3,1)$ 完全满足条件，因此是一个“fantastic IS”，其元素的和为$6$。

没有任何元素之和小于$6$的“fantastic IS”，因此答案是$6$。

示例输入2

2 2 2
1 1 2 2
2 1 1 2

示例输出2

-1

不存在任何“fantastic IS”，因此应输出$-1$。

示例输入3

5 10 10
4 1 2 7
5 1 3 2
2 9 4 4
5 4 2 9
2 9 1 9
4 8 3 10
5 7 1 5
3 5 1 2
3 8 2 10
2 9 4 8

示例输出3

12