33971번 - 비전 마법사 지환

문제

지환이는 사실 마법사다. 그는 현대 문명에 위협이 될 수 있는 엄청난 비전 마법의 소유자인데, 그 마법은 바로 컴퓨터 메모리에 저장된 비트를 마음대로 뒤집는 것이다. 이 사실을 눈치챈 종환이는 지환이가 세상에 선한 영향력을 행사할 수 있도록 능력에 대한 자신감을 떨어뜨리고자 마음먹고 지환이에게 한 가지 문제를 제시하였다.

"이봐, 0ドル$으로만 이루어진 길이 $N$의 정수열 $\{x_{n}\}$을 줄테니 최소한의 마력으로 모든 항을 1ドル$로 만들 수 있겠어?"

이를 듣자마자, 천재 마법사 지환이는 순식간에 $M$개의 마법진을 떠올렸다. 각 마법진은 두 양의 정수 $l_i$과 $r_i$에 대한 정보를 담고 있으며, 지환이는 떠올린 마법진들에 대해 1ドル$번째 마법진부터 $M$번째 마법진까지 순차적으로 다음 중 하나의 행동을 선택하여 실행한다.

• 마법진을 사용하지 않는다. 이 경우 마력을 소모하지 않는다.
• 마력을 $A$만큼 소모하여 1ドル \leq j \leq N$인 모든 정수 $j$에 대해, $l_i \leq j \leq r_i$를 만족하는 경우 $x_j$를 1ドル - x_j$로 설정한다.
• 마력을 $B$만큼 소모하여 1ドル \leq j \leq N$인 모든 정수 $j$에 대해, $l_i \leq j \leq r_i$를 만족하지 않는 경우 $x_j$를 1ドル - x_j$로 설정한다.

종환이는 지환이의 마음을 읽을 수 있기 때문에 미리 지환이의 성공 가능성을 예측하고자 한다. 종환이를 도와 지환이가 성공적으로 모든 항을 1ドル$로 만들 수 있는지 판단하고, 그렇다면 필요한 마력의 최솟값을 찾아보자!

입력

첫째 줄에 $N,ドル $M,ドル $A,ドル $B$가 공백으로 구분되어 주어진다. $(1 \leq N, M \leq 5,000円;$ 1ドル \leq A, B \leq 100,000円)$

둘째 줄부터 $M$개의 줄에 걸쳐 마법진의 정보가 주어진다. 각 줄에는 $i$번째 마법진을 나타내는 $l_{i}$와 $r_{i}$가 공백으로 구분되어 주어진다. $(1 \leq l_{i} \leq r_{i} \leq N)$

입력으로 주어지는 모든 수는 정수이다.

출력

첫째 줄에 지환이가 목표를 달성할 수 있다면 필요한 총 마력의 최솟값을 출력한다. 목표를 달성할 수 없다면 -1을 출력한다.

제한

힌트