← 返回题目列表

AtCoder · arc146_d

D. 大于、等于或小于

中文机器翻译题面 查看原题

分数: 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