Trucks in a parking lot There are P parking spaces in a parking lot, though some spaces are occupied by cars represented by octothorpes # while the free spaces are dots .. Soon there arrive T trucks, each of which will take up exactly L consecutive spaces. The trucks don't have to be parked next to each other.

Your task is to create a program that will find the smallest number of cars that need to be removed in order to park all of the trucks. There will always be enough spaces to fit all of the trucks, meaning T*L&lt;P

Input

In the first row there will be three integers, P, T and L separated by spaces. In the second row there will be a string of P characters representing the parking lot in its initial state.

Output

In the first and only line your program should print out the smallest number of cars that need to be removed in order to park all of the trucks.

Test cases

Input: 
6 1 3
#.#.##

Output: 1

Input: 
9 2 3
.##..#..#

Output: 2

Input: 
15 2 5
.#.....#.#####.

Output: 3

Shortest code wins. (Note: I'm particularly interested in a pyth implementation, if one is possible)
Python 2, 154 bytes
I,R=raw_input,range
P,T,L=map(int,I().split())
S=I()
D=R(P+1)
for r in R(P):D[1:r+2]=[min([D[c],D[c-1]+(S[r]&lt;&quot;.&quot;)][c%L&gt;0:])for c in R(1,r+2)]
print D[T*L]

A straightforward DP approach. A fair chunk of the program is just reading input.
Explanation
We calculate a 2D dynamic programming table where each row corresponds to the first n parking spots, and each column corresponds to the number of trucks (or parts of a truck) placed so far. In particular, column k means that we've placed k//L full trucks so far, and we're k%L along the way for a new truck. Each cell is then the minimal number of cars to clear to reach the state (n,k), and our target state is (P, L*T).
The idea behind the DP recurrence is the following:

If we're k%L &gt; 0 spaces along for a new truck, then our only option is to have come from being k%L-1 spaces along for a new truck
Otherwise if k%L == 0 then we have either just finished a new truck, or we'd already finished the last truck and have since skipped a few parking spots. We take the minimum of the two options.

If k &gt; n, i.e. we've placed more truck squares than there are parking spots, then we put ∞ for state (n,k). But for the purposes of golfing, we put k since this is the worst case of removing every car, and also serves as an upper bound.
This was quite a mouthful, so let's have an example, say:
5 1 3
..##.

The last two rows of the table are
[0, 1, 2, 1, 2, ∞]
[0, 0, 1, 1, 1, 2]

The entry at index 2 of the second last row is 2, because to reach a state of 2//3 = 0 full trucks placed and being 2%3 = 2 spaces along for a new truck, this is the only option:
  TT
..XX

But the entry at index 3 of the second last row is 1, because to reach a state of 3//3 = 1 full trucks placed and being 3%3 = 0 spaces along for a new truck, the optimal is
TTT
..X#

The entry at index 3 of the last row looks at the above two cells as options — do we take the case where we are 2 spaces along for a new truck and finish it off, or do we take the case where we have a full truck already finished?
  TTT            TTT
..XX.     vs     ..X#.

Clearly the latter is better, so we put down a 1.
Pyth, 70 bytes
JmvdczdKw=GUhhJVhJ=HGFTUhN XHhThS&gt;,@GhT+@GTq@KN\#&gt;%hT@J2Z)=GH)@G*@J1eJ

Basically a port of the above code. Not very well golfed yet. Try it online
Expanded
Jmvdczd              J = map(eval, input().split(&quot; &quot;))
Kw                   K = input()
=GUhhJ               G = range(J[0]+1)
VhJ                  for N in range(J[0]):
=HG                    H = G[:]
FTUhN                  for T in range(N+1):
 XHhT                    H[T+1] =
hS                                sorted(                                        )[0]
&gt;                                                                 [            :]
,                                        (      ,                )
@GhT                                      G[T+1]
+@GTq@KN\#                                       G[T]+(K[N]==&quot;#&quot;)
&gt;%hT@J2Z                                                           (T+1)%J[2]&gt;0
)=GH                   G = H[:]
)@G*@J1eJ            print(G[J[1]*J[-1]])

Now, if only Pyth had multiple assignment to &gt;2 variables...