Hide

Problem C
Cutting the Necklace

A group of friends was given a necklace. The necklace is a circular nylon wire with gold beads of various weights glued on. They want to cut the wire into segments so that everybody gets one segment, every person gets the same amount of gold, no bead is cut, and no gold is left over. They wonder whether such a split is possible.

Input

The first line contains two integers $k$ and $n$ where $k$ is the number of friends and $n$ is the number of beads on the necklace. The next line contains $n$ positive integers—the weights of the beads in the order they occur on the necklace. You may assume $k\leq 1\, 000\, 000$, $n\leq 10\, 000\, 000$, and that bead weights are each $\leq 1\, 000\, 000\, 000$.

Output

The output consists of a single line consisting of the string YES if the necklace can be split into $k$ segments of equal weight, and the string NO otherwise.

Sample Input 1 Sample Output 1
3 4
1 2 2 1 
YES
Sample Input 2 Sample Output 2
3 4
2 2 4 1
NO

Please log in to submit a solution to this problem

Log in