Green Energy

Flatland is building solar power stations of a new type this year. The panels are not laid on the ground. They are mounted on the sides of tall towers, all the way up.

There are $n$ towers to mount, and they are already bought. The height of the $i$-th tower is $h_i$. The engineers now want to choose the points where the towers stand so that the total power is as large as possible.

The landscape of the plant territory is given as a polyline with $m$ vertices. The vertices have coordinates $(x_i, y_i)$ with $x_i < x_{i+1}$. A tower stands vertically at a point of this landscape, and the $x$ coordinate of that point may be any real number between $x_1$ and $x_m$.

The sun angle in Flatland is always $\alpha$ degrees. The sun shines from the top left to the bottom right, and all rays are parallel to each other and make an angle of $\alpha$ degrees with the horizontal. The power produced by a tower is the length of its surface that the sun lights up. In other words, take the vertical segment that represents the tower: the power is the length of the part of that segment which a ray reaches without being blocked by the landscape or by another tower.

When two towers stand close to each other, the shadow of the left tower can fall onto the right one, and the power of the right tower drops. High points of the landscape drop shadows on towers as well.

Choose the points to mount the towers so that the total illuminated length of the tower surfaces is as large as possible.

The first line contains three integers $n$, $m$ and $\alpha$ ($1 \le n \le 10^4$, $2 \le m \le 10^4$, $1 \le \alpha < 90$). The second line contains $n$ heights $h_i$ of the towers ($1 \le h_i \le 10^3$). Each of the next $m$ lines contains the coordinates $x_i$, $y_i$ of one landscape vertex ($|x_i| \le 10^5$, $x_i < x_{i+1}$, $|y_i| \le 10^3$).

Print on one line the maximum total illuminated length of the tower surfaces, rounded to six digits after the decimal point, with all six digits written out. No input gives an answer close enough to a rounding boundary for the sixth digit to depend on the implementation.

Several towers may be mounted at the same point. In that case only the longest one among the towers mounted at that point counts as illuminated by the sun.