分数: 800 点
问题陈述
A 太棒了 是长度的整数序列 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.
确定是否存在一个奇妙的IS。如果确实如此,请找到一个奇妙的 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
输出
如果存在一个幻想 IS,则打印幻想 IS 中元素的最小可能总和;否则,打印 -1.
示例输入 1
3 4 3 3 1 1 2 1 1 2 2 3 4 1 4
示例输出 1
6
A=(2,3,1) 完全满足条件,因此是一个奇妙的 IS,其元素之和为 6.
没有一个奇妙的 IS 的元素总和小于 6,所以答案是 6.
示例输入 2
2 2 2 1 1 2 2 2 1 1 2
示例输出 2
-1
没有出色的 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