Наверное, нет уже смысла напоминать, что этой зимой в городе XXXводске совсем не жарко. В связи с этим резко возросла популярность общественного транспорта. На маршруте 62-го автобуса в точности n остановок (причем остановка номер 1 — первая на пути, а номер n — последняя). Остановки расположены на одной прямой и имеют координаты 0 = x1 < x2 < ... < xn.
Каждый день 62-ым автобусом пользуются ровно m человек. Для каждого человека известен номер остановки, на которой он садится, и номер остановки, на которой он выходит. Билет от остановки a до остановки b (a < b) стоит xb - xa рублей. Однако кондуктор может не продать пассажиру билет от остановки c до остановки d (c < d), или вовсе не продавать билет. Более формально: Кондуктор выбирает не более одного отрезка с C по D (C <= D) на который он НЕ ПРОДАЕТ БИЛЕТ. То есть пассажир имеет билет на отрезках [A, C] и [D, B]. Сэкономленные деньги кондуктор и пассажир делят поровну. Заработку кондуктора мешают постоянные проверки, случающиеся во время перегонов между двумя последовательными остановками. За каждого пассажира, не имевшего билет на проезд этого перегона, проверка берет с кондуктора штраф c рублей.
Вам известны координаты всех остановок xi; номера остановок, на которых заходит и выходит i-ый пассажир, ai и bi (ai < bi); штраф c; а также pi — вероятность того, что на перегоне между i-ой и i + 1-ой остановкой произойдет проверка. Кондуктор попросил вас помочь ему составить план продажи билетов, максимизирующий математическое ожидание его прибыли.
Выходные данные
Выведите одно вещественное число — максимальное математическое ожидание прибыли кондуктора. Ответ будет считать верным, если его относительная или абсолютная погрешность не превосходит 10 - 6.
Примечание
Комментарий к первому примеру:
Первому и третьему пассажиру продаем билет с остановки 1 до остановки 2. Второму пассажиру билет не продаем. На перегоне 1-2 проверка появляется всегда, но у обоих пассажиров будет билет на него. На перегоне 2-3 проверка не появляется никогда, поэтому второго пассажира никто не поймает. Итого наша прибыль (0 + 90 / 2 + 90 / 2) = 90.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3 3 10
0 10 100
100 0
1 2
2 3
1 3
|
90.000000000
|
|
2
|
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
|