/*
[templates]: 
duipai
compre
addhis
floor_sum
matrix
network_flow
polynomial
lca
bitset
valuesgt
fenwick
erbitree
segment
mcmf
primal_dual
centroid
add0cnt
euler
basis
*/
//#pragma GCC optimize("Ofast")
//#pragma GCC target("avx")
#include<bits/stdc++.h>
using namespace std;
#define int long long
//use ll instead of int.
#define f(i, a, b) for(int i = (a); i <= (b); i++)
#define cl(i, n) i.clear(),i.resize(n);
#define endl '\n'
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int inf = 1e18;
#define cerr if(false)cerr
//#define freopen if(false)freopen
mt19937 rng(std::chrono::high_resolution_clock::now().time_since_epoch().count()); 
int rnd(int l, int r) {return rng() % (r-l+1) + l; }
#define watch(x) cerr  << (#x) << ' '<<'i'<<'s'<<' ' << x << endl
void pofe(int number, int bitnum) {
    string s; f(i, 0, bitnum) {s += char(number & 1) + '0'; number >>= 1; } 
    reverse(s.begin(), s.end()); cerr << s << endl; 
    return;
}
double runtime() {return 1.0*clock()/CLOCKS_PER_SEC;}
template <typename TYP> void cmax(TYP &x, TYP y) {if(x < y) x = y;}
template <typename TYP> void cmin(TYP &x, TYP y) {if(x > y) x = y;}
//调不出来给我对拍！
//use std::array.
const int N=500000; 
char s[N+10]; int pre[N+10], suf[N+10],valpre[N+10],valsuf[N+10]; pii dp[N+10]; 
int _pos[2*N+10],*pos,_num[2*N+10],*num; int a[N+10]; int tmid=0;int n,k;int curl,curr; int cnt[N+10]; int iw=0; 
int w(int l,int r) {
    while(curl>l-1) {curl--; if(suf[curl]>curr)iw += cnt[a[curl]]; else iw += valsuf[curl]; cnt[a[curl]] ++; }
    while(curr<r)   {curr++; if(pre[curr]<curl)iw += cnt[a[curr]]; else iw += valpre[curr]; cnt[a[curr]] ++; }
    while(curl<l-1) {cnt[a[curl]] --; if(suf[curl]>curr)iw -= cnt[a[curl]]; else iw -= valsuf[curl]; curl++; }
    while(curr>r)   {cnt[a[curr]] --; if(pre[curr]<curl)iw -= cnt[a[curr]]; else iw -= valpre[curr]; curr--; }
    // cerr<<"w("<<l<<", "<<r<<") = "<<iw<<endl;
    return iw; 
}
void solve(int l,int r,int x,int y) {
    if(y<x)return; 
    int mid=(x+y)>>1; pii best={inf,0}; int argbest=0;  
    f(i,l,r) {
        int val=dp[i].first+w(i+1,mid)-tmid;
        if(val<best.first || (val==best.first && dp[i].second+1<best.second)) {
            best={val,dp[i].second+1}; argbest=i;
        }
    }
    cmin(dp[mid],best);
    solve(l,argbest,x,mid-1);solve(argbest,r,mid+1,y); 
}
void cdq(int l,int r){
    if(l==r) return; 
    int mid=(l+r)>>1; cdq(l,mid); solve(l,mid,mid+1,r);cdq(mid+1,r); 
} 
pii check(int mid) {
    tmid=mid; 
    f(i,1,n)dp[i]={inf,0};
    cdq(0,n);
    // cerr<<"check("<<mid<<"), res = ("<<dp[n].first<<", "<<dp[n].second<<")\n";
    return dp[n]; 
}
signed main() {
    ios::sync_with_stdio(0);
    cin.tie(NULL);
    cout.tie(NULL);
    //freopen("bracket.in","r",stdin);
    //freopen("bracket.out","w",stdout);
    // freopen("bracket.ear","w",stderr);
    //time_t start = clock();
    //think twice,code once.
    //think once,debug forever.
    cin>>n>>k; pos=_pos+N+5,num=_num+N+5;int tot=0; 
    f(i,1,n)cin>>s[i];
    f(i,-n-1,n+1)pos[i]=-1,num[i]=0;
    f(i,0,n) {
        if(i!=0) a[i]=a[i-1]+(s[i]=='('?1:-1);
        pre[i]=pos[a[i]-1];valpre[i]=num[a[i]];
        num[a[i]+1]=0;num[a[i]]++;pos[a[i]]=i;
        tot+=valpre[i]; 
    }
    // cerr<<"pre:";f(i,0,n) cerr<<pre[i]<<" \n"[i==n]; 
    // cerr<<"valpre:";f(i,0,n) cerr<<valpre[i]<<" \n"[i==n];
    f(i,-n-1,n+1)pos[i]=n+1,num[i]=0;
    for(int i=n;i>=0;i--) {
        suf[i]=pos[a[i]-1];valsuf[i]=num[a[i]];
        num[a[i]+1]=0;num[a[i]]++;pos[a[i]]=i;
    }
    // cerr<<"suf:";f(i,0,n) cerr<<suf[i]<<" \n"[i==n]; 
    // cerr<<"valsuf:";f(i,0,n) cerr<<valsuf[i]<<" \n"[i==n];
    curl=1,curr=0;
    int lo=-tot,hi=0; 
    while(lo<hi) {
        int mid=lo+(hi-lo+1)/2; pii res=check(mid); 
        if(res.second<k) {lo=mid;}
        else if(res.second == k) {cout<<res.first+k*mid<<endl;return 0; }
        else {hi=mid-1;}
    }
    pii res=check(lo); 
    cout << res.first+k*lo<<endl;
    //time_t finish = clock();
    //cout << "time used:" << (finish-start) * 1.0 / CLOCKS_PER_SEC <<"s"<< endl;
    return 0;
}