C. Хитрый жук
ограничение по времени на тест
5 seconds
ограничение по памяти на тест
256 megabytes
ввод
стандартный ввод
вывод
стандартный вывод

Наверное, нет уже смысла напоминать, что этой зимой в городе 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-ой остановкой произойдет проверка. Кондуктор попросил вас помочь ему составить план продажи билетов, максимизирующий математическое ожидание его прибыли.

Входные данные

Первая строка содержит три целых числа n, m и c (2 ≤ n ≤ 1.5·105, 1 ≤ m ≤ 3·105, 1 ≤ c ≤ 104).

Следующая строка содержит n целых чисел xi (0 ≤ xi ≤ 109, x1 = 0, xi < xi + 1) — координаты остановок вдоль маршрута автобуса.

Третья строка содержит n - 1 целое число pi (0 ≤ pi ≤ 100) – вероятность в процентах появления кондуктора на перегоне между остановкой i и остановкой i + 1.

Далее следуют m строк, описывающие пассажиров автобуса, каждая строка содержит ровно два целых числа ai и bi (1 ≤ ai < bi ≤ n) — номера остановок, на которых заходит и выходит i-ый пассажир.

Выходные данные

Выведите одно вещественное число — максимальное математическое ожидание прибыли кондуктора. Ответ будет считать верным, если его относительная или абсолютная погрешность не превосходит 10 - 6.

Примеры
Входные данные
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
Примечание

Комментарий к первому примеру:

Первому и третьему пассажиру продаем билет с остановки 1 до остановки 2. Второму пассажиру билет не продаем. На перегоне 1-2 проверка появляется всегда, но у обоих пассажиров будет билет на него. На перегоне 2-3 проверка не появляется никогда, поэтому второго пассажира никто не поймает. Итого наша прибыль (0 + 90 / 2 + 90 / 2) = 90.