C. Ухаалаг хуурагч

хугацааны хязгаарлалт 5 секунд

санах ойн хязгаарлалт 256 мегабайт

оролт стандарт оролт

гаралт стандарт гаралт

Би бодохдоо танд Нводскийн өвөл яг ч халуун биш гэдгийг сануулах хэрэггүй гэж бодном. Энэ нь нийтийн тээврээр үйлчлүүлэгчдийн тоог ихэсгэж байв. $62$-р автобусны чиглэлд нь яг $n$ ширхэг буудал байх бөгөөд $1$ дугаартай буудал дээрээс эхэлж явсаар $n$ дугаартай буудал дээр хамгийн сүүлд зогсох ажээ. Буудлууд нь шулуун дээр байрласан байх бөгөөд тэдгээрийн координатууд нь $0 = x_{1} < x_{2} < ... < x_{n}$ байх юм.

Өдөр болгон яг $m$ ширхэг хүн $62$-р автобусыг ашигладаг байв. Хүн болгоны хувьд та тухайн хүн нь ямар буудлаас уг автобусанд суухыг мөн ямар буудал дээр буухыг мэдэж байх ажээ. $a$-р буудлаас $b$-р ($a < b$) буудал хүртэлх тасалбар нь $x_{b} - x_{a}$ рублийн үнэтэй байна. Тэгсэн хэдий ч тасалбар шалгагч нь нэгээс ихгүй завсрыг сонгож болох бөгөөд автобус уг завсарт явж байх зуур билет зарахгүй байх юм. Тодруулбал тасалбар шалгагч C болон D (С <= D)-г сонгох ёстой бөгөөд [$A$, $C$] болон [$D$, $B$] сегментийн хооронд билет зарах юм. Эсвэл тэрээр бүхэл замын турш ч билет зарахгүй байж болно (энэ үед C болон D нь автобусны чиглэлийн эхлэл болон төгсгөлийн цэгүүд байна). Тасалбар шалгагч болон зорчигч нь тэдгээрийн олсон ашгаа тэнцүү хуваах ажээ. Өөрөөр хэлбэр тасалбар шалгагч билетийн үнийн талыг өөртөө ашиг болгон авах юм. Автобус ямар нэгэн дараалан байрласан 2 буудлын хооронд явж байх зуур тасалбар шалгагчийн уг "татвар төлөөгүй ашиг"-ийг зарим тохиолдолд хяналтын байцагчид илрүүлдэг байжээ. Ингэснээр байцаагч тасалбар шалгагчийг автобусны чиглэлийн уг сегментийн турш билетгүй зорчиж байгаа хүн бүрийн тоогоор $c$ рубль-ээр торгодог байв.

Та бүх буудлуудын координатууд болох $x_{i}$-ууд, $i$-р зорчигчийн автобусанд суух болон буух буудлын дугаар $a_{i}$ болон $b_{i}$ ($a_{i} < b_{i}$), байцаагчийн торгууль $c$ болон $i$-р болон $i + 1$-р буудлуудын хооронд байцаагч тасалбар шалгагчийг шалгах магадлал $p_{i}$-уудыг мэдэж байв. Одоо тасалбар шалгагч танаас түүний олох нийт орлогын хүлээгдэж буй утга нь хамгийн их байхаар билет зарах төлөвлөгөө гаргаж өгөхийг хүсжээ.

Оролт

Эхний мөрөнд 3-н бүхэл тоо $n$, $m$ болон $c$ ($2 ≤ n ≤ 150 000$, $1 ≤ m ≤ 300 000$, $1 ≤ c ≤ 10 000$) өгөгдөнө.

Дараагийн мөрөнд $n$ ширхэг бүхэл тоонууд $x_{i}$ ($0 ≤ x_{i} ≤ 10^{9}$, $x_{1} = 0$, $x_{i} < x_{i + 1}$)-ууд өгөгдөх ба эдгээр нь автобусны чиглэл дээрх буудлуудын координатуудыг илэрхийлнэ.

3-дахь мөрөнд $n - 1$ ширхэг бүхэл тоонууд $p_{i}$ ($0 ≤ p_{i} ≤ 100$)-ууд өгөгдөх ба эдгээр нь $i$-р болон $i + 1$-р буудлуудын хооронд байцаагч тасалбар шалгагчийг шалгах магадлалыг хувиар илэрхийлсэн утгууд байна.

Дараагийн $m$ ширхэг мөрөнд автобусны зорчигчдыг дүрсэлнэ. Мөр болгонд яг 2 ширхэг бүхэл тоо $a_{i}$ болон $b_{i}$ ($1 ≤ a_{i} < b_{i} ≤ n$)-ууд өгөгдөх эдгээр нь $i$-р зорчигчийн автобусанд суух болон буух буудлуудын дугааруудыг илэрхийлнэ.

Гаралт

Тасалбар шалгагчийн нийт орлогын хамгийн их хүлээгдэж буй утга болох ганц бодит тоо хэвлэнэ үү. Хэрэв таны хариултын абсолют болон харьцангуй алдаа $10^{ - 6}$-аас хэтрэхгүй байвал таны хариултыг зөвөөр тооцно.

Тодруулбал таны хариултыг $a$ шүүх хариултыг $b$ гэж үзье. Хэрэв байвал шалгагч программ нь таны хариултыг зөвөөр тооцох юм.

Орчуулсан: Баатархүү

Жишээ тэстүүд

Оролт
3 3 10
0 10 100
100 0
1 2
2 3
1 3
Гаралт
90.000000000
Оролт
10 8 187
0 10 30 70 150 310 630 1270 2550 51100
13 87 65 0 100 44 67 3 4
1 10
2 9
3 8
1 5
6 10
2 7
4 10
4 5
Гаралт
76859.990000000

Тэмдэглэл

Эхний жишээний тайлбарыг доор дүрслэв:

Эхний болон 3-дахь зорчигчид $1$-р буудлаас $2$-р буудал хүртэлх билет худалдан авна. Харин 2-дахь зорчигч билет худалдан авахгүй байна. Учир нь $1$-$2$ гэсэн сегмент дээр үргэлж шалгалт байх юм. Гэвч уг сегментээр явах үед автобусанд явж буй 2 зорчигч нь 2-уулаа билеттэй байна. Харин $2$-$3$ гэсэн сегмент дээр хэзээ ч шалгалт ирэхгүй бөгөөд ийм учраас 2-дахь зорчигч автобусанд билетгүй суусаар буух ажээ. Ингэснээр манай нийт орлого нь $(0 + 90 / 2 + 90 / 2) = 90$ болно.

Сэтгэгдлүүдийг ачааллаж байна...