#include<bits/stdc++.h>
 
//#pragma GCC optimize("Ofast")
//#pragma GCC optimize("trapv")
 
#define st first
#define nd second
#define pb push_back
#define pp pop_back
#define eb emplace_back
#define mp(a, b) make_pair(a, b)
#define all(x) (x).begin(), (x).end()
#define rev(x) reverse(all(x))
#define sor(x) sort(all(x))
#define sz(x) (int)(x).size()
#define rsz(x) resize(x)
 
using namespace std;
 
///~~~~~~~~~~~~~~~~~~~~~~~~~~
 
template <typename H, typename T> 
ostream& operator<<(ostream& os, pair<H, T> m){
	return os <<"("<< m.st<<", "<<m.nd<<")";
}
template <typename H> 
ostream& operator<<(ostream& os, vector<H> V){
	os<<"{";
	for(int i=0; i<V.size(); i++){
		if(i)os<<" ";
		os<<V[i];
	}
	os<<"}";
	return os;
}
 
void debug(){cerr<<"\n";}
template <typename H, typename... T>
void debug(H h, T... t) {cerr<<h; if (sizeof...(t)) cerr << ", "; debug(t...);}
#define deb(x...) cerr<<#x<<" = ";debug(x);
 
///~~~~~~~~~~~~~~~~~~~~~~~~~
 
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<pii > vii;
typedef vector<ll> vl;
typedef vector<pll> vll;
typedef string str;
 
#define BOOST ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
 
mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count());
 
const int N=1e5+5, INF=1e9+5, mod=1e9+7;
int K=1000, KK=200;
str s;
int n, k;
ll dp[N];
ll pref[N];
int ile[N], tab[N], pocz[N], id[N], gdzie[N];
int akt[N];
vector<int> male[N];
vector<vl> male2;
vector<vi> iter;
vi co[N];
//vector<int> S[N+N];
vi big;
vector<int> dobre;
ll cnt=0;
ll cost(int l, int r){
	//return 0;
	/*ll res2=0;
	for(int i=l; i<r; i++){
		int sum=0;
		for(int j=i; j<r; j++){
			if(s[j]=='(')sum++;
			else sum--;
			if(sum<0)break;
			if(sum==0)res2++;
		}
		//deb(res);
	}
	//return res;*/
	//cnt++;
	ll res=0;
	for(int i=0; i<big.size(); i++){
		//deb(iter[i][gdzie[l]], iter[i][gdzie[r]]);
		int j=iter[i][gdzie[r]]-iter[i][gdzie[l]];
		if(co[big[i]].size()>iter[i][gdzie[r]] && r==co[big[i]][iter[i][gdzie[r]]])j++;
		res+=j*1ll*(j-1)/2;
	}
	assert(gdzie[r]/KK<male2.size());
	assert(l<=r);
	//assert(gdzie[l]<male2[gdzie[r]/KK].size());
	if(gdzie[l]/KK!=gdzie[r]/KK)res+=male2[(gdzie[r]/KK)][gdzie[l]];
	//deb(res);
	for(int i=max((gdzie[r]/KK)*KK+1, gdzie[l]); i<=gdzie[r]; i++){
		res+=male[i].size()-(lower_bound(all(male[i]), l)-male[i].begin());
		//deb(i, res);
		cnt++;
	}
	//deb(l, r, gdzie[l], gdzie[r], res, res2);
	//assert(res2==res);
	return res;
}

