#include<bits/stdc++.h>
using namespace std;
int n,m;
char c[501000];
#define ll long long
namespace Sol1{
	const ll I=1e12;
	const int N=4e3+10;
	int is[N],top,f2[N];
	ll f[N],va[N][N];
	struct qq{int l,r,z;};
	bool ck(int x,int y,int z){
		ll v1=f[x]+va[x+1][z],v2=f[y]+va[y+1][z];
		return v1<v2||v1==v2&&f2[x]>f2[y];
	}
	bool chk(ll mid){
		deque<qq>o;o.push_back((qq){1,n,0});
		f[0]=0,f2[0]=0;
		for(int i=1;i<=n;i++){
			qq op=o.front();o.pop_front();
			f[i]=f[op.z]+va[op.z+1][i]+mid,f2[i]=f2[op.z]+1;
			if(i==n)break;
			if(op.l<op.r)o.push_front((qq){op.l+1,op.r,op.z});
			int ml=n+1;
			while(!o.empty()){
				qq eg=o.back();
				if(ck(i,eg.z,eg.l))ml=eg.l,o.pop_back();
				else break;
			}
			if(!o.empty()){
				qq eg=o.back();o.pop_back();
				int l=eg.l,r=eg.r;
				while(l<=r){
					int mi=(l+r)>>1;
					if(ck(i,eg.z,mi))ml=mi,r=mi-1;
					else l=mi+1;
				}
				if(eg.l<ml)o.push_back((qq){eg.l,ml-1,eg.z});
			}
			if(ml<=n)o.push_back((qq){ml,n,i});
		}
		return f2[n]>=m;
	}
	void sol(){
		for(int i=1;i<=n;i++){
			top=0;memset(is,0,sizeof(is));
			int ee=0;
			for(int j=i;j<=n;j++){
				if(c[j]=='(')top++,is[top]=0;
				else if(top)top--,is[top]++,ee+=is[top];
				else is[0]=0;
				va[i][j]=ee;
			}
		}
		ll l=0,r=I,at=-1;
		while(l<=r){
			ll mid=(l+r)>>1;
			if(chk(mid))at=mid,l=mid+1;
			else r=mid-1;
		}
		chk(at);
		printf("%lld\n",f[n]-at*m);
	}
}
const ll I=1e12;
int rr[500100],sta[500100],top,col[501000],sc;
int ce[501000],L,R;ll qt;
ll f[500100];int f2[501000];
ll val(int l,int r){
	swap(l,L),swap(r,R);
	while(r<R){r++;if(col[r])qt+=ce[col[r]],ce[col[r]]++;}
	while(l>L){l--;if(col[l])qt+=ce[col[l]],ce[col[l]]++;}
	while(r>R){if(col[r])ce[col[r]]--,qt-=ce[col[r]];r--;}
	while(l<L){if(col[l])ce[col[l]]--,qt-=ce[col[l]];l++;}
	return qt;
}
void cdq2(int pl,int pr,int l,int r){
	if(l>r)return;
	int mid=(l+r)>>1;
	ll o1=1e18;int o2=-1,is=-1;
	for(int i=pl;i<=pr;i++){
		ll ve=f[i]+val(i,mid);
		if(o1>ve||o1==ve&&o2<f2[i])o1=ve,o2=f2[i],is=i;
	}
	if(f[mid]>o1||f[mid]==o1&&f2[mid]<o2)
	f[mid]=o1,f2[mid]=o2;
	assert(is!=-1);
	cdq2(pl,is,l,mid-1),cdq2(is,pr,mid+1,r);
}
ll FK;
void cdq(int l,int r){
	if(l==r){
		if(l)f2[l]++,f[l]+=FK;
		return;
	}
	int mid=(l+r)>>1;
	cdq(l,mid);
	for(int i=L;i<=R;i++)ce[col[i]]=0;
	L=mid+1,R=mid,qt=0;
	cdq2(l,mid,mid+1,r),cdq(mid+1,r);
}
bool chk(ll K){
	FK=K;
	for(int i=1;i<=n;i++)f[i]=I;
	cdq(0,n);
	return f2[n]>=m;
}
int main(){
	scanf("%d%d%s",&n,&m,c+1);
	//if(n<=4000){Sol1::sol();return 0;}
	for(int i=1;i<=n;i++){
		if(c[i]=='(')sta[++top]=i;
		else if(top)rr[sta[top]]=i,top--;
	}
	for(int i=0;i<n;i++)if(rr[i+1]&&!col[i]){
		int u=i;
		col[u]=++sc;
		while(rr[u+1])u=rr[u+1],col[u]=sc;
	}
	ll l=0,r=I,at=-1;
	while(l<=r){
		ll mid=(l+r)>>1;
		if(chk(mid))at=mid,l=mid+1;
		else r=mid-1;
	}
	chk(at);
	printf("%lld\n",f[n]-at*m);
	return 0;
}