AT_arc146_d [ARC146D] >=<

我们称长度为 $N$ 且所有元素均为 $1$ 到 $M$ 之间的整数序列 $A=(A_1,A_2,\dots,A_N)$，满足以下所有条件的序列为“素晴らしい整数列”： - 对于每个满足 $1 \le i \le K$ 的整数 $i$，以下三种情况之一成立： - $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$ 请判断是否存在“素晴らしい整数列”，如果存在，请求出所有可能的“素晴らしい整数列”中元素和的最小值。

输入通过标准输入给出，格式如下： > $N$ $M$ $K$ $P_1$ $X_1$ $Q_1$ $Y_1$ $P_2$ $X_2$ $Q_2$ $Y_2$ $\cdots$ $P_K$ $X_K$ $Q_K$ $Y_K$

如果存在“素晴らしい整数列”，输出其元素和的最小可能值；如果不存在，输出 $-1$。

### 数据范围 - $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$ - 所有输入均为整数。 ### 样例解释 1 $A=(2,3,1)$ 满足所有条件，因此是“素晴らしい整数列”。此时元素和为 $6$。不存在元素和小于等于 $5$ 的“素晴らしい整数列”，所以答案为 $6$。 ### 样例解释 2 不存在“素晴らしい整数列”，因此输出 $-1$。 由 ChatGPT 4.1 翻译