Farmer Bob is trying to move hay bales (each being 1 meter wide) from one side of his farm to the other.
Farmer Bob has tractors, each with a certain integer width, in meters. Each tractor can carry as many hay bales as it is wide (i.e. a tractor that is 3 meters wide can carry 3 hay bales at a time), but does not necessarily need to carry a full load each trip.
Farmer Bob's farm is meters wide. There is a line of trees splitting the farm across the centre. To carry the hay bales across, Farmer Bob's tractor must be able to squeeze through the line of trees without hitting a tree.
Farmer Bob has a map of the tree line. The map is a string of characters. For each meter across the farm, the map shows a
1 if there are trees in that meter, or a
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 meters if the width of the tractor is less than or equal to . He will use the widest possible tractor that can pass through the line of trees to move the hay bales. In the above example, the widest tractor Farmer Bob can use is 2 meters wide (it can squeeze through the gaps between the trees in the third meter and the trees in the sixth meter).
Please determine the least number of trips that Farmer Bob must make to deliver all the hay bales (it is guaranteed that this job is possible).
The input contains exactly 5 lines.
The first line consists of one integer, , the number of hay bales Farmer Bob must move.
The second line consists of one integer, , the number of tractors Farmer Bob has.
The third line consists of integers, the widths of the tractors, in increasing order. Each tractor has a maximum width of .
The fourth line consists of the integer , the width of Farmer Bob's farm in meters.
The fifth line consists of a string, representing the map of the tree line cutting across the farm as described in the problem statement.
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.
15 3 1 2 4 10 1X1101XX01
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).