Parcel

Interview

Time limit1sMemory limit512 MB

Summary

Given n distinct integers and target w, decide whether four of them sum exactly to w.

Level: Hard8 of 10
Topics: Two pointers, Hash map, Sorting
Solved: No attempts yet

Problem

The International Collegiate Parcel Center (ICPC) is running a free shipping event for university students worldwide. The condition for free shipping is that the parcel must consist of 4 items, and the total weight of these items must be exactly a given integer weight w grams.

Chansu, at Pusan National University, has a very large number of items to send to Suhwan at the Royal University of England, and every item has a distinct weight (all integer grams). Since this event runs for a limited time, Chansu wants to find out as quickly as possible whether any 4 of the items he will send satisfy this condition. In other words, given a set A of n distinct integers (n ≥ 4), he wants to determine whether some subset B consisting of only 4 elements of A (|B| = 4) satisfies ∑b∈B b = w.

For the given w and A, write a program that outputs YES if a subset B satisfying the condition exists, and NO otherwise.

Input

The input is read from standard input. The first line gives the weight w (10 ≤ w ≤ 799,994) and the number of elements n of A (4 ≤ n ≤ 5,000), separated by a space. The next line gives the n integers a**i ∈ A (1 ≤ i ≤ n) that are the elements of A, separated by spaces. Each element a**i lies between 1 and 200,000 (1 ≤ a**i ≤ 200,000).

Output

The output is written to standard output. Depending on the condition of the problem, print YES or NO on one line.

Examples2

Example 1
Input
```
10 6
5 10 7 3 2 1
```
Expected output
```
NO
```
Example 2
Input
```
21 7
10 1 4 6 2 8 5
```
Expected output
```
YES
```