Zombies Arrive Before My Discharge

Time limit2sMemory limit1024 MB

Summary

Given zombies on a road with health values and three limited firearms, decide whether Kilo can kill or stop every zombie before the one 1 m from the post reaches it.

Level: Medium5 of 10
Topics: Brute force, Simulation
Solved: No attempts yet

Problem

Sergeant Kilo and Private Hecto are on guard duty at the ammunition depot post. While keeping watch, Kilo spots a horde of zombies approaching and hurriedly calls the command center, but no one answers.

The road from the depot post is $L$ m long. A zombie $i$ m from the post has health $Z_i$ . A zombie whose health drops to 0 or below dies permanently.

Kilo will hold off the zombies with personal firearms. He orders Hecto to carry ammunition.

Kilo's aimed shot always hits the front-most zombie on the road, no matter how far away it is.

Kilo cannot aim past the front-most zombie to hit one behind it. The aimed shot above is not possible.

While a zombie moves 1 m, Kilo can fire only one type of personal firearm, once.

Hecto is busy carrying ammunition and cannot fire.

The available firearms are as follows.

Assault rifle (B1)

Reduces the health of the front-most zombie by $B1_{power}$ . Remaining lethality does not carry over to the zombie behind. For example, a round that hits at 3 m with 6 lethality left does not carry over to a zombie at 4 m. Rifle rounds are unlimited.

Shotgun (B2)

Reduces the health of the front-most zombie by $B2_{power}$ . Remaining lethality does not carry over to the zombie behind. For example, a pellet that hits at 3 m with 6 lethality left does not carry over to a zombie at 4 m. There are $B2_{ammo}$ shotgun shells.

Sniper rifle (B3)

Reduces the health of zombies gathered within $B3_{length}$ m of the first point of impact by $B3_{power}$ for each 1 m. The lethality of a large-caliber round is effective only within $B3_{length}$ m of the first point of impact. Remaining lethality and remaining penetration distance do not carry over to zombies behind. For example, if there is no zombie at 6 m, 1 m of penetration distance remains, but it does not carry over to a zombie at 8 m. There are $B3_{ammo}$ large-caliber rounds.

Kilo and Hecto die if the zombie 1 m from the depot post is not suppressed after the shots are fired.

Can Kilo and Hecto survive?

Input

The first line contains the length of the road $L$ ( $1 \le L \le 18$ ).

The second line contains the lethality of a rifle round $B1_{power}$ ( $1 \le B1_{power} \le 100$ ).

The third line contains the lethality of a shotgun pellet $B2_{power}$ ( $B1_{power} < B2_{power} \le 500$ ) and the number of shotgun shells $B2_{ammo}$ ( $0 \le B2_{ammo} \le 9$ ), separated by a space.

The fourth line contains the lethality of a large-caliber round $B3_{power}$ ( $1 \le B3_{power} \le 500$ ), its effective penetration distance $B3_{length}$ ( $2 \le B3_{length} \le 18$ ), and the number of large-caliber rounds $B3_{ammo}$ ( $0 \le B3_{ammo} \le 9$ ), separated by spaces.

Each of the next $L$ lines contains one integer. The integer on line $i$ ( $1 \le i \le L$ ) is the health $Z_i$ of the zombie $i$ m from the depot post ( $0 \le Z_i \le 500$ ). $Z_i = 0$ means there is no zombie $i$ m from the post.

Output

Print YES if Kilo and Hecto can survive, and NO otherwise.

Examples5

Example 1
Input
```
1
10
100 0
100 2 0
5
```
Expected output
```
YES
```
Example 2
Input
```
1
10
100 0
100 2 0
15
```
Expected output
```
NO
```
Example 3
Input
```
1
10
100 1
100 2 0
15
```
Expected output
```
YES
```
Example 4
Input
```
3
10
100 1
100 3 1
30
110
200
```
Expected output
```
YES
```
Example 5
Input
```
4
10
100 0
100 10 0
0
0
0
40
```
Expected output
```
YES
```