#P3480. [Usaco2014 Mar]Mooo
[Usaco2014 Mar]Mooo
Mooo Moo
题目描述
农夫约翰忘了自己有多少头奶牛,决定在各块田里放置麦克风,利用听到的叫声大小计算奶牛数量。
块田从左到右排成一列。约翰的奶牛来自 个品种,品种 的一头奶牛发出的叫声音量为 。每块田可以有多头、多个品种的奶牛,也可以没有奶牛。
风把叫声从左向右传递。如果一块田记录到的总音量为 ,它会为右边紧邻的田贡献 的音量。每块田记录到的音量等于本田所有奶牛的叫声音量之和,加上左边紧邻田传来的音量。最左边的田没有来自其他田的音量。
根据各块田的记录,求与记录相符的最少奶牛数。
输入格式
第一行包含两个整数 。
接下来 行,第 行包含品种 的叫声音量 。
再接下来 行,从左到右给出各块田记录的总音量。
输出格式
输出一个整数,表示约翰可能拥有的最少奶牛数。如果无法得到给定的记录,输出 。
样例 #1
5 2
5
7
0
17
16
20
19
4
第 块田有两头品种 的奶牛和一头品种 的奶牛,第 块田有一头品种 的奶牛。
数据范围
,,。各块田记录的总音量为 到 之间的整数。