CF150C.Smart Cheater

I guess there's not much point in reminding you that Nvodsk winters aren't exactly hot. That increased the popularity of the public transport dramatically. The route of bus 62 has exactly n stops (stop 1 goes first on its way and stop n goes last). The stops are positioned on a straight line and their coordinates are 0 = _x_1 < _x_2 < ... < x__n.

Each day exactly m people use bus 62. For each person we know the number of the stop where he gets on the bus and the number of the stop where he gets off the bus. A ticket from stop a to stop b (a < b) costs x__b - x__a rubles. However, the conductor can choose no more than one segment NOT TO SELL a ticket for. We mean that conductor should choose C and D (С <= D) and sell a ticket for the segments [A, C] and [D, B], or not sell the ticket at all. The conductor and the passenger divide the saved money between themselves equally. The conductor's "untaxed income" is sometimes interrupted by inspections that take place as the bus drives on some segment of the route located between two consecutive stops. The inspector fines the conductor by c rubles for each passenger who doesn't have the ticket for this route's segment.

You know the coordinated of all stops x__i; the numbers of stops where the i-th passenger gets on and off, a__i and b__i (a__i < b__i); the fine c; and also p__i — the probability of inspection on segment between the i-th and the i + 1-th stop. The conductor asked you to help him make a plan of selling tickets that maximizes the mathematical expectation of his profit.

我想没必要再提醒你，Nvodsk 的冬天可一点也不暖和。这使得公共交通的受欢迎程度急剧上升。62 路公交车的路线恰好有 $n$ 个站点（第 1 站是线路起点，第 $n$ 站是终点）。这些站点位于一条直线上，其坐标满足 $0 = x_1 < x_2 < \dots < x_n$。

每天恰好有 $m$ 名乘客乘坐 62 路公交车。对每位乘客，我们已知其上车站点编号和下车站点编号。从站点 $a$ 到站点 $b$（其中 $a < b$）的车票价格为 $x_b - x_a$ 卢布。然而，售票员最多可以选择一个区间不售出车票：即售票员需选定 $C$ 和 $D$（满足 $C \le D$），并仅出售区间 $[A, C]$ 和 $[D, B]$ 上的车票；或者干脆整段都不出售车票。售票员与乘客将因此节省的金额平分。售票员的“未申报收入”有时会因检查而中断——检查发生在公交车行驶于某两个相邻站点之间的路段上。对于每个在该路段上没有对应车票的乘客，检查员将向售票员处以 $c$ 卢布的罚款。

你已知所有站点的坐标 $x_i$；第 $i$ 位乘客的上车站点与下车站点编号 $a_i$ 和 $b_i$（满足 $a_i < b_i$）；罚款金额 $c$；以及 $p_i$ —— 在第 $i$ 个站点与第 $i+1$ 个站点之间路段发生检查的概率。售票员请你帮他制定一个车票销售方案，以最大化其收益的数学期望值。

The first line contains three integers n, m and c (2 ≤ n ≤ 150 000, 1 ≤ m ≤ 300 000, 1 ≤ c ≤ 10 000).

The next line contains n integers x__i (0 ≤ x__i ≤ 109, _x_1 = 0, x__i < x__i + 1) — the coordinates of the stops on the bus's route.

The third line contains n - 1 integer p__i (0 ≤ p__i ≤ 100) — the probability of inspection in percents on the segment between stop i and stop i + 1.

Then follow m lines that describe the bus's passengers. Each line contains exactly two integers a__i and b__i (1 ≤ a__i < b__i ≤ n) — the numbers of stops where the i-th passenger gets on and off.

第一行包含三个整数 $n$、$m$ 和 $c$（满足 $2 \leq n \leq 150\,000$，$1 \leq m \leq 300\,000$，$1 \leq c \leq 10\,000$）。

第二行包含 $n$ 个整数 $x_i$（满足 $0 \leq x_i \leq 10^9$，$x_1 = 0$，且 $x_i < x_{i+1}$），表示公交车路线上的各站点坐标。

第三行包含 $n-1$ 个整数 $p_i$（满足 $0 \leq p_i \leq 100$），表示在第 $i$ 站与第 $i+1$ 站之间路段进行检查的概率（以百分比表示）。

接下来是 $m$ 行，描述公交车的乘客信息。每行恰好包含两个整数 $a_i$ 和 $b_i$（满足 $1 \leq a_i < b_i \leq n$），表示第 $i$ 位乘客上车和下车的站点编号。

Print the single real number — the maximum expectation of the conductor's profit. Your answer will be considered correct if its absolute or relative error does not exceed 10 - 6.

Namely: let's assume that your answer is a, and the answer of the jury is b. The checker program will consider your answer correct, if .

输出一个实数——指挥家利润的最大期望值。若你的答案的绝对或相对误差不超过 $10^{-6}$，则视为正确。

即：假设你的答案为 $a$，评测组的答案为 $b$。当满足 时，评测程序将判定你的答案正确。

A comment to the first sample:

The first and third passengers get tickets from stop 1 to stop 2. The second passenger doesn't get a ticket. There always is inspection on the segment 1-2 but both passengers have the ticket for it. There never is an inspection on the segment 2-3, that's why the second passenger gets away with the cheating. Our total profit is (0 + 90 / 2 + 90 / 2) = 90.

对第一个样例的说明：

第一位和第三位乘客购买了从第 1 站到第 2 站的车票。第二位乘客没有购票。区间 $1\text{-}2$ 上始终有检票，但两位乘客均持有该区间的有效车票。区间 $2\text{-}3$ 上从不检票，因此第二位乘客的逃票行为未被发现。我们的总收益为 $(0 + 90 / 2 + 90 / 2) = 90$。