Informatica Online Judge

  지하철 2호선 [1125 / 0465]

Time Limit(Test case) : 1000(ms)
Number of users who solved : 24   Total Tried : 174


The Champion of this Problem (C++) : gs18103 - ms / 520byte
My Best Submission (C++) : N/A

[koistudy.net (32nd 구재현)]

Background

서울 지하철 2호선은 원형으로 된 전철 노선으로써, 매일 엄청난 사람들을 수송시켜주는 명실상부한 서울 교통의 핵심 축이다.

하지만 너무 수요가 많아서 기차에 잔고장이 잦아지고 역이 사람으로 가득차는 일들이 벌어지자, 결국 오랜 고심끝에 정부는 안전을 위해 수요가 많은 부분만 민영화시키고 나머지 부분을 폐선시키기로 결정했다.


폐지하지 않고 민영화 시킬 부분을 결정하기 위해서, 정부는 M (1 <= M <= 500000) 명의 측근을 모아서 각 사람들이 자주 타는 전철 구간을 조사했다.

측근들은 자신이 자주 타는 전철 구간이 그대로 존재할 경우, 역 1개 당 A만큼의 만족도가 증가한다.

하지만, 자신이 자주 타는 전철 구간이 존재하지 않을 경우, 역 1개 당 B만큼 만족도가 감소한다.

또한, 남의 땅에 전철이 있으면 배가 아프므로, 자신이 자주 타는 전철 구간이 아닌 구간에 전철이 있을 경우 역시 역 1개 당 B만큼 만족도가 감소한다.

정부는 이 데이터들을 모두 모은 후 O(N^2 * M) 알고리즘을 돌려 기다렸지만, 몇 시간 뒤에 컴퓨터가 자동 업데이트 때문에 종료되어서 결국 koistudy에 도움을 요청했다.

정부는 만족도가 최대인 구간을 민영화하고 싶어하기에, 여러분이 할 일은 최대 만족도를 출력하는 프로그램을 만들어 정부를 도와주는 것이다.

Input

첫번째 줄에 역의 수, 측근의 수, 만족도 감소율, 만족도 증가율 (N,M,A,B)가 주어진다. 역은 1,2,3...N 순으로 번호가 붙어 있으며 N 역의 다음 역은 1 역이다.

이후 M개의 줄에 각각의 측근이 자주 타는 구간 Si, Ei가 주어진다. (1 <= Si , Ei <= N)
Si <= Ei 인 경우 이 측근은 Si, Si+1 ... Ei 구간을 자주 타는 것이며,
Ei < Si인 경우 이 측근은 Ei,Ei+1 ... N,1 .. Si 구간을 자주 타는 것이다.

[입력값의 정의역]
1 <= N <= 500,000
1 <= M <= 500,000
A,B <= 10,000

[Sub-Task Info]
- 20%의 데이터는 N <= 1,000, M <= 1,000 을 만족한다.
- 20%의 데이터는 N <= 1,000, M <= 500,000
- 60%의 데이터는 추가적인 제한조건이 없다.

Output

얻을 수 있는 최대 만족도를 출력한다. 만약 만족도가 0 이하일 경우 "FAIL"을 출력한다. 출력값은 64비트 정수형 범위를 넘지 않는다.

IO Example

입력1
10 5 5 3
1 3
2 5
3 6
3 7
4 8

출력1
56

입력2
10 5 3 5
1 3
2 5
3 6
3 7
4 8

출력2
FAIL

Submit : [C/C++] | [C++11] | [Obj-C] | [Java] | [Python]
Prob Analysis : [Problem Statistics] | [Solution]