Frog and Princes


Submit solution

Points: 1
Time limit: 2.0s
Memory limit: 1000M

Author:
Problem type
Allowed languages
Assembly, C, C++, Java, Pascal, Perl, Python, Text

In the distant land of Glimmerbrook, there once lived a noble prince, brave of heart. Alas, his fate took a cruel turn when he crossed paths with an ancient and vengeful wizard. With a flick of his staff, the wizard cast a dreadful curse - transforming the prince into a frog, slimy and green. The curse was no ordinary spell, but part of an age-old magical trial known as the Geometric Arcane Puzzle of Coordinates - a test designed by the old wizards to trap the bold and free-spirited. Now, bound by enchantment, the frog-prince must reach the princess - for only her touch can break the curse and restore his true form.

The magic has twisted his very legs: he may leap no more than \(n\) times. The length of each jump (measured in Euclidean distance) is strictly dictated by the ancient spell: on the \(i\)-th jump, the frog should jump a distance of \(a_i\), no more, no less. If he can land at the princess's side before his jumps run out, the curse will shatter instantly (even if some jumps remain) and he shall be free. But should he fall short, he will remain a frog forevermore.

Figure F.1: Some ways that the frog can jump to the princess in the first sample.

Input

The input consists of:

  • One line with an integer \(n \ (1 \le n \le 4 \cdot 10^5)\), the number of jumps that the frog can make.
  • One line with four integers \(x_f, y_f, x_p,\) and \(y_p \ (-10^9 \le x_f, y_f, x_p, y_p \le 10^9)\), the coordinates \((x_f, y_f)\) of the starting position of the frog, and the coordinates \((x_p, y_p)\) of the princess.
  • One line with \(n\) integers \(a_1, \ldots, a_n \ (1 \le a_i \le 10^9\) for each \(i\), and \(\sum_{i=1}^{n} a_i \le 2 \cdot 10^9)\), where \(a_i\) is the length of the \(i\)-th jump of the frog.

It is guaranteed that the coordinates of the frog and those of the princess are not the same.

Output

Output yes if the frog can jump to the exact position of the princess, and no otherwise.

Examples

Sample 1

input

3
0 0 2 2
1 2 3

output

yes
Sample 2

input

2
0 0 -2 -2
1 1

output

no
Sample 3

input

3
0 0 2 2
6 1 2

output

no
Sample 4

input

1
0 1 1000000000 0
1000000000

output

no

Comments

There are no comments at the moment.