Hiking#5277
Nastya and Sasha, two hiking enthusiasts, are planning a trip to a popular mountain range this summer. They have a map of the range, depicted as a continuous broken line, where no two points share the same vertical alignment. Each vertex of this line has a known elevation above sea level, measured in meters.
However, Nastya and Sasha have different tastes when it comes to scenic beauty. Nastya is drawn to the majestic views from snowy peaks, while Sasha prefers the serene landscapes of valleys and green hills. To decide on their final destination without conflict, they have devised a game.
The game begins with a chosen "starting" point x_0 and a value . Nastya makes the first move, shifting the point x_0 to either x_0 - 2^d or x_0 + 2^d. After her move, the value decreases by one, and it becomes Sasha's turn. The game continues with decreasing by one after each move, alternating turns between Nastya and Sasha.
The game concludes when a move is made with equal to zero. The location of x_0 at this point is declared the final destination, and the decision is final.
Nastya aims to maximize the elevation of the destination, while Sasha seeks to minimize it. Your task is to determine the height of the final destination, assuming both girls play optimally.
The first line of input contains the integer (2 \leq n \leq 10000). The next lines each contain two integers x_i and y_i (-10^9 \leq x_i \leq 10^9, x_i < x_{i+1}, 0 \leq y_i \leq 10000), representing the coordinates of the -th vertex of the broken line, listed from left to right. The subsequent line contains two integers, x_0 and (x_1 \leq x_0 \leq x_n, 0 \leq d \leq 30). It is guaranteed that any point reached during the game will remain within the marked section of the range on the map.
Output a single real number with at least six decimal places, representing the result of the game.
Example 1