#include <bits/stdc++.h>

using namespace std;

#define int long long

const int N = 1e5 + 10, inf = 1e18;
typedef unsigned long long ull;

namespace seq
{
	const ull B = 20090519, MOD = 1e9 + 7;
	vector<ull> s;
	ull hash;
	ull pw[N];

	void init(int n)
	{
		hash = 0;
		pw[0] = 1; for (int i = 1; i <= n; i++) pw[i] = pw[i - 1] * B;
	}

	void push(ull x)
	{
		hash += x * pw[s.size()];
		s.push_back(x);
	}

	void pop()
	{
		ull x = s.back(); s.pop_back();
		hash -= x * pw[s.size()];
	}

	ull get()
	{
		return hash;
	}
}

int n, k, a[N];
ull h[N];

namespace DS
{
	int l, r, ans, k, cnt[N];

	void init(int n, int p)
	{
		l = 1, r = 0, ans = 0, k = p;
		memset(cnt, 0, sizeof(int) * (n + 1));
	}

	void add(int pos)
	{
		int v = h[pos];
		ans += cnt[v], cnt[v]++;
	}

	void del(int pos)
	{
		int v = h[pos];
		cnt[v]--, ans -= cnt[v];
	}

	int get(int ll, int rr)
	{
		ll--;
		while (l > ll) l--, add(l);
		while (r < rr) r++, add(r);
		while (l < ll) del(l), l++;
		while (r > rr) del(r), r--;
		return ans - k;
	}
}

array<int, 2> dp[N];

void trans(int l, int r, int pl, int pr)
{
	if (l > r) return;
	int mid = (l + r) >> 1;
	array<int, 2> mn = dp[mid];
	int pmid = pl - 1;
	for (int i = pl; i <= pr && i < mid; i++)
	{
		array<int, 2> v = { dp[i][0] + DS::get(i + 1, mid), dp[i][1] + 1 };
		if (v < mn) mn = v, pmid = i;
	}
	dp[mid] = min(dp[mid], mn);
	trans(l, mid - 1, pl, pmid), trans(mid + 1, r, pmid, pr);
}

void cdq(int l, int r)
{
	if (l >= r) return;
	int mid = (l + r) >> 1;
	cdq(l, mid);
	trans(mid + 1, r, l, mid);
	cdq(mid + 1, r);
}

array<int, 2> getf(int p)
{
	DS::init(n, p);
	dp[0] = {0, 0};
	for (int i = 1; i <= n; i++) dp[i] = {inf, 0};
	cdq(0, n);
	return dp[n];
}

signed main()
{
	cin >> n >> k;
	seq::init(n + 1);
	set<ull> help;
	h[0] = seq::get(); help.insert(h[0]);
	for (int i = 1; i <= n; i++)
	{
		char c; cin >> c;
		if (c == '(') a[i] = 1;
		else a[i] = -1;
		if (seq::s.empty() || c == '(' || (c == ')' && a[seq::s.back()] == -1)) seq::push(i);
		else seq::pop();
		h[i] = seq::get(), help.insert(h[i]);
	}

	map<ull, int> disc;
	int idx = 0;
	for (int x : help) idx++, disc[x] = idx;
	for (int i = 0; i <= n; i++) h[i] = disc[h[i]];
	int pl = -1e10, pr = 0;
	while (pl + 1 < pr)
	{
		int mid = (pl + pr) >> 1;
		auto res = getf(mid);
		int c = res[1];
		// printf("mid = %lld, v = %lld, c = %lld\n", mid, res[0], res[1]);
		if (c < k) pl = mid;
		else pr = mid;
	}
	auto res = getf(pl);
	cout << res[0] + k * pl;
}