Farmer John has completely forgotten how many cows he owns! He decides to count his cows secretly by planting microphones in the fields, figuring that he can determine the number of cows from the total volume of all the mooing he hears.

FJ's N fields (1 <= N <= 100) are all arranged in a line along a long straight road. FJ owns cows that come from B different breeds (1 <= B <= 20), and a cow of breed i moos at a volume of V(i) (1 <= V(i) <= 100). There is a strong wind blowing down the road, which carries the sound of mooing from left to right: if the total mooing volume in some field is X, then in the next field this contributes X-1 to the total mooing volume (and X-2 in the field after that, etc.). The mooing volume in a field is the sum of the contribution due to cows in that field, plus X-1, where X is the total mooing volume in the preceding field.

Given the volume of mooing that FJ records in each field, please compute the minimum possible number of cows FJ might own. The volume recorded in any field is at most 100,000.

Line 1: The integers N and B.

Lines 2..1+B: Line i+1 contains the integer V(i).

Lines 2+B..1+B+N: Line 1+B+i contains the total volume of all mooing in field i.

The minimum number of cows owned by FJ, or -1 if there is no configuration of cows consistent with the input.

riseoj 작성

출처 올림피아드 > USACO > 2013-2014 > March > Silver