题目描述

我们称长度为 $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

输入

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

输出

6

样例 2

输入

2 2 2
1 1 2 2
2 1 1 2

输出

-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

输出

12

说明/提示

数据范围

• $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 翻译