Small Ping Pong Tournament

Time limit2sMemory limit512 MB

Summary

Given the total points each of 2^N players scored, decide whether Dudu (first score) can be the champion.

Level: Medium6 of 10
Topics: Brute force, Recursion, Divide and conquer, Implementation
Solved: No attempts yet

Problem

"Don't underestimate my strength." Dudu, 2015

This is the same problem as Large Ping Pong Tournament, with smaller bounds.

Dudu is spending time in Thailand and has decided to compete in a local ping pong tournament.

A ping pong game in this tournament is played by two players. It lasts for a fixed amount of time, and when the time is up, the player with more points wins. If both players have the same number of points, an arm wrestling match decides the winner.

The tournament has $2^N$ players including Dudu, and it runs in rounds. In each round, the $K$ remaining players are formed into pairs to play games of ping pong. The loser of each game is eliminated, and the $K/2$ winners move on to the next round. The last player remaining is the champion.

After the tournament, the organizers realized that the only thing they recorded is the total number of points each player scored. They did not write down who played whom, or who won each game. They did not write down who the champion was either.

You are given the total number of points each player scored across all of the games that player played. In a single game, each of the two players scores a non-negative integer number of points. Dudu is very strong and never loses at arm wrestling. Determine whether it is possible that Dudu was the champion.

Input

The first line contains an integer $N$ . Each of the next $2^N$ lines contains the total number of points scored by one player. Dudu's score is given first.

$0 \le N \le 3$ , and every score is an integer between 0 and $10^9$ .

Output

Print YES if it is possible that Dudu won the tournament, and NO otherwise.

Note

In the first example Dudu is player 1, and the four scores are 5, 6, 3, 5 in that order. One way for Dudu to win is the following.

First round

Player 1 beats player 3, 4:3.
Player 2 ties player 4, 5:5, and wins the arm wrestling match.

Players 1 and 2 move on to the next round.

Second round

Player 1 ties player 2, 1:1, and wins the arm wrestling match.

The total number of points each player scored matches the input. Dudu has other ways to win, but only the question of whether it is possible needs an answer.

Examples2

Example 1
Input
```
2
5
6
3
5
```
Expected output
```
YES
```
Example 2
Input
```
1
5
6
```
Expected output
```
NO
```