#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>
#include <set>
#include <map>
#include <array>
#include <random>
#include <cmath>
#include <chrono>
#include <list>
#include <ctime>
#include <sstream>
#include <queue>
#include <climits>
#include <stack>
#include <valarray>
#include <random>
#include <bitset>
#include <numeric>
#include <iomanip>
#include <cassert>
using namespace std;
typedef vector<int> vi;
typedef pair<int,int> pii;
typedef long long ll;
#define rep(x, b, e) for(int x=(b); x<(e); ++x)
#define trav(a, x) for(auto& a : x)
#define ford(x, b, e) for(int x=((int)(b))-1; x>=(e); --x)
#define all(c) c.begin(),c.end()
#define sz(x) ((int)((x).size()))
#define pb push_back
#define eb emplace_back
#define st first
#define nd second
#define mp(x,y) make_pair(x,y)
typedef short int sint;
template<typename T> bool ckmin(T& a, const T& b){return b<a?a=b,1:0;}
template<typename T> bool ckmax(T& a, const T& b){return b>a?a=b,1:0;}


template <typename A, typename B>
string to_string(pair<A, B> p);

template <typename A, typename B, typename C>
string to_string(tuple<A, B, C> p);

template <typename A, typename B, typename C, typename D>
string to_string(tuple<A, B, C, D> p);

string to_string(const string& s) {
  return '"' + s + '"';
}

string to_string(char c) {
  return string(1, c);
}

string to_string(const char* s) {
  return to_string((string) s);
}

string to_string(bool b) {
  return (b ? "true" : "false");
}

string to_string(vector<bool> v) {
  bool first = true;
  string res = "{";
  for (int i = 0; i < static_cast<int>(v.size()); i++) {
    if (!first) {
      res += ", ";
    }
    first = false;
    res += to_string(v[i]);
  }
  res += "}";
  return res;
}

template <size_t N>
string to_string(bitset<N> v) {
  string res = "";
  for (size_t i = 0; i < N; i++) {
    res += static_cast<char>('0' + v[i]);
  }
  return res;
}

template <typename A>
string to_string(A v) {
  bool first = true;
  string res = "{";
  for (const auto &x : v) {
    if (!first) {
      res += ", ";
    }
    first = false;
    res += to_string(x);
  }
  res += "}";
  return res;
}

template <typename A, typename B>
string to_string(pair<A, B> p) {
  return "(" + to_string(p.first) + ", " + to_string(p.second) + ")";
}

template <typename A, typename B, typename C>
string to_string(tuple<A, B, C> p) {
  return "(" + to_string(get<0>(p)) + ", " + to_string(get<1>(p)) + ", " + to_string(get<2>(p)) + ")";
}

template <typename A, typename B, typename C, typename D>
string to_string(tuple<A, B, C, D> p) {
  return "(" + to_string(get<0>(p)) + ", " + to_string(get<1>(p)) + ", " + to_string(get<2>(p)) + ", " + to_string(get<3>(p)) + ")";
}

void debug_out() { cerr << endl; }

template <typename Head, typename... Tail>
void debug_out(Head H, Tail... T) {
  cerr << " " << to_string(H);
  debug_out(T...);
}

#ifdef LOCAL
#define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
#else
#define debug(...) 42
#endif


// #include <atcoder/modint>
// using namespace atcoder;
// using mint = modint998244353; // modint1000000007;
// typedef vector<mint> vmi;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); // use rng() to get unsigned int
// mt19937_64 for random long longs

const ll inf = 1e18;

vector<ll> dp, ndp;
vector<vector<ll>> C;

void compute(int l, int r, int optl, int optr) {
  if (l > r) return;

  int mid = (l + r) / 2;
  pair<ll, int> best = {inf, -1};

  for (int k = optl; k <= min(mid, optr); ++k) {
    ckmin(best, { (k ? dp[k-1] : 0) + C[k][mid], k });
  }

  ndp[mid] = best.first;
  int opt = best.second;
  compute(l, mid - 1, optl, opt);
  compute(mid + 1, r, opt, optr);
}


