프로그램 명: usa_moomoo
제한시간: 1 초

//번역 중

Farmer John has completely forgotten how many cows he owns! He is too embarrassed to go to his fields to count the cows, since he doesn't want the cows to realize his mental lapse. 농부 존은 얼마나 많은 소를 가지고 있는지 기억이 나질 않는다. 그는 너무 당황해서 몇 마리인지 확인하기 위해 가지 않는다. 왜냐하면 소들의 그의 멘붕 상태를 알리지 .. Instead, he decides to count his cows secretly by planting microphones in the fields in which his cows tend to gather, 대신, 그는 결정했다. 몰래 마이크로 폰을를 설치해서 그의소들이 모이는 경향이 있는 필드에 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. 농부 존의 필드는 한 줄로 되어 있다. Each field might contain several types of cows; 각 필드는 여러타입의 소들을 포함하고 있다. 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). 존은 소들을 소유하고 있다. B 개의 다른 종 그리고 i 종의 소리는 V(i) 이다. Moreover, there is a strong wind blowing down the road, which carries the sound of mooing in one direction from left to right: 게다가 , 마을 아래로 몰아치는 강한 바람이 있다 이는 왼쪽에서 오른쪽 방향으로 음메소리를 실어 나른다. if the volume of mooing in some field is X, then in the next field this will contribute X-1 to the total mooing volume (and X-2 in the field after that, etc.). Otherwise stated, 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 FJ records in any field is at most 100,000.

Farmer John has completely forgotten how many cows he owns! He is too embarrassed to go to his fields to count the cows, since he doesn't want the cows to realize his mental lapse. Instead, he decides to count his cows secretly by planting microphones in the fields in which his cows tend to gather, 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. Each field might contain several types of cows; 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). Moreover, there is a strong wind blowing down the road, which carries the sound of mooing in one direction from left to right: if the volume of mooing in some field is X, then in the next field this will contribute X-1 to the total mooing volume (and X-2 in the field after that, etc.). Otherwise stated, 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 FJ records in any field is at most 100,000.

입력

출력

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

입출력 예

입력

5 2
5
7
0
17
16
20
19

출력

4

INPUT DETAILS:

FJ owns 5 fields, with mooing volumes 0,17,16,20,19. There are two breeds of cows; the first moos at a volume of 5, and the other at a volume of 7.

OUTPUT DETAILS:

There are 2 cows of breed #1 and 1 cow of breed #2 in field 2, and there is another cow of breed #1 in field 4. 
출처: USACO 2014 March Contest, Silver
[질/답] [제출 현황] [푼 후(0)]
[ 채 점 ] [홈으로]  [뒤 로]