Giải bài trực tuyến Học viện Công nghệ Bưu chính Viễn Thông

Bạn có thể đã được nghe tới câu truyện huyền thoại về Goldilocks và ba con gấu. Có một điều mà ít người biết đến là, Goldilocks cuối cùng chọn nghề nông làm nghề mưu sinh của mình. Trên cánh đồng của cô ta, cô ta có một chuồng bò có N con bò (1 <= N <= 20 000). Không may thay, những con bò của cô ta rất nhạy cảm với nhiệt độ.

Mỗi con bò I có một khoảng nhiệt độ A(i)..B(i) là “vừa phải” (0 <= A(i) <= B(i) <= 10^9). Nếu Goldilocks chỉnh nhiệt độ trong chuồng một nhiệt độ T < A(i), con bò sẽ cảm thấy khá lạnh và chỉ sẽ sản xuất được X đơn vị sữa. Nếu cô ta chỉnh nhiệt độ trong khoảng A(i) <= T <= B(i), con bò sẽ cảm thấy thoải mái và sẽ sản xuất được Y đơn vị sữa. Nếu như cô ta chỉnh nhiệt độ trong chuồng T > B(i), con bò sẽ cảm thấy quá nóng và sẽ sản xuất được Z đơn vị sữa. Tất nhiên là Y sẽ lớn hơn X và Z.

Bạn được cho trước X,Y,Z cũng như là khoảng nhiệt độ ưa thích của từng con bò, hãy tính lượng sữa lớn nhất mà Goldilocks có thể có nếu như cô ta chỉnh nhiệt độ của chuồng bò một cách hợp lý. Giá trị của X, Y, Z sẽ nằm trong khoảng 0..1000, và nhiệt độ có thể được hiệu chỉnh theo một con số tự nhiên bất kì nào.

Input

*Dòng 1: Bốn số tự nhiên cách nhau: N X Y Z.

*Dòng thứ 2 tới N: Dòng thứ i chứa hai số tự nhiên cách nhau: A(i) và B(i).

Output

Số lượng sữa tối đa mà Goldilocks có thể đạt được khi cô ta chỉnh nhiệt độ một cách tối ưu.

Example

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

Output:
31

Giải thích test:
Có 4 con bò trong chuồng, với khoảng nhiệt ưa thích lần lượt là 5..8, 3..4, 13..20, và 7..10. 
Một con bò khi lạnh sẽ sản xuất 7 đơn vị sữa, khi thoải mái sẽ sản xuất 9 đơn vị sữa, và 
khi nóng sẽ sản xuất 6 đơn vị sữa.

Nếu Goldilocks chỉnh nhiệt độ là 7 hoặc 8, cô ta sẽ làm cho con bò thứ 1 và thứ 4 cảm thấy 
thoải mái, con bò thứ 2 thấy nóng, và thứ 3 thấy lạnh. Cô ta sẽ thu nhận được 31 đơn vị sữa.