Farmer Bob is trying to move
Farmer Bob has
Farmer Bob's farm is
Farmer Bob has a map of the tree line. The map is a string of 1
if there are trees in that meter, or a 0
or X
if there are no trees in that meter.
For example, the string 101X01
means that there are trees on the first, third and sixth meters of the tree line, but no trees on the second, fourth or fifth meter.
Farmer Bob's tractors can squeeze through a gap of
Please determine the least number of trips that Farmer Bob must make to deliver all the
Input Specification
The input contains exactly 5 lines.
The first line consists of one integer,
The second line consists of one integer,
The third line consists of
The fourth line consists of the integer
The fifth line consists of a string, representing the map of the tree line cutting across the farm as described in the problem statement.
Output Specification
Please output the minimum number of trips Farmer Bob must make to deliver all the hay bales, assuming he always uses the widest tractor he has that can pass through the line of trees.
Sample Input
15
3
1 2 4
10
1X1101XX01
Sample Output
8
Explanation
The fifth line tells us that the largest gap between trees is 3 meters wide (from meter 7 to meter 9). Out of Farmer Bob's three tractors, the largest one that fits through a 3-meter gap is 2 meters wide (which can carry 2 hay bales each trip). As there are 15 hay bales, Farmer Bob must make 8 trips (carrying 2 hay bales for 7 trips and 1 hay bale for 1 trip).
Comments