Mooo Moo

Time limit1sMemory limit128 MB

Summary

Find the fewest cows whose breed volumes explain the recorded volumes when each field spills its total minus one into the next field.

Problem

Farmer John forgot how many cows he owns. He placed microphones in $N$ fields along a road to estimate cow counts from mooing volume.

Breed $i$ moos at volume $V(i)$ . Wind blows left to right: if a field's total volume is $X$ , the next field gains $max(0, X-1)$ from carryover.

Given recorded total volumes, find the minimum possible number of cows, or $-1$ if impossible.

Line 1: $N$ , $B$ .

Next $B$ lines: $V(i)$ .

Next $N$ lines: recorded volume in each field.

Minimum number of cows, or $-1$ .