1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
#include <bits/stdc++.h>
#ifdef LOC
#include "debuglib.h"
#else
#define deb(...)
#define DBP(...)
#endif
using namespace std;
using   ll         = long long;
using   vi         = vector<int>;
using   pii        = pair<int, int>;
#define pb           push_back
#define mp           make_pair
#define x            first
#define y            second
#define rep(i, b, e) for (int i = (b); i < (e); i++)
#define each(a, x)   for (auto& a : (x))
#define all(x)       (x).begin(), (x).end()
#define sz(x)        int((x).size())

constexpr ll INF = 1e18;

struct Hull {
	using T = ll;

	struct Line {
		T a, b, end;
		T intersect(const Line& r) const {
			if (a == r.a) return b > r.b ? INF : -INF;
			ll u = b-r.b, d = r.a-a;
			return u/d + ((u^d) >= 0 || !(u%d));
		}
	};

	vector<Line> S;
	Hull() { S.pb({ 0, -INF, INF }); }

	void push(T a, T b) {
		Line l{-a, -b, INF};
		while (true) {
			T e = S.back().end = S.back().intersect(l);
			if (sz(S) < 2 || S[sz(S)-2].end < e) break;
			S.pop_back();
		}
		S.pb(l);
	}

	T query(T x) {
		auto t = *upper_bound(all(S), x, [](int l, const Line& r) { return l < r.end; });
		return -t.a*x - t.b;
	}
};

int n, k;
string s;

struct Frame {
	Hull hull;
	ll total = 0, blocks = 0, before = 0;
	ll query(bool outside) {
		ll p = hull.query(blocks);
		if (outside) p = min(p, before);
		return p+total;
	}
};

ll solve(ll lambda) {
	vector<Frame> stk(1);
	stk[0].before = lambda;
	stk[0].hull.push(0, lambda);

	each(chr, s) {
		if (chr == '(') {
			stk.emplace_back();
			auto &cur = stk.back(), &prv = stk[sz(stk)-2];
			cur.before = prv.query(1);
			cur.hull.push(0, cur.before+lambda);
		} else if (sz(stk) > 1) {
			auto &cur = stk.back(), &prv = stk[sz(stk)-2];
			ll q = cur.query(0);
			prv.blocks++;
			prv.total += prv.blocks + cur.total;
			prv.hull.push(-prv.blocks, q - prv.total + prv.blocks*prv.blocks);
			stk.pop_back();
		} else {
			ll q = stk[0].query(1);
			stk[0] = {};
			stk[0].before = q;
			stk[0].hull.push(0, q);
		}
	}

	return stk.back().query(1) - lambda*k;
}

void run() {
	cin >> n >> k >> s;
	ll b = 0, e = 1e11;
	while (b+1 < e) {
		ll m = (b+e) / 2;
		(solve(m-1) <= solve(m) ? b : e) = m;
	}
	cout << solve(b) << '\n';
}

int main() {
	cin.sync_with_stdio(0); cin.tie(0);
	cout << fixed << setprecision(10);
	run();
	cout << flush; _Exit(0);
}