Solar Power Towers

The technological progress in Flatland has led to a new challenge. In a solar power station, n towers of pre‐determined heights \(h_1, h_2, \dots, h_n\) are to be mounted along the heights of high towers over a landscape. The landscape is described by a polyline with m vertices having coordinates \((x_i,y_i)\) with \(x_i < x_{i+1}\). The sun shines from the top–left at a fixed angle \(\alpha\) (in degrees). When a tower is mounted at a point on the landscape, its illuminated surface length is the portion of the tower that is not shadowed either by the terrain or by any tower to its left. In particular, if a tower with base at \((x,y)\) and height \(h\) is mounted at a selected vertex, its top is at \(y+h\), and its illuminated length is computed as

\(L = \max\{0, (y+h) - \max\Bigl(y, \max_{\substack{\text{towers to the left}\;j}}\{y_j+h_j - \tan(\alpha)\,(x-x_j)\}\Bigr)\}\).

Your task is to choose exactly n distinct vertices (in increasing order of \(x\)) from the given polyline and assign the n towers (in any order) to these mounting positions such that the total illuminated surface length of all towers is maximized. Output that maximal total illuminated length.

inputFormat

The first line contains three numbers: an integer n (the number of towers), an integer m (the number of vertices in the landscape polyline), and a real number \(\alpha\) (the sun angle in degrees).

The second line contains n space‐separated positive integers \(h_1, h_2, \dots, h_n\) representing the heights of the towers.

Each of the next m lines contains two space‐separated integers \(x_i\) and \(y_i\) representing the coordinates of the ith vertex of the polyline. It is guaranteed that \(x_i < x_{i+1}\) for all valid i.

outputFormat

Output a single number: the maximum total illuminated surface length that can be achieved by optimally choosing the mounting positions and assigning the towers. You may assume that the answer is an integer.

sample

2 2 45
10 20
0 0
10 0

30