Người soát vé thông minh

Tuyến xe buýt số 62 có đúng $n$ trạm dừng, được đánh số $1,2,\dots ,n$ theo thứ tự chạy. Các trạm nằm trên một đường thẳng với tọa độ $0=x_1<x_2<\cdots <x_n$. Vé đi từ trạm $a$ đến trạm $b$ (với $a<b$) có giá $x_b-x_a$ rúp.

Mỗi ngày có đúng $m$ hành khách sử dụng tuyến. Hành khách thứ $i$ lên tại trạm $a_i$ và xuống tại trạm $b_i$ ($a_i<b_i$).

Người soát vé có thể chọn không quá một đoạn liền mạch để không bán vé. Cụ thể, với mỗi hành khách anh ta chọn hai chỉ số $C,D$ với $a_i\le C\le D\le b_i$ rồi chỉ bán vé cho hai đoạn $[a_i,C]$ và $[D,b_i]$; nếu chọn $C=D$ thì tương đương với bán vé đầy đủ. Số tiền tiết kiệm được là $x_D-x_C$, và người soát vé chia đôi khoản đó với hành khách (mỗi người nhận $(x_D-x_C)/2$).

Tuy nhiên, thanh tra có thể xuất hiện trên một đoạn giữa hai trạm liên tiếp. Xác suất có thanh tra trên đoạn giữa trạm $j$ và trạm $j+1$ là $p_j/100$. Nếu có thanh tra trên đoạn đó và một hành khách không có vé cho đoạn đó, người soát vé bị phạt $c$ rúp cho hành khách đó.

Hãy giúp người soát vé lập kế hoạch bán vé sao cho kỳ vọng lợi nhuận thu được là lớn nhất.

Dữ liệu vào

• Dòng đầu tiên chứa ba số nguyên $n$, $m$, $c$.
• Dòng thứ hai chứa $n$ số nguyên $x_1,x_2,\dots ,x_n$.
• Dòng thứ ba chứa $n-1$ số nguyên $p_1,p_2,\dots ,p_{n-1}$.
• $m$ dòng tiếp theo, mỗi dòng chứa hai số $a_i$, $b_i$ mô tả hành khách thứ $i$.

Dữ liệu ra

Một số thực duy nhất — kỳ vọng lợi nhuận lớn nhất của người soát vé. Đáp án được xem là đúng nếu sai số tuyệt đối hoặc tương đối không vượt quá ${10}^{-6}$.

Ràng buộc

• $2\le n\le 150,000$
• $1\le m\le 300,000$
• $1\le c\le 10,000$
• $0\le x_i\le {10}^9$, $x_1=0$, $x_i<x_{i+1}$
• $0\le p_j\le 100$
• $1\le a_i<b_i\le n$

Ví dụ