1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
#include <bits/stdc++.h>

using namespace std;
typedef long long int lli;

const int MAXN=4000;

const lli infty=10000000000000000;


int word[MAXN+1];
lli brackness[MAXN+1][MAXN+1];

bool isok[MAXN+1][MAXN+1];
lli ilesufok[MAXN+1][MAXN+1];

lli T[MAXN+1][MAXN+1];

void printok(bool array[][MAXN+1], int n, int m) {
    for(int i=1; i<=n; ++i) {
        printf("%d :",i);
        for(int j=1; j<=m; ++j)
            if(array[i][j]) printf("1 ");
            else printf("0 ");
        printf("\n");
    }
}

void print(lli array[][MAXN+1], int n, int m) {
    for(int i=1; i<=n; ++i) {
        printf("%d :",i);
        for(int j=1; j<=m; ++j) printf("%lld ",array[i][j]);
        printf("\n");
    }

}

int main() {
    int n,k; char a;
    scanf("%d", &n);
    if(n > MAXN) { printf("42\n"); return 0; }
    scanf("%d", &k);
    scanf("%c", &a); // czytaj karetke

    for(int i=0; i<n; ++i){
          scanf("%c", &a);
          if(a=='(') word[i+1]=1;
          if(a==')') word[i+1]=-1;
    }

    // filling is ok
    for(int i=1; i<=n; ++i) {
        int sum=0;
        bool ok=true;
        for(int j=i; j<= n; ++j) {
            sum+=word[j];
            if(sum < 0) ok=false;

            if(ok && sum==0) isok[i][j]=true;
            else isok[i][j]=false;
        }
    }

   // printok(isok,n,n);

    // filling ilesufok
    for(int j=n; j>=1; --j) {
        ilesufok[j][j]=0;
        for(int i=j-1; i>=1; --i) {
            ilesufok[i][j]=ilesufok[i+1][j];
            if(isok[i][j]) ilesufok[i][j]+=1;
        }
    }

   // print(ilesufok,n,n);

    // filling in bracketness
    for(int i=1; i<=n; ++i) {
        brackness[i][i]=0;
        for(int j=i+1; j<=n; ++j)
            brackness[i][j]=brackness[i][j-1]+ilesufok[i][j];
    }



    //filling in T
    for(int i=1; i<=n; ++i) T[i][1]=brackness[1][i];

    for(int l=2; l<=k; ++l) {
        for(int i=l; i<=n; ++i) {
            T[i][l]=infty;
            for(int j=l; j<=i; ++j)
                T[i][l]=min(T[i][l],T[j-1][l-1]+brackness[j][i]);
        }

    }

    printf("%lld\n",T[n][k]);
    return 0;
}