Có lẽ biết Goldilocks và ba con gấu. Sau đó cô thành nông dân, có $N$ bò ($(1 \le N \le 20,000)$) trong chuồng, nhạy cảm nhiệt độ.

Bò $i$ thích $A(i)..B(i)$ ($0 \le A(i) \le B(i) \le 10^9$). Với $T < A(i)$ lạnh và cho $X$; $T$ trong khoảng ($A(i) \le T \le B(i)$) thoải mái và $Y$; $T > B(i)$ nóng và $Z$. $Y$ luôn lớn hơn $X$, $Z$.

Từ $X$, $Y$, $Z$ và khoảng, tính sữa tối đa với nhiệt độ tối ưu. $X$, $Y$, $Z$ nguyên trong 0..1000, nhiệt độ có thể là số nguyên bất kỳ.

Dữ liệu vào

• Dòng 1: bốn số nguyên $N$ $X$ $Y$ $Z$ cách nhau bởi khoảng trắng.
• Dòng $2..1+N$: dòng $1+i$ chứa số nguyên $A(i)$ và $B(i)$ cách nhau bởi khoảng trắng.

Dữ liệu ra

• Dòng 1: sữa tối đa với nhiệt độ tối ưu.

Ví dụ

Dữ liệu vào 1

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

Dữ liệu ra 1

31

Ghi chú

Bốn khoảng: 5..8, 3..4, 13..20, 7..10. Lạnh cho 7, thoải mái 9, nóng 6 đơn vị.

Ở 7 hoặc 8, #1 và #4 thoải mái, #2 nóng và #3 lạnh, tổng 31.

Nhiệm vụ con

Điểm phần: trong 10 bộ, 1..4 mọi $B(i) \le 100$, 1..6 $N$ tối đa 1000.

Tác giả bài toán: Brian Dean, 2013