Connecting Rods in 3D

Interview

Time limit1sMemory limit512 MB

Summary

Given a start and end point in 3D and a multiset of rod lengths, decide whether every rod can be chained from start to end, allowing overlap and at most one rod end at each of the two points.

Level: Medium5 of 10
Topics: Greedy, Math, Geometry, Sorting
Solved: No attempts yet

Problem

In a three-dimensional coordinate system, we want to connect a start point and an end point with rods of various lengths.

The rods may overlap each other. Starting from the start point, we connect the rods one by one until we reach the end point.

Determine whether all the given rods, with none left unused, can be joined to form an exact connection from the start point to the end point.

Both ends of every rod must be connected to the start point, the end point, or the end of another rod. No more than one rod end may be connected to the start point or to the end point.

The thickness of the rods is small enough to ignore, so they may overlap each other.

Input

The first line gives the start point (X1, Y1, Z1) and the end point (X2, Y2, Z2) of the coordinate system.

The second line gives the number of rods N.

Starting from the third line, N lines each give an integer K, the length of one rod.

Output

Print "YES" if the rods can be used to connect the start point to the end point, and "NO" otherwise.

Constraints

-1,000 ≤ X1, Y1, Z1, X2, Y2, Z2 ≤ 1,000
X1, Y1, Z1, X2, Y2, Z2 are all integers
1 ≤ N ≤ 100
1 ≤ K ≤ 100

Examples4

Example 1
Input
```
0 0 0 5 4 7
6
1 1 1 1 1 1
```
Expected output
```
NO
```

Example 2

Input

0 0 0 1 2 3
10
25 22 10 5 3 4 7 8 10 40

Expected output

YES

Example 3
Input
```
0 0 0 0 0 1
2
1 2
```
Expected output
```
YES
```
Example 4
Input
```
0 0 0 0 0 2
3
1 1 100
```
Expected output
```
NO
```