Có lẽ bạn đã nghe câu chuyện kinh điển về Goldilocks và ba chú gấu. Tuy nhiên, ít ai biết rằng sau này Goldilocks đã chọn nghề nông. Trong trang trại của cô có một chuồng chứa \(N\) con bò (\(1 \le N \le 20\,000\)). Thật không may, những con bò của cô khá nhạy cảm với nhiệt độ.

Mỗi con bò \(i\) chỉ định một khoảng nhiệt độ \(A(i)..B(i)\) mà nó cảm thấy "vừa phải" (\(0 \le A(i) \le B(i) \le 1\,000\,000\,000\)). Nếu Goldilocks đặt bộ điều nhiệt trong chuồng ở nhiệt độ \(T < A(i)\), con bò sẽ quá lạnh và sản xuất \(X\) đơn vị sữa. Nếu cô đặt bộ điều nhiệt ở nhiệt độ \(T\) nằm trong khoảng này (\(A(i) \le T \le B(i)\)), con bò sẽ cảm thấy dễ chịu và sản xuất \(Y\) đơn vị sữa. Nếu cô đặt bộ điều nhiệt ở nhiệt độ \(T > B(i)\), con bò sẽ quá nóng và sản xuất \(Z\) đơn vị sữa. Đúng như dự đoán, \(Y\) luôn lớn hơn cả \(X\) và \(Z\).

Cho \(X\), \(Y\), \(Z\) cùng khoảng nhiệt độ ưa thích của mỗi con bò, hãy tính lượng sữa lớn nhất Goldilocks có thể thu được nếu cô cài đặt bộ điều nhiệt trong chuồng một cách tối ưu. Các giá trị \(X\), \(Y\) và \(Z\) là những số nguyên trong khoảng \(0..1000\), và bộ điều nhiệt có thể được đặt ở bất kỳ giá trị nguyên nào.

Dữ liệu vào

• Dòng 1 chứa bốn số nguyên cách nhau bởi dấu cách: \(N\), \(X\), \(Y\), \(Z\).
• Các dòng \(2..1+N\): dòng \(1+i\) chứa hai số nguyên cách nhau bởi dấu cách là \(A(i)\) và \(B(i)\).

Dữ liệu ra

• Dòng 1 chứa lượng sữa lớn nhất Goldilocks có thể thu được khi đặt nhiệt độ trong chuồng một cách tối ưu.

Phân nhóm

Trong 10 test của bài toán này:

• Các test \(1..4\) có \(B(i) \le 100\) với mọi con bò.
• Các test \(1..6\) có \(N \le 1000\).

Ví dụ

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

31

Nguồn

USACO 2013 November Contest, Bronze — Problem 2: Goldilocks and the N Cows

Tác giả đề: Brian Dean, 2013.