B"You are walking with your dog, and now you are at the promenade. The promenade can be represented as an infinite line. Initially, you are in the point 0 with your dog. You decided to give some freedom to your dog, so you untied her and let her run for a while. Also, you watched what your dog is doing, so you have some writings about how she ran. During the i -th minute, the dog position changed from her previous position by the value a_i (it means, that the dog ran for a_i meters during the i -th minute). If a_i is positive, the dog ran a_i meters to the right, otherwise (if a_i is negative) she ran a_i meters to the left. During some minutes, you were chatting with your friend, so you don't have writings about your dog movement during these minutes. These values a_i equal zero. You want your dog to return to you after the end of the walk, so the destination point of the dog after n minutes should be 0 . Now you are wondering: what is the maximum possible number of different integer points of the line your dog could visit on her way, if you replace every 0 with some integer from -k to k (and your dog should return to 0 after the walk)? The dog visits an integer point if she runs through that point or reaches in it at the end of any minute. Point 0 is always visited by the dog, since she is initially there. If the dog cannot return to the point 0 after n minutes regardless of the integers you place, print -1. The first line of the input contains two integers n and k ( 1 <= n <= 3000; 1 <= k <= 10^9 ) -- the number of minutes and the maximum possible speed of your dog during the minutes without records. The second line of the input contains n integers a_1, a_2, ldots, a_n ( -10^9 <= a_i <= 10^9 ), where a_i is the number of meters your dog ran during the i -th minutes (to the left if a_i is n"...