Problem C
Lazy River Defense

While Tom was relaxing in the lazy river, his friend came up with a scheme to annoy him. They bought a bunch of water balloons and position themselves around the lazy river, waiting for Tom to come inside their throwing range to give him a water balloon to the face.

Everyone shares a stockpile of balloons, so after every throw, they take $t$ seconds to get a new balloon and be ready for the next throw.

There is no travel time for the balloons, so the time between a balloon being thrown and it hitting Tom is instant.

The lazy river has $n$ corners. The river travels in a straight line between each corner, in order. The final corner is connected to the first corner to form a loop. The travelling distance between each corner is guaranteed to always be an integer, and Tom’s distance travelled in an amount of time matches the amount of time travelled.

The prank ends the moment the stockpile of balloons runs out, putting an end to Tom’s misery. Please help Tom calculate how long the prank will last.

Input

First line of input contains an integer $n$ ($3\le n\le 100$), the number corners the river has.

For the next $n$ lines, each line contains two integers, the $x$ and $y$ coordinates of the $i^{th}$ corner of the river ($0\le x,y\le 100$).

Then, the next line contains two integers, the number of friends joining in the prank $m$ ($1\le m\le 10$), and number of water balloons $b$ ($1\le b\le 100$) in the pool of balloons.

For the last $m$ lines of input, each line contains four integers, the $x$ and $y$ coordinates of the $i^{th}$ person ($0\le x,y\le 100$), their throwing radius $r$ ($1\le r\le 100$), and throwing interval $t$ ($1\le t\le 100$).

Output

Output how long the prank last. Your answers must have an absolute error or relative error of at most ${10}^{-6}$. If no one can reach the river, output ‘safe‘ instead.

4
0 0
2 0
2 2
0 2
1 3
0 0 1 2

9

4
0 0
4 0
4 4
0 4
1 2
2 0 1 1

2

4
0 0
1 0
1 1
0 1
1 1
5 5 1 1

safe

4
0 0
2 0
2 2
0 2
2 5
0 0 1 2
2 2 1 2

9

4
0 0
2 0
2 2
0 2
1 4
1 1 2 2

6