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
112
113
114
115
116
117
118
119
120
121
122
123
124
//   _|                                                _|
//   _|  _|    _|    _|    _|_|    _|_|_|      _|_|_|  _|  _|      _|_|      _|_|
//   _|_|      _|    _|  _|_|_|_|  _|    _|  _|_|      _|_|      _|_|_|_|  _|_|_|_|
//   _|  _|    _|    _|  _|        _|    _|      _|_|  _|  _|    _|        _|
//   _|    _|    _|_|_|    _|_|_|  _|_|_|    _|_|_|    _|    _|    _|_|_|    _|_|_|
//                   _|            _|
//               _|_|              _|
#include <iostream>
#include <vector>

using namespace std;

// #define DEBUG
#ifdef DEBUG
#define dassert(x) assert(x);
#define df(...) printf(__VA_ARGS__)
#else
#define dassert(x)
#define df(...)
#endif

#define x first
#define y second
#define mp make_pair
#define pb push_back
#define ir(x, a, b) ((a) <= (x) && (x) <= (b))
#define vec vector
#define sz(x) (ll)x.size()
#define foru(i, n) for (int i = 0; (i) < (n); ++(i))
#define all(x) (x).begin(), (x).end()

typedef int64_t ll;

int read() {
    int n = 0; bool b = 0; char c = getchar();
    for (; !ir(c, '0', '9'); c = getchar()) b = (c == '-');
    for (; ir(c, '0', '9'); c = getchar()) n = 10*n + (c-'0');
    if (b) return -n;
    return n;
}

int n, k;
string s;

bool verify(int i, int j) {
    vec<int> dp(j-i+1);
    if (s[i] == ')') return 0;
    dp[0] = 1;
    for (int ii = i+1; ii <= j; ++ii) {
        dp[ii-i] = dp[ii-i-1] + (s[ii] == ')' ? -1 : 1);
        if (dp[ii-i] < 0) return 0;
    }
    return dp.back() == 0;
}

vec<vec<bool>> a;
int measure(int i, int j) { // [i, j]
    int s = 0;
    // cout << i << " " << j << endl;
    for (int ii = i; ii < j; ++ii) {
        for (int jj = ii+1; jj <= j; ++jj) {
            // cout << " " << ii << " " << jj << endl;
            s += a[ii][jj];
        }
    }
    return s;
}

vec<int> blocks;
int bt(int total, int i, int leftmost, int left) {
    if (left == 0) {
        total += measure(leftmost, n-1);
        // if (total == 6) {
        //     for (auto x : blocks) {
        //         cout << x << " ";
        //     }
        //     cout << endl;
        // }
        return total;
    }
    if (i == n-1) return 1e9; // should be divided before now
    int m = 1e9;
    blocks.pb(i);
    m = min(m, bt(total + measure(leftmost, i), i+1, i+1, left-1));
    blocks.pop_back();
    m = min(m, bt(total, i+1, leftmost, left));
    return m;
}

int main() {
    df("debug mode\n");
#ifndef DEBUG
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#endif
    cin >> n >> k;
    cin >> s;
    a.resize(n, vec<bool>(n));
    foru (j, n) foru (i, j) a[i][j] = verify(i, j);
    vec<vec<int>> t(n, vec<int>(n));
    foru (j, n) foru (i, j) t[i][j] = measure(i, j);
    // foru (i, n) {
    //     foru (j, n) cout << t[i][j] << " ";
    //     cout << endl;
    // }
    int mn = 1e9;
    foru (i, 1 << (n-1)) {
        if (__builtin_popcount(i) != k-1) continue;
        int last = 0;
        int s = 0;
        foru (j, n-1) {
            if ((1 << j) & i) {
                // cout << j << " ";
                s += t[last][j];
                last = j+1;
            }
        }
        s += t[last][n-1];
        // cout << "\n";
        // cout << s << "\n";
        mn = min(mn, s);
    }
    cout << mn << "\n";
    return 0;
}