006 - Min-Max Propagation

問題文

　長さ $N$ の数列 $A = (1, 2, \dots, N)$ があります。あなたには $M$ 個の魔法が与えられています。 各魔法 $i$ ($1 \le i \le M$) は種類 $T_i \in \{0, 1\}$、区間 $[L_i, R_i]$、消費体力 $C_i$ で表され、以下の効果を持ちます。

• $T_i = 0$: 区間 $[L_i, R_i]$ を選び、その区間内のすべての要素を、現在の $A_{L_i}, A_{L_i+1}, \dots, A_{R_i}$ の中の最小値に置き換える。体力を $C_i$ 消費する。
• $T_i = 1$: 区間 $[L_i, R_i]$ を選び、その区間内のすべての要素を、現在の $A_{L_i}, A_{L_i+1}, \dots, A_{R_i}$ の中の最大値に置き換える。体力を $C_i$ 消費する。

　魔法は好きな順番で何度でも使うことができます。あなたの目標は、数列の $X$ 番目の要素を $Y$ にすること（すなわち $A_X = Y$ とすること）です。目標を達成するために消費する体力の合計の最小値を求めてください。どのように魔法を使っても達成不可能な場合は -1 を出力してください。

制約

• $2 \le N \le 2 \times 10^5$
• $1 \le M \le 2 \times 10^5$
• $1 \le X, Y \le N$
• $X \neq Y$
• $T_i \in \{0, 1\}$
• $1 \le L_i \le R_i \le N$
• $1 \le C_i \le 10^9$
• 入力はすべて整数

入出力

入力

入力は以下の形式で標準入力から与えられる。

N M X Y
T_1 L_1 R_1 C_1
T_2 L_2 R_2 C_2
:
T_M L_M R_M C_M

出力

　目標を達成するために消費する体力の合計の最小値を出力せよ。どのように魔法を使っても達成不可能な場合は -1を出力せよ。

サンプル

入力例 1

5 4 5 2
0 2 3 10
0 3 5 20
1 2 4 5
0 1 5 100

出力例 1

30

提出

提出はこちらから行えます。