АЛГОРИТМЫН ЦАГААН ТОЛГОЙ

Та Алтан шаргал үст охин болон 3 баавгайн үлгэрийг сонссон байх.

Юутай ч Алтан шаргал үст охин мал маллах тал дээр мэргэшсэн нэгэн юм.

Тэр фермдээ N ширхэг (1 <= N <= 20’000) үнээтэй бөгөөд тэдгээр нь халуун хүйтэнд их мэдрэмтгий.

i дугаар үнээнд A[i]-аас B[i] хүртэлх температурын муж “яг таарна” (0 <= A[i] <= B[i] <= 1’000’000’000).

Хэрэв Алтан шаргал үст охин термостатыг T < A[i] байх температур дээр тааруулвал i дугаар үнээ хэт даарч X литр сүү өгнө.

Хэрэв A[i] <= T <= B[i] байх температур дээр тааруулвал i дугаар үнээнд температур “яг таарч” Y литр сүү өгнө.

Хэрэв T > B[i] байх температур дээр тааруулвал i дугаар үнээ хэт халууцаж Z литр сүү өгнө.

Y нь ямагт X болон Z тооноос их байна.

Та X, Y, Z (0 <= X, Y, Z <= 1’000) болон үнээ болгоны A[i], B[i] тоонуудыг мэдэж байгаа бол тохиромжтой температурыг тааруулаад авч болох хамгийн их сүүний хэмжээг олно уу.

Input

Эхний мөр: N, X, Y, Z бүхэл тоонууд зайгаар тусгаарлагдан өгөгдөнө.

2-оос (1+N) дүгээр мөр: (1+i) дугаар мөр бүрт i дугаар үнээний A[i], B[i] бүхэл тоонууд өгөгдөнө.

Output

Эхний мөр: Авч болох хамгийн их сүүний хэмжээ.

Example

Input:

4 7 9 6

5 8

3 4

13 20

7 10

Output:

31

Тайлбар:

Термостатыг 7 эсвэл 8 градус дээр тааруулвал 1-р үнээнээс 9 литр; 2-р үнээнээс 6 литр; 3-р үнээнээс 7 литр; 4-р үнээнээс 9 литр сүүнүүдийг авснаар

9 + 6 + 7 + 9 = 31 литр сүү авч чадна.

Орчуулсан : УБ 1-р сургуулийн 11-р ангийн сурагч Б.Мөнх-Оргил 2019.11.15