Time Limit: 4 sec / Memory Limit: 1024 MB
配点 : 800 点
問題文
長さ 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
「素晴らしい整数列」が存在するか判定し、存在するならば「素晴らしい整数列」の要素の総和としてあり得る最小値を求めてください。
制約
- 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
出力
「素晴らしい整数列」が存在する場合は「素晴らしい整数列」の要素の総和としてあり得る最小値を、「素晴らしい整数列」が存在しない場合は -1 を出力せよ。
入力例 1
3 4 3 3 1 1 2 1 1 2 2 3 4 1 4
出力例 1
6
A=(2,3,1) は全ての条件を満たすので「素晴らしい整数列」です。この場合要素の総和は 6 です。
要素の総和が 5 以下の「素晴らしい整数列」は存在しないため、解は 6 です。
入力例 2
2 2 2 1 1 2 2 2 1 1 2
出力例 2
-1
「素晴らしい整数列」は存在しないため、-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
Score : 800 points
Problem Statement
A fantastic IS is an integer sequence of length N whose every element is between 1 and M (inclusive) that satisfies the following condition.
- For every integer i such that 1 \le i \le K, one of the following holds.
- A_{P_i} < X_i and A_{Q_i} < Y_i;
- A_{P_i} = X_i and A_{Q_i} = Y_i;
- A_{P_i} > X_i and A_{Q_i} > Y_i.
Determine whether a fantastic IS exists. If it does, find the minimum possible sum of the elements in a fantastic IS.
Constraints
- 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
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
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
Output
If a fantastic IS exists, print the minimum possible sum of the elements in a fantastic IS; otherwise, print -1.
Sample Input 1
3 4 3 3 1 1 2 1 1 2 2 3 4 1 4
Sample Output 1
6
A=(2,3,1) fully satisfies the condition and thus is a fantastic IS, whose sum of the elements is 6.
There is no fantastic IS whose sum of the elements is less than 6, so the answer is 6.
Sample Input 2
2 2 2 1 1 2 2 2 1 1 2
Sample Output 2
-1
There is no fantastic IS, so -1 should be printed.
Sample Input 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
Sample Output 3
12