MILKTEMP - Best Temperature
Trong một trang trại có N chú bò. Các chú bò rất nhạy cảm với nhiệt độ.
Mỗi chú bò i có một khoảng nhiệt độ nhất định Ai .. Bi mà chúng có thể thấy thoải mái. Nếu gặp nhiệt độ T < Ai, chú bò sẽ thấy quá lạnh và sản xuất X đơn vị sữa. Nếu gặp nhiệt độ T nằm trong khoảng nhiệt độ này Ai ≤ T ≤ Bi chú bò sẽ sản xuất Y đơn vị sữa. Nếu nhiệt độ T > Bi, chú bò sẽ thấy quá nóng và sản xuất Z đơn vị sữa. Giá trị Y sẽ luôn lớn hơn cả X và Z.
Cho các giá trị X, Y và Z cũng như vùng nhiệt độ của mỗi chú bò, bạn hãy tính tổng lượng sữa lớn nhất có thể đạt được nếu nhiệt độ được đặt một cách tối ưu.
Input
Dòng một chứa 4 số nguyên N X Y Z.
N dòng tiếp, dòng thứ i chứa hai số nguyên Ai và Bi
Output
Ghi ra lượng sữa lớn nhất có thể đạt được
Giới hạn
- 1 ≤ N ≤ 20,000
- 1 ≤ Ai ≤ Bi ≤ 109
- 0 ≤ X, Y, Z ≤ 1000
- 40% số test có Bi ≤ 100
- 60% số test có N ≤ 1000
Ví dụ
Input: 4 7 9 6 5 8 3 4 13 20 7 10 Output: 31
Giải thích
Nhiệt độ tối ưu sẽ bằng 7 hoặc 8. Khi đó chú bò thứ 1 và thứ 4 sẽ thoải mái, chú bò thứ 2 cảm thấy nóng và chú bò thứ 3 cảm thấy lạnh. Số lượng sữa đạt được: 9 × 2 + 7 + 6 = 31
Added by: | Tran Dang Tuan Anh |
Date: | 2013-12-10 |
Time limit: | 2s |
Source limit: | 50000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Languages: | All except: ASM64 |
Resource: | Online contest |