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
import itertools
from functools import cache


def slice(s, cut):
    k = len(cut)
    if not k:
        return tuple([s])
    else:
        res = [s[:cut[0]]]
        res.extend(s[cut[i]:cut[i + 1]] for i in range(k - 1))
        res.append(s[cut[k - 1]:])
        return tuple(res)


def partitions(s, k):
    n = len(s)
    points = list(range(1, n))
    for cut in itertools.combinations(points, k):
        yield slice(s, cut)


@cache
def check(s):
    depth = 0
    for i in s:
        if i == '(':
            depth += 1
        else:
            if depth > 0:
                depth -= 1
            else:
                return False
    if depth == 0:
        return True
    else:
        return False


@cache
def count(part):
    res = 0
    for s in part:
        l = len(s)
        for i in range(l):
            for j in range(i + 1, l + 1):
                if check(s[i:j]):
                    res += 1
    return res


n, k = [int(x) for x in input().split()]
s = input()

res = 1e10
for part in partitions(s, k - 1):
    res = min(res, count(part))

print(res)