void solve2(int n, int k, string x) {
  if (n <= 3 || k >= (n + 1)/2) {
    cout << 0 << endl;
    return;
  }
  x = '#' + x;
  map<int, int> wys; // kiedy ostatnio dana suma wystepowala
  vi a(n + 1, -1); // pointer to previous
  vi c(n + 1, -1);
  vi kt(n + 1);
  int nr = 0;
  int s = 0;
  wys[s] = 0;
  rep(i, 1, n + 1) {
    if (x[i] == '(') {
      ++s; 
    } else {
      --s;
      if (wys.count(s)) {
        // we can put a pointer
        int pop = wys[s];
        a[i] = pop;
        if (c[pop] != -1) {
          c[i] = c[pop];
          kt[i] = kt[pop] + 1;
        } else {
          c[i] = nr++;
          kt[i] = 1;
        }
        a[pop + 1] = pop + 1;
        c[pop + 1] = c[i];
      }
    }
    wys[s] = i;
  }
  debug(a);
  debug(c);
  debug(kt);
  
  --k;
  vector<map<int, int>> opens;
  vector<map<int, int>> closed;
  map<int, int> copen, cclosed;
  int lastClose = 0;
  vi blocks;
  rep(i, 1, n + 1) {
    if (c[i] == -1) {
      continue;
    }
    if (x[i] == '(') {
      ++copen[c[i]];
    } else {
      if (copen[c[i]] == 0) {
        ++cclosed[c[i]];
      } else {
        // need to make a closing before i
        opens.pb(copen);
        closed.pb(cclosed);
        copen.clear();
        cclosed.clear();
        lastClose = i - 1;
        blocks.pb(lastClose);

        ++cclosed[c[i]];
      }
    }
  }
  opens.pb(copen);
  closed.pb(cclosed);

  debug(blocks);
  debug(sz(opens));
  debug(opens);
  debug(closed);

  if (sz(blocks) <= k) {
    cout << 0 << endl;
    return;
  }
  vector<pii> lr(sz(blocks), {-1, -1});
  rep(i, 0, sz(blocks)) {
    lr[i].st = i;
    lr[i].nd = i + 1;
  }
  vector<ll> cost(sz(blocks) + 1, 0); // cost within a block
  vector<ll> potencjal(sz(blocks)); // for each cutting, how much would it add
  debug(lr);

  auto costFunc = [&](int lset, int rset) {
    // [] // []
    ll wouldAdd = 0;
    if (sz(opens[lset]) < sz(closed[rset])) {
      for (auto [opek, cnt] : opens[lset]) {
        wouldAdd += (ll)cnt * closed[rset][opek];
      }
    } else {
      for (auto [opek, cnt] : closed[rset]) {
        wouldAdd += (ll)cnt * opens[lset][opek];
      }
    }
    debug("compute cost: ", opens[lset], closed[rset], wouldAdd);
    return wouldAdd;
  };

  set<int> active;
  set<pair<ll, int>> pq;
  rep(i, 0, sz(blocks)) {
    potencjal[i] = costFunc(lr[i].st, lr[i].nd);
    active.insert(i);
    pq.insert({potencjal[i], i});
  }

  auto lacz = [&](int lset, int rset) {
    // do lewego bede laczyl
    if (sz(opens[lset]) < sz(opens[rset])) {
      swap(opens[lset], opens[rset]);
    }
    if (sz(closed[lset]) < sz(closed[rset])) {
      swap(closed[lset], closed[rset]);
    }
    // always add to lset
    debug("lacz:");
    debug("opens", opens[lset], opens[rset]);
    debug("closed", closed[lset], closed[rset]);
    for (auto [repr, fr] : opens[rset]) {
      opens[lset][repr] += fr;
    }
    for (auto [repr, fr] : closed[rset]) {
      closed[lset][repr] += fr;
    }
  };

  ll res = 0;
  while (sz(pq) > k) {
    auto [potek, repr] = *pq.begin();
    debug("usuwam podzial w: ", blocks[repr], potek);
    pq.erase(pq.begin());
    res += potek;
    int lewy = lr[repr].st;
    int prawy = lr[repr].nd;
    lacz(lewy, prawy);
    // lewy je posiada
    auto it = active.find(repr);
    int przed = -1, po = -1;
    if (it != active.begin()) {
      przed = *prev(it);
      pq.erase({potencjal[przed], przed});
      lr[przed].nd = lewy;
      potencjal[przed] = costFunc(lr[przed].st, lr[przed].nd);
      pq.insert({potencjal[przed], przed});
    }
    if (next(it) != active.end()) {
      po = *next(it);
      pq.erase({potencjal[po], po});
      lr[po].st = lewy;
      potencjal[po] = costFunc(lr[po].st, lr[po].nd);
      pq.insert({potencjal[po], po});
    }
    active.erase(it);
  }
  cout << res << endl;
}


void solve() {
	int n, k;
  cin >> n >> k;
  string x;
  cin >> x;
  if ((ll) n * n >= 1e7 ) {
    solve2(n,k,x);
    return;
  }
  x = '#' + x;
  map<int, int> wys; // kiedy ostatnio dana suma wystepowala
  vi a(n + 1, -1); // pointer to previous
  vi c(n + 1, -1);
  vi kt(n + 1);
  int nr = 0;
  int s = 0;
  wys[s] = 0;
  rep(i, 1, n + 1) {
    if (x[i] == '(') {
      ++s; 
    } else {
      --s;
      if (wys.count(s)) {
        // we can put a pointer
        int pop = wys[s];
        a[i] = pop;
        if (c[pop] != -1) {
          c[i] = c[pop];
          kt[i] = kt[pop] + 1;
        } else {
          c[i] = nr++;
          kt[i] = 1;
        }
        a[pop + 1] = pop + 1;
        c[pop + 1] = c[i];
      }
    }
    wys[s] = i;
  }
  debug(a);
  debug(c);
  debug(kt);
  C.resize(n, vector<ll>(n));;
  rep(i, 1, n + 1) {

    vi howManyOpen(n, 0); // how many items from this specific component are currently open
    vi howManyClosed(n, 0);

    int currentlyInside = 0;
    ford(j, i + 1, 1) {
      // j - I need to add it to my current
      if (c[j] != -1) {
        if (x[j] == '(') {
          currentlyInside += howManyClosed[c[j]];
          ++howManyOpen[c[j]];
        } else {
          ++howManyClosed[c[j]];
        }
      }
      C[j - 1][i - 1] = currentlyInside;
    }
  }
  debug(C);
  dp = C[0];
  ndp.resize(n);
  rep(i, 1, k) {
    compute(0, n - 1, 0, n - 1);
    dp = ndp;
  }
  cout << dp[n - 1] << endl;
}

int main() {
	ios_base::sync_with_stdio(false); cin.tie(0);
	int t;
	// cin >> t;
	t = 1;
	while (t--) {
		solve();
	}
}