int licz(int i, int j){//i<j
	/*for(int M=j; M<=n; M++)if(dp[i]+cost(i, M)>=dp[j]+cost(j, M)){
		//deb(i, j, M);
		return M;
	}
	//deb(i, j, n+1);
	return n+1;*/
	int L=gdzie[j], R=dobre.size();
	while(L<R){
		int M=(L+R)>>1;
		if(dp[i]+cost(i, dobre[M])<dp[j]+cost(j, dobre[M])){
			L=M+1;
		}
		else R=M;
	}
	//deb(i, j, L)
	return L;
}
int main(){
	//BOOST;
	cin>>n>>k>>s;
	for(int i=0; i<n; i++){
		if(s[i]=='(')tab[i+1]=tab[i]+1;
		else tab[i+1]=tab[i]-1;
	}
	dobre.pb(0);
	for(int i=1; i<=n; i++){
		if(s[i-1]=='(' && s[i]==')')dobre.pb(i);
	}
	dobre.pb(n);
	for(int i=0; i<dobre.size(); i++){
		gdzie[dobre[i]]=i;
	}
	//deb(dobre);
	if(k+1>=dobre.size()){
		cout<<0<<" ";
		return 0;
	}
	vector<int> V;
	for(int i=0; i<=n; i++){
		while(V.size() && tab[V.back()]>tab[i])V.pp();
		if(V.size() && tab[V.back()]==tab[i]){
			pocz[i]=pocz[V.back()];
			id[i]=id[pocz[V.back()]]+1;
			co[pocz[i]].pb(i);
		}
		else pocz[i]=i, co[pocz[i]].pb(i);
		V.pb(i);
	}
	KK=dobre.size()/1500+1;
	vector<int> todo;
	int wsk=0;
	for(int i=0; i<=n; i++){
		if(co[i].size()>=K){
			//deb(co[i]);
			big.pb(i);
			iter.pb(vi(dobre.size()));
			int wsk2=0;
			for(int j=0; j<dobre.size(); j++){
				while(wsk2!=co[i].size() && dobre[j]>co[i][wsk2])wsk2++;
				iter.back()[j]=wsk2;
			}
		}
		if(co[pocz[i]].size()<K){
			for(int j:co[pocz[i]]){
				if(j>=i)break;
				else{
					todo.pb(j);
					akt[j]++;
				}
			}
		}
		if(dobre[wsk]==i){
			sor(todo);
			for(int j:todo){
				male[gdzie[i]].pb(j);
			}
			//deb(gdzie[i], todo);
			todo.clear();
			if((wsk%KK)==0){
				male2.pb(vl(wsk+1));
				int wsk2=wsk;
				ll s=0;
				for(int j=i; j>=0; j--){
					s+=akt[j];
					//deb(dobre.size(), wsk2);
					if(dobre[wsk2]==j){
						male2.back()[wsk2]=s;
						//if(male2.size()>1 && male2[male2.size()-2].size()>wsk2)male2.back()[wsk2]+=male2[male2.size()-2][wsk2];
						wsk2--;
					}
				}
			}
			wsk++;
		}
	}
	//for(auto i:male2)cnt+=i.size();
	//deb(cnt)
	//deb(dobre.size())
	//deb(iter)
	//deb(male2);
	/*for(int i=1; i<N+N; i++){
		if(S[i].size())sor(S[i]);
	}*/
	//deb(big.size());
	//deb("a");
	ll l=0, r=4e10;
	//deb(cost(0, n));
	r=cost(0, n);
	if(k==1){
		cout<<r<<" ";
		return 0;
	}
	r+=2;
	int m1=0, m2=n+1;
	ll val1=cost(0, n), val2=0;
	ll prv=0;
	while(l<r){
		//ll m=(l+r)/2;
		ll m=(val1-val2)/(m2-m1);
		if(prv==m)m++;
		prv=m;
		if(m<l || m>=r)m=(l+r)>>1;
		deque<int> opt;
		deque<int> gdzie2;
		opt.pb(0);
		//deb(m);
		for(int i:dobre){
			if(i==0)continue;
			if(i%1000==0){
				//deb(i);
			}
			if(gdzie2.size() && gdzie2.back()<=gdzie[i]){
				gdzie2.pp();
				opt.pp();
			}
			//deb(i, opt.back())
			dp[i]=dp[opt.back()]+cost(opt.back(), i)+m;
			ile[i]=ile[opt.back()]+1;
			while(opt.size()){
				int ii=licz(opt.front(), i);
				if(gdzie2.size() && ii<=gdzie2.front()){
					//deb("a");
					gdzie2.pop_front();
					opt.pop_front();
				}
				else{
					//deb("b");
					gdzie2.push_front(ii);
					opt.push_front(i);
					break;
				}
			}
			/*dp[i]=1e18;
			for(int j=0; j<i; j++){
				ld a=dp[j]+cost(j, i)+m;
				if(dp[i]>a)dp[i]=a, ile[i]=ile[j]+1;
			}*/
		}
		//deb(m, ile[n]);
		//deb(m);for(int i=0; i<=n; i++){deb(dp[i], ile[i]);}
		if(ile[n]>k){
			l=m+1;
			if(ile[n]<m2){
				m2=ile[n];
				val2=ll(round(dp[n]-m*ile[n]));
			}
		}
		else{
			if(ile[n]>m1){
				m1=ile[n];
				val1=ll(round(dp[n]-m*ile[n]));
				if(m1==k)break;
			}
			r=m;
		}
		//l=min(l, (val1-val)/(m2-m1));
	}
	//deb(m1, m2, val1, val2);
	//deb(l);
	//deb(cnt/ld(n));
	cout<<((k-m1)*val2+(m2-k)*val1)/(m2-m1)<<" ";
}