Goldilocks와 세 곰 이야기를 들어봤을 것이다. 그녀는 나중에 농부가 되어 헛간에 소 $N$마리 ($(1 \le N \le 20,000)$)를 키우며 소는 온도에 민감하다.

소 $i$의 적정 온도는 $A(i)..B(i)$ ($0 \le A(i) \le B(i) \le 10^9$)이다. $T < A(i)$면 추워 생산량 $X$, $T$가 범위 내 ($A(i) \le T \le B(i)$)면 편안해 $Y$, $T > B(i)$면 더워 $Z$이다. $Y$는 항상 $X$와 $Z$보다 크다.

$X$, $Y$, $Z$와 각 적정 범위로 최적 온도 설정의 최대 우유량을 구하라. $X$, $Y$, $Z$는 0..1000 범위 정수이며 온도는 임의의 정수로 설정할 수 있다.

입력

• 1번 줄: 공백으로 구분한 네 정수 $N$ $X$ $Y$ $Z$.
• $2..1+N$번 줄: $1+i$번 줄은 공백으로 구분한 두 정수 $A(i)$, $B(i)$이다.

출력

• 1번 줄: 최적 온도 설정의 최대 우유량.

예제

입력 1

4 7 9 6
5 8
3 4
13 20
7 10

출력 1

31

참고

범위는 5..8, 3..4, 13..20, 7..10이다. 추우면 7, 편안하면 9, 더우면 6 단위 생산한다.

7 또는 8이면 #1, #4가 편안하고 #2는 덥고 #3은 추워 총 31이다.

서브태스크

부분 점수: 10개 테스트 중 1..4는 모든 소에 $B(i) \le 100$, 1..6은 $N$이 최대 1000이다.

문제 출제자: Brian Dean, 2013