题目描述

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.

题目背景

农夫约翰完全忘了他有多少头牛了！他不好意思到牧场里去数牛，因为他不想让牛意识到他的健忘。取而代之的是，他决定在奶牛聚集的牧场里安装麦克风，秘密计算出他能从中听到的所有牛叫声的总音量，以便以此确定奶牛的数量。

题目描述

$FJ$ 的 $N(1\le N\le 100)$ 个牧场都是沿着一条笔直的道路分布的。每一个牧场可能有许多种品种的奶牛； $FJ$ 拥有 $B(1\le B\le 20)$ 个不同品种的奶牛，而第 $i$ 种奶牛的叫声音量为 $V_i(1\le V_i \le 100)$ 。此外，有一股强风沿着道路吹来，将牛的叫声从左往右传递，如果某个牧场的总音量是 $x$ ，那么它将传递 $x-1$ 的音量到右边的下一个牧场。这就意味着，一个牧场里的总音量是处在该牧场的奶牛所发出的音量加上左边前一个牧场的总音量 $-1$ 。数据保证，每一个牧场内由该牧场所有奶牛所发出的总音量最多为$10^5$。

输入格式

第 $1$ 行：两个用空格分隔的整数 $N$ 和 $B$。
第 $2...B+1$ 行：第 $i+1$ 行包含整数 $V_i$ 。
第 $B+2...B+N+1$ 行：第 $B+i+1$ 行表示在第 $i$ 个牧场内所能监听到的总音量。

输出格式

共一行，即 $FJ$ 拥有的最小奶牛数量。

如果 FJ 不可能拥有一种牧场配置满足给出的条件，输出 -1。

说明/提示

输入说明：

$FJ$ 拥有 $5$ 个牧场，每个牧场总音量从左到右分别为为$0、17、16、20、19$。 $FJ$ 有两种不同品种的奶牛；第一种奶牛的叫声音量是 $5$，第二种奶牛的叫声音量是 $7$ 。

输出说明：

$2$ 号牧场场有 $2$ 头 $1$ 号品种的奶牛， $1$ 头 $2$ 号品种奶牛；还有一头牛在 $4$ 号牧场，共 $4$ 头奶牛。

输入格式

* 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.

输出格式

* 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.

Source: USACO 2014 March Contest, Silver