PUCMM005 - Mighty Powers
In a world dominated by evil, The One must emerge to bring joy, freedom and happiness back to the world. Franciszek Filippov, a late mathematician, proved The One emerges in a generation if and only if the sum of the chi of some of the members of the generation equals Po, the perfect balance number. Formally, the one emerges if there is some subset K, such that:
and
Given the chi’s of every member of a generation, determine whether The One can emerge from them.
Input
The first line contains two space-separated integers n and Po (2 <= n <= 20, 1 <= Po <= 20,000,000,000). The next line contains n space-separated integers Chi_i (1 <= Chi_i <= 10,000,000,000), the chi of the i-th member of the generation.
Output
Please output “YES” if The One emerges. Otherwise, print “NO”. In any case, do not include quotes in your output!
Sample Cases
Input | Output |
3 7 5 2 9 |
YES |
4 8 9 10 15 100 |
NO |
Note
In the first case, 5 + 2 = 7 thus The One emerges. In the second case, nothing sums up to 8.
Added by: | kojak_ |
Date: | 2013-03-12 |
Time limit: | 1s |
Source limit: | 50000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Languages: | All except: ASM64 |
Resource: | 2013 PUCMM Beginners (Round #1) |