You've got an *n* × *m* pixel picture. Each pixel can be white or black. Your task is to change the colors of as few pixels as possible to obtain a barcode picture.

A picture is a barcode if the following conditions are fulfilled: 
 -  All pixels in each column are of the same color. -  The width of each monochrome vertical line is at least *x* and at most *y* pixels. In other words, if we group all neighbouring columns of the pixels with equal color, the size of each group can not be less than *x* or greater than *y*.
The first line contains four space-separated integers *n*, *m*, *x* and *y* (1 ≤ *n*, *m*, *x*, *y* ≤ 1000; *x* ≤ *y*).

Then follow *n* lines, describing the original image. Each of these lines contains exactly *m* characters. Character "." represents a white pixel and "#" represents a black pixel. The picture description doesn't have any other characters besides "." and "#".
#include<iostream>
#include<vector>
using namespace std;
#include<unordered_map>
#define ll long long
//0 -> .
//1 -> #
vector<vector<vector<ll>>>dp;
vector<ll>countDotes;
int n, m, x, y;


ll solve(int col,int last,int width){
    if(col == m) {
        if(width < x || width > y)
          return 100000000;
          
        return 0;
    }
    
    if(dp[col][last][width] != -1)
      return dp[col][last][width];
    
    ll dotes = 100000000,hashes = 100000000;
    //current column (.) 
    if(col == 0 || last == 0 && width < y || last == 1 && width >= x )
      dotes = n - countDotes[col] + solve(col + 1,0,(last == 0)? width + 1 : 1);
    
    //current column (#)
    if(col == 0 || last == 0 && width >= x || last == 1 && width < y)
       hashes = countDotes[col] + solve(col + 1 , 1,(last == 0)?1:width + 1);
       
    dp[col][last][width] = min(dotes,hashes);
     
    return dp[col][last][width];
}
int main(){
    
    
    cin>>n>>m>>x>>y;
    
    vector<vector<char>>matrix;
    char cur;
    
    for(int i = 0 ; i < n ; i++){
        vector<char>nums;
        
        for(int j = 0 ;j < m ; j++){
            cin>>cur;
            nums.push_back(cur);
        }
        
        matrix.push_back(nums);
    }
    
    vector<vector<ll>>d(3,vector<ll>(y,-1));
    
    dp.resize(m,d);
    
    countDotes.resize(m,0);
    
    for(int c = 0 ;c < m ; c++){
        
        unordered_map<char,int>hsh;
       
        for(int r = 0 ; r < n ; r++)
          hsh[matrix[r][c]]++;
          
        countDotes[c] = hsh['.'];
    }
    cout<<solve(0,2,0);
}