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
#include<bits/stdc++.h>

#define st first
#define nd second
#define pb(x) push_back(x)
#define pp(x) pop_back(x)
#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;

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); 
const int MN = 30, INF = (int)1e9 + (int)2345; 
int n, k; 
int tab[30]; 
stack <int> S; 
vi good[MN];  
string napis; 
void read(){ 
	cin >> n >> k;  
	cin >> napis ;
	for(int i =1; i <= n; i++){ 
		if(napis[i-1] == '(') 
			tab[i] = 1; 
		else 
			tab[i] = -1; 
	}
} 

void check(int pocz){  
	
	for(int i = pocz; i<=n; i++){ 
		if(S.empty() && tab[i] == -1) 
			return; 
		if(S.empty()){
			S.push(tab[i]); 
			continue; 
		} 
		if(S.top() == 1 && tab[i] == -1){ 
			S.pop();  
			if(S.empty()) 
				good[pocz].pb(i); 
			continue; 
		} 
		S.push(tab[i]); 
	} 
	while(!S.empty()) 
		S.pop(); 
} 

void prepare(){ 
	for(int i = 1; i <=n; i++) 
		check(i); 
	/*for(int i = 1; i <=n; i++){ 
		cout << i << ": "; 
		for(auto x: good[i]) 
			cout << x << ' '; 
		cout << "\n"; 
	}*/ 
} 
int ogr[30]; 
void run(){ 
	int lim = (1 << n);  
	int wynik = INF; int aktu; 
	int ind, ogrid; 
	for(int mask  =0; mask < lim; mask++){ 
		if(__builtin_popcount(mask) != k-1) 
			continue; 
		ind = 0; 
		for(int i = 0; i < n; i++){ 
			if(mask & (1 <<i)) 
				ogr[ind++] = i+1; 
		}  
		ogr[ind] = n + 3; 
		aktu = 0; ogrid = 0; 
		for(int i =1; i <= n; i++){ 
			for(auto x: good[i]){ 
				if(x <= ogr[ogrid]) 
					aktu++;  
				else 
					break; 
			} 
			if(i == ogr[ogrid]) 
				ogrid++; 
		} 
		wynik = min(wynik, aktu); 
	}		 
	cout << wynik ; 
}
int main(){  
	BOOST
	read(); 
	prepare();  
	run(); 
}