题目描述

長さ $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$ $\vdots$ $P_K$ $X_K$ $Q_K$ $Y_K$

输出格式

「素晴らしい整数列」が存在する場合は「素晴らしい整数列」の要素の総和としてあり得る最小値を、「素晴らしい整数列」が存在しない場合は $-1$ を出力せよ。

题目大意

求构造一个长度为 $n$ 而每个数取 $[1,m]$ 之间的“完美序列”$A$ ，使得其中所有数之和最小化。如果不存在，输出 $-1$ 。

完美序列的定义：对于所有 $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$ 。

$1\le n,m,k\le 2\times 10^5$ 。数据合法。

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

6

2 2 2
1 1 2 2
2 1 1 2

-1

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$
• 入力は全て整数である。

Sample Explanation 1

$A=(2,3,1)$ は全ての条件を満たすので「素晴らしい整数列」です。この場合要素の総和は $6$ です。 要素の総和が $5$ 以下の「素晴らしい整数列」は存在しないため、解は $6$ です。

Sample Explanation 2

「素晴らしい整数列」は存在しないため、$-1$ を出力します。