QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#133724#5246. Nawiasowe podziały [B]Mobius_12710 ✓1971ms82284kbC++145.4kb2023-08-02 13:33:002023-08-02 13:33:11

Judging History

你现在查看的是最新测评结果

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-08-02 13:33:11]
  • 评测
  • 测评结果:10
  • 用时:1971ms
  • 内存:82284kb
  • [2023-08-02 13:33:00]
  • 提交

answer

#include <stdio.h>
#include <algorithm>
#include <string.h>
#include <cctype>
#include <vector>
#include <queue>
#include <bitset>
#include <cmath>
#define vi vector<int>
#define vl vector<long long>
#define pb push_back
#define mp make_pair
#define st first
#define nd second
using namespace std;
typedef long long ll;
typedef pair <int, int> Pii;
const int INF=0x3f3f3f3f;
const int cp=998244353;
inline int mod(int x){if(x>=cp) x-=cp;if(x<0) x+=cp;return x;}
inline void plust(int &x, int y){x=mod(x+y);return ;}
inline void minut(int &x, int y){x=mod(x-y);return ;}
inline int read(){
	char ch=getchar();int x=0, f=1;
	while(!isdigit(ch)){if(ch=='-') f=-1; ch=getchar();}
	while(isdigit(ch)){x=(x<<3)+(x<<1)+ch-'0';ch=getchar();}
	return x*f;
}
inline void write(int x){
    if(x<0) putchar('-'), x=-x;
    if(x>9) write(x/10);
    putchar(x%10+'0');
}
inline int ksm(int a, int b=cp-2){
	int ret=1;
	for(; b; b>>=1, a=1ll*a*a%cp)
		if(b&1) ret=1ll*ret*a%cp;
	return ret;
}
const int N=1e5+5;
const int M=N<<1;
int n, K, sum[N];char s[N];
namespace CarTree{//Cartesian Tree
	int cnt, pos[N], dfn[M], ST[20][N], ET[20][M], val[M];
	int fa[M][20], son[M], mxd[M], dep[M], top[M], pc[M], sc[M];
	bool tp[M];vi G[M], U[M], D[M];
	ll pre[M], suf[M], C2[N], siz[M], ep[M], es[M], S[M];
	//若 x 是圆点,则 val 表示 x 有多少个方点儿子
	//若 x 是方点,则 val 表示 x 是父亲的第几个方点儿子
	int MN(int x, int y){return sum[x]==sum[y]?(x<y?x:y):(sum[x]<sum[y]?x:y);}
	int qry(int x, int y){
		if(x>y) return -1;int k=__lg(y-x+1);
		return MN(ST[k][x], ST[k][y-(1<<k)+1]);
	}
	int MX(int x, int y){return dep[x]<dep[y]?x:y;}
	int LCA(int x, int y){
		if(x==y) return x;x=dfn[x], y=dfn[y];if(x>y) swap(x, y);
		int k=__lg(y-x);return fa[MX(ET[k][x+1], ET[k][y-(1<<k)+1])][0];
	}
	void build(int k, int l, int r){
		if(l>r) return ;
		int x=qry(l, r), v=sum[x];
		// printf("[%d %d %d]\n", l, r, x);
		for(; x>=0&&sum[x]==v; l=x+1, x=qry(x+1, r)){
			if(l<x) G[k].pb(++cnt), build(cnt, l, x-1);
			G[k].pb(++cnt), tp[cnt]=1, val[cnt]=++val[k], pos[x]=cnt;
		}
		if(l<=r) G[k].pb(++cnt), tp[cnt]=0, build(cnt, l, r);
	}
	void dfs(int x){
		mxd[x]=dep[x];ET[0][dfn[x]=++dfn[0]]=x;if(!tp[x]) siz[x]=C2[val[x]];
		for(int i=1; i<20; ++i) fa[x][i]=fa[fa[x][i-1]][i-1];
		for(auto v:G[x]){
	//int c=0;suf[v]=suf[x]+C2[val[x]-c+1];if(tp[v]) ++c;pre[v]=pre[x]+C2[c];
			dep[v]=dep[x]+1, fa[v][0]=x;dfs(v);siz[x]+=siz[v];
			mxd[x]=max(mxd[v], mxd[x]);if(mxd[v]>mxd[son[x]]) son[x]=v;
		}
	}
	void dfs(int x, int rt){
		// printf(">>>%d %d\n", x, rt);
		if(x==rt) for(int i=0, p=x; i<=mxd[x]-dep[x]; ++i, p=fa[p][0]) U[x].pb(p);
		D[top[x]=rt].pb(x);if(son[x]) dfs(son[x], rt);
		for(auto v:G[x]) if(!top[v]) dfs(v, v);
	}
	void calc(int x){
		int sz=G[x].size()-1;
		ll pres=0;for(int i=0, c=0, v; i<=sz; ++i)
			c+=tp[v=G[x][i]], pre[v]=pre[x]+C2[c]+pres, 
			pc[v]=c, ep[v]=pres, pres+=siz[v];
		ll sufs=0;for(int i=sz, c=0, v; i>=0; --i)
			c+=tp[v=G[x][i]], suf[v]=suf[x]+C2[c]+sufs,
			sc[v]=c, es[v]=sufs, sufs+=siz[v];
		ll s=0;for(auto v:G[x]) S[v]=(s+=siz[v]), calc(v);
	}
	int kLA(int x, int k){
		if(!k) return x;int hb=__lg(k);
		x=fa[x][hb];k-=(1<<hb)+dep[x]-dep[top[x]];
		// printf("ask %d to %d [%d]\n", x, top[x], k);
		return (k>=0)?U[top[x]][k]:D[top[x]][-k];
	}
	ll query(int l, int r){
		if(l+1>=r) return 0;
		// printf("ask [%d %d] ", l, r);
		l=pos[l], r=pos[r];int x=LCA(l, r);
		ll p=suf[l]-suf[x]+pre[r]-pre[x];
		int lk=kLA(l, dep[l]-dep[x]-1), rk=kLA(r, dep[r]-dep[x]-1);
		// printf("%d(%d) %d(%d) to %d %lld+%lld\n", 
		// l, lk, r, rk, x, suf[l], pre[r]);
		p+=C2[(pc[rk]-pc[lk]+tp[rk]+sc[lk]-sc[rk]+tp[lk])/2]-C2[sc[lk]]-C2[pc[rk]];
		p+=(S[rk]-S[lk]-siz[rk])-es[lk]-ep[rk];
		// printf("find %lld\n", p);
		return p;
	}
	void init(){
		for(int i=1; i<=n; ++i) 
			sum[i]=sum[i-1]+(s[i]=='('?1:-1), ST[0][i]=i, C2[i]=1ll*i*(i-1)/2;
		C2[n+1]=1ll*n*(n+1)/2, sum[0]=ST[0][0]=0;
		// for(int i=0; i<=n; ++i) printf("%d", sum[i]);puts("");
		for(int i=1; i<=__lg(n+1); ++i)
			for(int x=0; x+(1<<i)-1<=n; ++x)
				ST[i][x]=MN(ST[i-1][x], ST[i-1][x+(1<<i-1)]);
		build(cnt=1, 0, n);
		dfs(dep[1]=1);dfs(1, 1);calc(1);
		// for(int i=1; i<=cnt; ++i) printf("%lld ", suf[i]);puts("");
		for(int i=1; i<=__lg(cnt); ++i)
			for(int x=1; x+(1<<i)-1<=cnt; ++x)
				ET[i][x]=MX(ET[i-1][x], ET[i-1][x+(1<<i-1)]);
	}
}
ll f[N];
int h, t, g[N];
struct node{int l, r, pos;}q[N];
ll DP(int l, int r){return f[l]+CarTree :: query(l, r);}
bool cmp(int a, int b, int r){
	ll fa=DP(a, r), fb=DP(b, r);
	return fa>fb||(fa==fb&&g[a]>=g[b]); 
}
int find(int l, int r, int p, int q){
	int res=r;
	while(l<=r){
		int mid=(l+r)/2;
		if(cmp(p, q, mid)) r=mid-1, res=mid;
		else l=mid+1;
	}
	return res;
}
int check(ll C){
	q[h=t=1]=(node){1, n, 0};
	for(int i=1; i<=n; ++i){
		while(h<=t&&q[h].r<i) ++h;
		f[i]=DP(q[h].pos, i)-C, g[i]=g[q[h].pos]+1;
		if(cmp(q[t].pos, i, n)){
			int L=n;
			while(h<=t&&cmp(q[t].pos, i, q[t].l)) L=q[t].l, --t;
			if(h<=t&&cmp(q[t].pos, i, q[t].r)) L=find(q[t].l, q[t].r, q[t].pos, i);
			if(L<=q[t].r) q[t].r=L-1;q[++t]=(node){L, n, i};
		}
	}
	return g[n];
}
signed main(){
	n=read(), K=read();
	scanf("%s", s+1);CarTree :: init();
	ll L=-2e10, R=2e10, ans=0;//斜率单增
	while(L<=R){
		ll mid=L+R>>1;
		if(check(mid)<=K) L=mid+1, ans=f[n]+mid*K;
		else R=mid-1;
	}
	printf("%lld\n", ans);
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 1
Accepted

Test #1:

score: 1
Accepted
time: 4ms
memory: 38000kb

input:

1 1
(

output:

0

result:

ok single line: '0'

Test #2:

score: 0
Accepted
time: 1ms
memory: 39996kb

input:

1 1
)

output:

0

result:

ok single line: '0'

Test #3:

score: 0
Accepted
time: 1ms
memory: 33816kb

input:

2 1
()

output:

1

result:

ok single line: '1'

Test #4:

score: 0
Accepted
time: 1ms
memory: 38000kb

input:

2 1
)(

output:

0

result:

ok single line: '0'

Test #5:

score: 0
Accepted
time: 4ms
memory: 40056kb

input:

2 2
()

output:

0

result:

ok single line: '0'

Test #6:

score: 0
Accepted
time: 2ms
memory: 37932kb

input:

2 2
)(

output:

0

result:

ok single line: '0'

Test #7:

score: 0
Accepted
time: 0ms
memory: 33948kb

input:

10 4
()))(()(()

output:

0

result:

ok single line: '0'

Test #8:

score: 0
Accepted
time: 0ms
memory: 41980kb

input:

15 4
())))()(()()(((

output:

1

result:

ok single line: '1'

Test #9:

score: 0
Accepted
time: 8ms
memory: 36008kb

input:

18 18
(()()()))(())(((((

output:

0

result:

ok single line: '0'

Test #10:

score: 0
Accepted
time: 3ms
memory: 42080kb

input:

18 3
(())(()()()())()()

output:

7

result:

ok single line: '7'

Test #11:

score: 0
Accepted
time: 1ms
memory: 42040kb

input:

17 5
()()(())()(()()()

output:

3

result:

ok single line: '3'

Test #12:

score: 0
Accepted
time: 4ms
memory: 36020kb

input:

17 4
()(()()())(()()()

output:

4

result:

ok single line: '4'

Test #13:

score: 0
Accepted
time: 5ms
memory: 39956kb

input:

18 4
()(()())(())()()()

output:

4

result:

ok single line: '4'

Test #14:

score: 0
Accepted
time: 1ms
memory: 33920kb

input:

18 4
(())()(())()()(())

output:

4

result:

ok single line: '4'

Test #15:

score: 0
Accepted
time: 0ms
memory: 42116kb

input:

18 4
(()())(()())()(())

output:

3

result:

ok single line: '3'

Subtask #2:

score: 1
Accepted

Test #16:

score: 1
Accepted
time: 0ms
memory: 46260kb

input:

300 25
((()()()(()())(((())())()))()((()(())))((()()))((()()))()()(((())())))((((())(()()()())(((()))(()())()(())())()()()()())(()((()()()))))(())()((()))((()))(()(()())))((()(())(((()))))((()()()()()())())(((()))()()()(())())(())()(((()))()((()()())))((())())(((()())())((()))(()()()()(())(()())((()...

output:

90

result:

ok single line: '90'

Test #17:

score: 0
Accepted
time: 1ms
memory: 46268kb

input:

300 1
((((()))((((())))(())((()()(()())()())()()())()()())((()(()(())))((()))))()()(((())())))((((()((()))(())())))()(((())(())(())()()))((()()()())((())()())((()()(()(())))(()()))())()(((()()(()))))((()())()((()()(()()()())()(())()(()())()))((()()(())()())()()())((()((())())()))))(((())()(())(((())...

output:

332

result:

ok single line: '332'

Test #18:

score: 0
Accepted
time: 2ms
memory: 48204kb

input:

300 4
((((((()(())()())))(((()()(())())))()())((((((()()))))()((())(()((())))()()())(()(()()(()())())()))(()(()())(()())())(((())))(()())()(()((()()())(()()((())))((()((())())))(((()())()))(()))()((()))()()()()()()()(()(()(())()))(()(()()()()())()(()))))()(((()())))((()(())()))((()()(()()((()()(()))...

output:

250

result:

ok single line: '250'

Test #19:

score: 0
Accepted
time: 1ms
memory: 40076kb

input:

300 1
(((()((()(()()()())()))((()))((()()(()(())())(()())()())()(()))((()()()))()((()(()())()()(()()))(()(()()()))()())()(()(())(())(())()(())(()())((())()()(())())(()((()))(()))(()(((()())))(()))((()()))()()(((()))))(()()(((()()))))(()()))()(()((((()()))(((()))))()())()(()((()())())(())(((()())(())...

output:

400

result:

ok single line: '400'

Test #20:

score: 0
Accepted
time: 4ms
memory: 40132kb

input:

300 2
()((())()(())()()()()(()))(()(())(()))(()())(()()()()()()(()()())())(()())()(()()(()()())()((())()))(()()())(()())((()()(()))(()())()()())(()()()()())((()()))(()(())(()()))((()())(()())()(()(()()()())())()())(()())(()()()()()(())(()()))((()()()))(())(()(()())(()()))()(((()))()()()()(()())())((...

output:

453

result:

ok single line: '453'

Test #21:

score: 0
Accepted
time: 1ms
memory: 40132kb

input:

300 169
(((()))()()())(()(()(())))(()(()()())()(())()(())(()()()))(()(()))(()()(()())(()))(()()())()()(()(())(()()())(()))()((()))(())((())(())()((()))()()())(()()(()()))((()))((()()))(()()(()))(()())(())()(())(()()())()(()())(())((()())(()()))()(())(()(()))(()()(()()))()(()())(())(()(()))(((()))()(...

output:

0

result:

ok single line: '0'

Test #22:

score: 0
Accepted
time: 3ms
memory: 48204kb

input:

300 1
)((())(()()(()))(())))((()()()))))((((()))))()())()))((())))()))(())))()()))))())(())()())((((((()))(((()())())((())()(()(()()((()(())))())((()())())))()())))(((()(((()(((()))(()((()())))(((((((()(())((((()((()()())(((()))()((()()((((((()())))((()())))))))())()(())))()))()(()()()(((()(()))())(...

output:

202

result:

ok single line: '202'

Test #23:

score: 0
Accepted
time: 2ms
memory: 48284kb

input:

300 2
)(())((())))(()()(((())(((()((((()()))())(((((())))))((())())())))(((((()((((())(()())))))))))((()()))(()))((()())(())(()(((((((((()))()(())(((((()(((()())(()))))()))((()((())())))((((((((()(())((()))()()(())(()()()()()))()())())()(()(((()))((()()(((((())(()))(()(()(((()(()))(()(((())((()(((((...

output:

181

result:

ok single line: '181'

Test #24:

score: 0
Accepted
time: 1ms
memory: 40076kb

input:

300 7
()((()))())())((((()()(((())))))())()((()))()(())()())((()))))((((((()))((()()))())((()()()(()()((()((())))))))(()((()()(())()((())((((((()())(()))()))())))))(((()()())))()()(()))()))(()()(()()))()((())))((()(())(())(())()())())()))))(((())(()))))))()()(()()(())))))))))()()(()))(())()()(()))))...

output:

148

result:

ok single line: '148'

Test #25:

score: 0
Accepted
time: 0ms
memory: 46288kb

input:

290 15
))(())())(((()()()))((()())))(()))()()))())()())()((()))))())()))(()()(()))()())(())((()()())((())()))(()(())))))(())(()(((()))((()))()((())()(((())(((()))((((((()()()(((()(()((()))(())(())(((()()()())()())()((()())()()(()()))))())(())))))(()()(()()())))()))()))))))())(((())(()))))())()(((

output:

88

result:

ok single line: '88'

Test #26:

score: 0
Accepted
time: 5ms
memory: 40072kb

input:

300 30
(()((()()))(()))()(((())(()()))(((()(())()))()(()(()(((())))(((((((())()(()())()((((()((()(((((()()))()()))()))()(()()())))(())(()((((())(()(((()()))))))))))()(()())))))))())()))((()())()())())())))))((())()))()()(())())())())(()))()(()))(()(((((()))))((()((()))))()()))(()(()((((((()()(((((((...

output:

42

result:

ok single line: '42'

Test #27:

score: 0
Accepted
time: 4ms
memory: 40140kb

input:

300 300
((()())))))))))()()(()((())((()())))))(())))((()(((((()))())(((())))))((((())(()())()((((((())(()(())))())))())))()))((((()())((((((()())((())()(())(()()))(((()(())))))()())())()()(()))()()()))))(()())())()())(()((((())((((()()((()))()((((())(((((((())(()())((()()())(()())))(((()))))(()(())(...

output:

0

result:

ok single line: '0'

Test #28:

score: 0
Accepted
time: 5ms
memory: 46164kb

input:

300 1
(()((()))(()()((()(()()(()(()(()())()(()())()()(()(((()())))()())((()()((((())()(()(()()(((()(()))())()))((())))(())((((((())(((((())())((()())))((())(((()))(()(((((())((())))))))))))))((())((())(())))))(((((())))((()))((((()))()())))((((()))(()))()()))()(((((())))))((()))(()()())(()(()))()(((...

output:

261

result:

ok single line: '261'

Test #29:

score: 0
Accepted
time: 0ms
memory: 48200kb

input:

300 2
(((((((()))((((()(())))())))))))(((((((((((((((((((((())))))))))))))))))))))()))())))))(()())()()))(((())()())(())(()()(((())(()()()(()(()()((())((())))()()()((())))())(((()()))(())(((((())())(()())()()(())()(())(())()()(())((()()())())((())((())()))(()()(())(())())((()))()((())()()(())())((()...

output:

280

result:

ok single line: '280'

Test #30:

score: 0
Accepted
time: 1ms
memory: 40044kb

input:

298 7
(((((((())((((((())(((((()((((((((())(((()((())())))))))())()))))())())(()))())))())(((())))))))))((()((()(((()(()()))))))))))())(())())())((()((((((()())(()))))))(())((((((((((((()))))))))))))(()())(())()()()(()()()((()))()())((())()(()))(()()(()))((()))(((())()())(())()()()())(()()())()(()()...

output:

123

result:

ok single line: '123'

Test #31:

score: 0
Accepted
time: 6ms
memory: 40168kb

input:

300 15
()((())((()))((((((())((()()(())((((()(()))((((())(()(((()))(((((())))((())(((((((((()(((((()))((()))))(()())))())((())(((()))())))))()))))))))((((((((((((((((((((((((((((((((((((((()))))))))))))))))))))))))))))))))))))))((((((()))(((())))())((()))))((())(()))(()(())((())()(((()))))))()((()()...

output:

42

result:

ok single line: '42'

Test #32:

score: 0
Accepted
time: 3ms
memory: 44096kb

input:

290 30
((((((((((((((((((((((((((((((((((((()))))))))))))))))))))))))))))))))))))(((((())(())))(((((()))()))(()))))((()()))(()(()(())((())))())((())()())()((()))()(())(((()))()())()(()()(())()())()()(())(()(())(())()(())(())()()(())()(()))()(())))(((()((()(()))())((())())(()()(())))(()))()()()()(

output:

35

result:

ok single line: '35'

Subtask #3:

score: 1
Accepted

Test #33:

score: 1
Accepted
time: 12ms
memory: 51268kb

input:

4000 1
(((((())())()((())(())(()()())()())(()(())(()))()(()))(()((())()()()()(()())(()()()))()(())()()(()(()()())))(()))(()(((()))()())((())(()()(()()))))((()((()())())((())())((()()))(())(())(()(()()))(((())())())((())()()(()))(()()()(()(())(()))()())((()))((())()(())()())))(((()(()()()()())(())())...

output:

5599

result:

ok single line: '5599'

Test #34:

score: 0
Accepted
time: 8ms
memory: 51124kb

input:

4000 3
(((((((())))()()((((())(())()())()())(()(()())())))(()((())()((()()()((())()()))()))(())(()(()))()(()()()()((()(()))())()((()()()))(())(()()((())())))))(()(((((())))())((()()(((()()))())())())(())(()())(((()))())(()((()()()))(((()))())())())((())(())((())(())()(())()(((()))((())))))(((((())))...

output:

4568

result:

ok single line: '4568'

Test #35:

score: 0
Accepted
time: 10ms
memory: 47224kb

input:

4000 8
(((()))((()()(()())(()())((()))(((())))))(((())()(())()()()()((())())())((())()((())()))()(((())())()())(((()()()))(()()()(())(()))))(()()((()))((()())())((())(())()(())))(((((()()()())))(()()(()()())()()))()((())(()(()))((())()())((()()))()())(((())())()((()())(()()(())())()()((())))(())()((...

output:

4780

result:

ok single line: '4780'

Test #36:

score: 0
Accepted
time: 8ms
memory: 47192kb

input:

4000 21
(((((()())(())()))(()(())((((())())))()((()))()(()())()((())()())()()((((()))))))(((((()())()()()))((()))())((()))(()()(()))(()()((())))(())((()()())())(()()(())))(((())(()((())))()()(())(()((()()())(()))(()))))((()()((()()()())()())(()((()()()())())))(()()(((())()())()()((())(()))()(()))()(...

output:

3864

result:

ok single line: '3864'

Test #37:

score: 0
Accepted
time: 8ms
memory: 52716kb

input:

4000 55
((((()))((((()())))())(())((()()())((()))(()()(()((())()((())))()())(()))((()())(()())()()))))((((())))(()()(((())())())()((()))(()(()(()))(())())())((((()())(((()))())())((())())(()((()(())()(()())))()(()()(())))))(((((())()))((()())(())()()(())()()(()())())(()()(())((()()()))))))((()(())((...

output:

2909

result:

ok single line: '2909'

Test #38:

score: 0
Accepted
time: 16ms
memory: 52816kb

input:

4000 2
(((()())()(()())(())((()()))()())()((((())))())()()(()()(()())(())(()())()(())))(((())((()))(()((())))((()())((()())()())(()))((()))()(())(()())(())(())()(()()((())))()(())(())()()())()((((()))()()))((()()((()))())(())(())()()((()))()(()())(()))((())(((())()))())((()(()())(()()))(()(()))())((...

output:

5959

result:

ok single line: '5959'

Test #39:

score: 0
Accepted
time: 8ms
memory: 45232kb

input:

4000 5
(((((()())()))()(()((()())(()()())())((())((()()())()()))()(())(()()()(()))()((()))()()(((((()))))(()))()()()(()()))(((())(()(()))()()(()())(())()(()))())(()()())((()(()(()())()))(()(()()()()(())))))(((())((()())()()(())()()(())))((((()))(())())((())(())))((()))(()())((((()))))(((())))(()(())...

output:

4784

result:

ok single line: '4784'

Test #40:

score: 0
Accepted
time: 8ms
memory: 51088kb

input:

4000 30
((((()()(()())(()(())((()(()))()))(()(()((()))))(())()((()())()((())())()((())()))())()((())())(((()))()()((())(()))(()())(((()))())(())))()((()(((())))((((()))()()()()()()(())())(())(())()(())))())(((())()()((((()))())())))(((()(()))))((()(()(()())()()()()(()))()))((()((())()())((()()())())...

output:

3346

result:

ok single line: '3346'

Test #41:

score: 0
Accepted
time: 9ms
memory: 45228kb

input:

4000 200
(((())()(()(()())())(())(())(()(()()())()()(())()(()))((())())(()(()))()(()(())))(()(()))(()()())((()(()))()(()()))((()((()))))(()(()())()(())))(((())())((()((()))))(())()(()(()())(((()))()))(())(()(()())(())(())(())())(()()()()((()()())())(())((()))(()()()()()(())))((())()()((()))(())(()))...

output:

1712

result:

ok single line: '1712'

Test #42:

score: 0
Accepted
time: 18ms
memory: 47252kb

input:

4000 800
()()(())()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()(())()()()()()(())()()()()()()()()()()()()()()()()()()()()()()()()()()()(())()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()(())()(...

output:

1410

result:

ok single line: '1410'

Test #43:

score: 0
Accepted
time: 8ms
memory: 47116kb

input:

4000 1
(()))))))(())())((((()()())))((())((()(()))))())()())))))()(()))()()()())()()((()((()))((((())))())(()))(())))(()()()))())(()(()(())(((((((((((()(())(()))()((()())(())))(()))((())(()))(((())(())))())(()))(()))()((((((())))()(()()()((((()())()(()))(((())((((())((())))()(((())))())()((()())((((...

output:

3883

result:

ok single line: '3883'

Test #44:

score: 0
Accepted
time: 13ms
memory: 47232kb

input:

4000 3
()(()((())))()((()))(()()()))())))()())((()()((((()()))(()((()()((())(())())))(())))())()((()()(()))()()())))())))((()(()))(((()(((((())())())))()())())))((((((()))))()((()))))(()()(()((((())()()(())())(()(()((()))))()()((()(())))))(()()(((()())((()()))((()))(((((())(()()((((()((()((()()))(((...

output:

3322

result:

ok single line: '3322'

Test #45:

score: 0
Accepted
time: 11ms
memory: 51248kb

input:

4000 7
)(()(()))())))((())()((()))()()))()()))()(())()(())))((())))(((((((()))((((())))))))))))(()()((())(((())(((((())()))(())())()))()(((()())(())(()((()))()())))()(())(()))))(()))())())))))(()))))()))((())()))()(())())((()((((((()()(()()())((()()()(())((()))()(()))(((()))))(()))(()((())())()(((((...

output:

3230

result:

ok single line: '3230'

Test #46:

score: 0
Accepted
time: 12ms
memory: 47220kb

input:

3997 30
(())()()((())()((()((()(()((())(()((((())))((()))))))((())()()(()))()()(()(()(((()())())((()(())()))())((()()))(())(()((((()())(()))()()()((()()()(()))()))()()(()((((((())((())(()(((()((())()())()(()()((()()()()))(())))(())()))))))())(()(())))()())(()))))(())))(())((((((()))(()(((((()))())((...

output:

2556

result:

ok single line: '2556'

Test #47:

score: 0
Accepted
time: 17ms
memory: 47296kb

input:

4000 250
))))(()))))())()())))))(()()()())()())))((()(()())(()))))()(()((()(())((((((())))((((((((())()()))()()()()))(((((()()()())()((()(())()))))))))))())(()(()(()))))((()())(((()))))()())))(()((((()()(()())(()()))())(()(()((((()()((()()())())((((()))()(()(()(())))())())()()()())(()(()))())(()())(...

output:

1017

result:

ok single line: '1017'

Test #48:

score: 0
Accepted
time: 4ms
memory: 47280kb

input:

3990 1
(((((((((((((((()(()))((((())(((()())(()))))())))(())))))))))(((((((()(((((()))))))))))))))((((((())(()()))(((((((()(((())((((((())))()))))(((()(((()())(()))))))))))))((((((((())((())(())))(((((((()())))))((((((())))(((((((((())((((())((((((()(((((()((()(())))))()))(()())))(((((((((((()(((()(...

output:

40104

result:

ok single line: '40104'

Test #49:

score: 0
Accepted
time: 9ms
memory: 51116kb

input:

4000 3
((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((()))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))(())(()(()))(()(())()()()()()(()()))(())()()(())(())((()())()())(()()()())()(()()(()))(())()()((()())(())((...

output:

7331

result:

ok single line: '7331'

Test #50:

score: 0
Accepted
time: 12ms
memory: 51128kb

input:

3999 7
(((((()))((((((((((((((((()(((()())))))()))(((()((()((((())()))))(((()(((((((((())))(((()(((((((()((()(()()))))(((()((()(()))))))))))())))))))())(()(((()(()))(((((((())((((((((((())((()((()(()))((((((()())())(()(((((()))()))))))))))))()))())))))(((())((()())))))))())()))()))))))))))))((((((((...

output:

2010

result:

ok single line: '2010'

Test #51:

score: 0
Accepted
time: 13ms
memory: 45172kb

input:

3996 30
((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((...

output:

1529

result:

ok single line: '1529'

Test #52:

score: 0
Accepted
time: 11ms
memory: 52776kb

input:

4000 150
((((((((((())))((()())())))((()(((()(((((())((((((((())(((((()))(((()()))((())))))))))()))))))((()(()())))))))()))((((()())(((((((((((())(()())))(((()))))))))(((((((((()())((((()())((()(()))(()(())))))(()(((((((((())))))))))))))))((())))())))))))))))(())))(())))(())((())()()(()())(()))((())...

output:

932

result:

ok single line: '932'

Test #53:

score: 0
Accepted
time: 24ms
memory: 47248kb

input:

4000 2000
()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()...

output:

1

result:

ok single line: '1'

Subtask #4:

score: 1
Accepted

Test #54:

score: 1
Accepted
time: 8ms
memory: 47288kb

input:

4000 2
((())(()(())))()((())()()()(())()()(())()((()))()()((()()))((())())((())())(()())()(())(()(()))((()())())(()())((()()))(()()())((()))()())(()(()))((()()())(())()((())()))(())((())((())))(((()(())))()(())())(()(())(())())((())(())())((()(()))()()()()(()())())(((()))(())())((()())())((())()((()...

output:

18432

result:

ok single line: '18432'

Test #55:

score: 0
Accepted
time: 9ms
memory: 52856kb

input:

4000 5
(((((((()))(())(()(())()()(())(()))()()(((()))())()(()))(((()(()()))()())()()(()(())()(())))((()()()())(((())))((()())()(()()())()()()())()()(()(()))))())((()()())((((((()))()())(()())())())()((()()()(()()((()))()()())(())()())()()()))(())())()(((((()()(()(())()()))))((()()((())())((()())))((...

output:

4336

result:

ok single line: '4336'

Test #56:

score: 0
Accepted
time: 9ms
memory: 47204kb

input:

4000 13
(((((()()))(()()(()((())(()()()))(()))(((()()(()()))()())((())()())()())((()()(())())((()()()()))(())()(())())()((()(())())()()()()())((()(()()()(()())))(()()))(((())(()()))()(())))))()((())((((()()())(()()))(())((()((())))())()(((())()()(()()())(()))()(((()))(((())()()(())))))(((()())))(()(...

output:

3928

result:

ok single line: '3928'

Test #57:

score: 0
Accepted
time: 11ms
memory: 47276kb

input:

4000 34
(((((()())()(((()())()(()(()))(())(((())))()))(()()(()(()(()))))((((()))))((()))(((()()(())))()()(())((()))))()(()(())()()((())))()(()((()))())()((())((((()(()))(()())()()(()(())(())))(()()()())))(()()))((()))((((()()))(((()))))))((((()))((()()())())()(((((())))()(())))())(((())))()((((())))...

output:

3285

result:

ok single line: '3285'

Test #58:

score: 0
Accepted
time: 8ms
memory: 51156kb

input:

4000 89
((((((()(()(())())))((()()))((())()())((()))(())((()))((((())))())()()(()((()))())())(((()())(())()((())(())))()))()(((()((()))(()())())(()((()()))(())(())()())((())()()())(())((()))(((())()))(((()))(()())(()((()))))()()))((()())(((()(()))((()(())))))(((()))(()))(((()(()()()())(()()()())()()...

output:

2483

result:

ok single line: '2483'

Test #59:

score: 0
Accepted
time: 7ms
memory: 47136kb

input:

4000 3
((((()(())(())()(()((()(()))()())(()))())((()((())()((()()())())())())((()(()())()))(()())(((()))(())((())()))))((()())(((()))()(((())))(()()(()()))()(()()(()(())()()))((()))())(((()())())((())(())(())()()()()()((()))))((()(()()()()))()(())()()((()(())())(())))((())(())()())(((())()())((()))(...

output:

4590

result:

ok single line: '4590'

Test #60:

score: 0
Accepted
time: 8ms
memory: 51104kb

input:

4000 10
((((()))((())))(((()()())()(())(((()))))))(((((()))()()(()())((())())()()()()()(())()())()((()())()()())()()(((()())())())(((()))(()((()))())((())()())()(())()(())))((()((()(()))(()()))())(()()(())(())((())(()))(()))())((((())())(((()))))()((()))))((((()()))(()((()()())())()()(()()))()()(()(...

output:

4500

result:

ok single line: '4500'

Test #61:

score: 0
Accepted
time: 14ms
memory: 51204kb

input:

4000 100
((((((())((()))))(((()()())()((()(())))(()(()))()()((()(()))(())(()()())()))(((()))()))((()((()()))()))(((((())))(((())))()()((()()))()))(((()(())()()())()((()())((()))())()(())()(()()(()(()))))))(((((()))((()())(()())(()(())))()(()())())((()(()(()))((()()(())(()))))()()()()()((()())(())()(...

output:

2241

result:

ok single line: '2241'

Test #62:

score: 0
Accepted
time: 16ms
memory: 52816kb

input:

4000 400
()((()))(()(())())(()())((())(())())((())()()(())()()()())(()()()()())(())((()()())())((()()))(())((())((())())(())())(()())(()())((()()))(()()()())()(()((()))())((()()()))((())(()))(()())((()()()())((())())())((()()())())(())()(()(()))((()))(()(())(())()()()(()()))(()(())())(())((())(())((...

output:

1134

result:

ok single line: '1134'

Test #63:

score: 0
Accepted
time: 24ms
memory: 52816kb

input:

4000 1200
()()()()()()()()()()()()()()()()()()()()()()()()()(())()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()(())()()()()()()()()()()()()()()()()(())()()()()()()()()()()()()()(())()()(())()()()(())()()(())()()()()()()()()()()()()()()()()()()()()()()()()()()()(())()()()()()()()...

output:

705

result:

ok single line: '705'

Test #64:

score: 0
Accepted
time: 12ms
memory: 47292kb

input:

4000 2
((()()))))((((())(())))()((()))()(()))()))()(()))((())(()()(()()))(())))()))))))(())))(()((((()(((()())(((((((())()())()()(()()))))(((()))(((()()((()()(()))())(((()())()))((((((())(()()()(((((())))()))(()())(())((((()))()())())(())))()()(()()(()()())((((())(((())(())(()(((())))))(())))(()())(...

output:

3688

result:

ok single line: '3688'

Test #65:

score: 0
Accepted
time: 12ms
memory: 51200kb

input:

4000 5
)()(())(())))))(()(((())((())))))(()((())(())()(()(()((()((()()))())((()(((()()(((((()))(())))((()()()()()))())))((()))))((()()((())((())(())))(((())()((((()()(())())(())))()()()))))())(()())()))()))((())()))(())()()))(()()))()((())())(()()()(((())(((((()((()()(()()))(((((((()()(()(()(((())))...

output:

3157

result:

ok single line: '3157'

Test #66:

score: 0
Accepted
time: 13ms
memory: 52852kb

input:

3994 15
)())((()(()((()()((((()()))((()()()((((()())))(()(()()))())((()(()(((()(())())))))()())()())(()((())))))(((((((()))))())))(()()))((())))()()()(()(())(())())))()()((())))()(())))()((((())((())))()((((()))))(())()))()())()(((()(())()(())((((((()((())((((()(())()()(()))((()((()())(())())))))()(...

output:

2840

result:

ok single line: '2840'

Test #67:

score: 0
Accepted
time: 14ms
memory: 51160kb

input:

3993 100
)()()()()))()())(()(()))())(()()(()(()()())))(()))()(((((()()((((()((()()))()(()(())(()()())(((((()())((()))))())))))(()((())))))(((())))(()))()))))()()()))((((((((())(())(()((((((()(())()()(())))))((()))))()(()(((()))))(((((()((((())((()()(()))())))(()(()))))())((()))(()((()))(()()(())((()...

output:

1660

result:

ok single line: '1660'

Test #68:

score: 0
Accepted
time: 14ms
memory: 51168kb

input:

4000 4000
()()))(()))))))))(((((())(()(((())))((())((())((()())((((()()()()((((())((((()))))))((((()()())())))())))()(()))))())((((()((())())))()(()(()()()))())))))(()()()))()))))(()(((())(()))()()((())(()()())()(())))))(())(((((())()))(()()()))))()()(())())()))())(())((())(()()(()()(()())))()()(())...

output:

0

result:

ok single line: '0'

Test #69:

score: 0
Accepted
time: 9ms
memory: 45236kb

input:

3998 2
((((()(()))(()((((())(())())((()())))(((())())(()(()))))((()))))((((((((()(()()))())))())(()()))((((()()(()))((((((()()()))))))(()))(()())))((((()((()))))())((((())(()(())((((()())))))(((()))))))((()((()()())(()))()))))(((()()(()())))))((()())((())(())(((()))(()(()))))((((())((()))())))))((((...

output:

3806

result:

ok single line: '3806'

Test #70:

score: 0
Accepted
time: 19ms
memory: 51252kb

input:

4000 5
(((((((())((())(()()()))())((()())(())(()))((()()())(((())()(()())))))((()))((((()))(()())())))((((((()())()())))))(((()())(()(()))())(())))(()((((()()))((()()())()(()))(()()))(()()))((()((()))())))())((((()()())()((())(())(()())))((((())(()(((())()(()((()))()))))((())(((())()()))))((()(()()(...

output:

7799

result:

ok single line: '7799'

Test #71:

score: 0
Accepted
time: 19ms
memory: 53228kb

input:

4000 15
((((((((())(((())(()(((())(((((((((()(((())((()(()()))()))())))())))((()())(()((())))))()))(((((()((()((())))))())))))))))()))()))(()((((((((((((())(()))(((()))))))(((()))))))())))((()((())))))))()))))(((()))))(((()()())))())))))()((()((())(())()))()(()())()))())()))(((())()((())(()())))()((...

output:

2474

result:

ok single line: '2474'

Test #72:

score: 0
Accepted
time: 17ms
memory: 45272kb

input:

3998 70
)))()()))(()))))((()))(()((())(((()(()((())))))()()(()(()))((((((((((())())(((()()())(((((((()(())))())()(())()()))()()(())())(())((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((()))))))))))))))))))))))))))))))))))))))))...

output:

1289

result:

ok single line: '1289'

Test #73:

score: 0
Accepted
time: 14ms
memory: 47232kb

input:

3991 250
(((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((...

output:

752

result:

ok single line: '752'

Test #74:

score: 0
Accepted
time: 22ms
memory: 45104kb

input:

4000 600
()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()(...

output:

2403

result:

ok single line: '2403'

Subtask #5:

score: 1
Accepted

Test #75:

score: 1
Accepted
time: 462ms
memory: 80276kb

input:

100000 3
(()((())(()))(())((()())))(((()()))(()))(()()()((())))()()((())(())((())(()(()))())((())))()()((())(()()))(((())))((())()(()())(()())()(()(()()())))(()(()()))()(()((())()()()()())((()))(())(())())(((()))()(()()())()(()()))((()()))(((()()()()))(()))(((())))(((()))(()()())(()(()()))(())(()())...

output:

3832013

result:

ok single line: '3832013'

Test #76:

score: 0
Accepted
time: 224ms
memory: 80452kb

input:

100000 9
(((((())(((())))(()))(()(()))((()()()))()(())(()))(((()()(()))))(()((()()))()(((()))((())))(())(()))(((()())(())((())))(()))()()(()((()))()(()(()())))((()(()))(()()((()())))((()(())())()((()))(()))()(()))((()((())))())(((()(())))()(((()())()()())(())()()(()(())(()())())))((()))(((()())()()(...

output:

131464

result:

ok single line: '131464'

Test #77:

score: 0
Accepted
time: 643ms
memory: 81380kb

input:

100000 15
()((()(()()))()(())(()))(((()))()((())(())(())(()())))(()()()())(()((())))()(((()))()(()(()))((()))(()))(()((())()()()(()))(())(())(()())(()()))(()(())(())(()()))(((())(())))(())(()()()()()()(()))((()()())())((()))(((())()()()))((())())()((())(())(())()()(()))((()()(()))()()()())()(()())((...

output:

1352858

result:

ok single line: '1352858'

Test #78:

score: 0
Accepted
time: 238ms
memory: 80456kb

input:

100000 21
((((())()(()()()((())))((())(())))((()()((((())()))()(()()()())()(()())(()(()))))(((()())(())()()((())))))()((()(()()())()(()()(()()((()))))))()(((((())())())((()())(())()()(())()()()))(()))()(((((()())()))((()()))))(((())(())())(()(())((()))))()((((()()())())))()(((())()()()(()(()()()))))...

output:

120911

result:

ok single line: '120911'

Test #79:

score: 0
Accepted
time: 726ms
memory: 77924kb

input:

100000 27
((()))(()(()))()(())((())())((())()(())())((())())()()(()()())(())(()(()())()(())(())(()()))((())()(()))(()(())()(()()))()(()(()(())()())()(()))((()())()(()())(((()))))((()))(())()((()()()())()(()()())((())())()()((())())(()()()))(()()(())())(()()(()()))(((()))(())()())(())()(()(()()()))((...

output:

1866778

result:

ok single line: '1866778'

Test #80:

score: 0
Accepted
time: 260ms
memory: 80532kb

input:

100000 1
)))))()))(()()()()((())(()()()))())())(()()()((()))()(())(((()))((())())()((((()))()()((()((()(()))())))(()))))()()())(()(())()))(()(()((()(())((((()((()())()))())())(((((((())())))(())))((()(())()(((((()()(()(()))(()))(())))()())()))))((()())))()))(()()))(((())(()(()()()(()))(((((((())()()...

output:

99830

result:

ok single line: '99830'

Test #81:

score: 0
Accepted
time: 266ms
memory: 80396kb

input:

100000 3
((((()(((()()))((())())))(()((()))()(()())(())((())())())()(((((()))()(())))(())(((()((((())())()((()(()(()))()))))()(()()))()))(())(()())())(()()))(()))())((())()(())())())())(()))((((()())(()))))())(()))(()(()())(()())()()())(((((()())())((((()(())()()()))(()(()()((())((())()(((()(()))(()...

output:

96717

result:

ok single line: '96717'

Test #82:

score: 0
Accepted
time: 287ms
memory: 79304kb

input:

100000 7
)((()((()(()(()())()))()))(((())))(()()))()))(())))))()()))()))))()))())(((()))(()(())(()())()))()(())(((((()())(()(())())))())((((()()(()(((((((()(()((((())()))()()())))))())())()((((())())(()(((()()(())((((((())(()()()))))())())))(((((()()()())(()(()(())((((())))()))))())())()))()(()((())...

output:

95714

result:

ok single line: '95714'

Test #83:

score: 0
Accepted
time: 313ms
memory: 81120kb

input:

99996 28
()())((()))()()())))()))))))(()(())()))(()((()())()()))()))()))))())((((()))(()))()()))(()()()((()))(())((()(())))(((())))()()())(((((()((((()(()))(((()(((((()))((((()((()(())()))(())(())()(()))((()())(((()()))))((()()(((()()))()())()()(()(())((()()(())((((())(())(()))()))()()))(()()(()())(...

output:

91255

result:

ok single line: '91255'

Test #84:

score: 0
Accepted
time: 311ms
memory: 79780kb

input:

100000 30
))(()()())))()())((())))())(((((()))()))()))(())()((()()))(((())))())()((((((()(((()())(())(()())()(())((()()()))(())(((())((()()()))(())))((())((())())))))()())())(()()))(()()()(()((((((()(()((())())())((((())()(())())((((())()())())((()))())()))))()()))()(()))(((())())((()()(())())()(()(...

output:

91102

result:

ok single line: '91102'

Test #85:

score: 0
Accepted
time: 270ms
memory: 79268kb

input:

99990 2
((())()()()()()()())(()())(())(()(())())((())())()((()(()))(()))(()())(()(()))((()()(()()))()()(())()(())(()())())()(()()(())(())(()))((()))(()()(())(())(()))(((())))(()()(())()((())(())))()(()()(()()))()((()))()()((())()())(()(()))(())(()(()))(((()))())(())(())(())((()))(()()())(()()()())()...

output:

94531

result:

ok single line: '94531'

Test #86:

score: 0
Accepted
time: 335ms
memory: 79784kb

input:

99998 5
((((())((((((())(()())(((()())(()))(()())((()())))))()(((()))(())((((())((()(())())((()))))))))((())(())(()))))))((()(()()())(((()()())(())())((((()))((())))(((((())()())(()))(((()))()))((()())))))))(((((((((((()())())(()()(((()()()))))))))(((()())))(((())()())((((()))))((()))))(((((())))()(...

output:

855997

result:

ok single line: '855997'

Test #87:

score: 0
Accepted
time: 356ms
memory: 80656kb

input:

100000 15
(())(()()(())()())()(())(())((()())())(((()))()()()()()()(())()()()())(()()()()()())()(()()())(())((()())()())(())()(()()(())(())()()()())(())()(())()(()())(())(()())()(()()()(())())()((()))()(()(()))()(()()()(())()()())((()))(()()()(()()))((())())(()()()()())((()()()))((())()(())()())(())...

output:

337304

result:

ok single line: '337304'

Test #88:

score: 0
Accepted
time: 455ms
memory: 78900kb

input:

99992 29
(((((((((()()())(((()))(())))((()((()))())))(((())(()()())())(())()))(((()(())())((()()))(((()())))))())((((((((((()((()()()))(()))(()()())((((())()())())))((((((()())()((()()(()))((())((()()))(((()()))))))(()())))(((((()((()()))())((()()))))(((((())(())(()))()))))((((((())((()))))))((((()(...

output:

285381

result:

ok single line: '285381'

Subtask #6:

score: 1
Accepted

Test #89:

score: 1
Accepted
time: 229ms
memory: 79432kb

input:

100000 6
((((()()((())))()((()())()())((())()(((()()))())((())((()()()))()()()(())))(((()(())(()()))(())())(())))(((()))((((())))()))(()((())(())(())((()())))(()(()(()))(())(()()()(())())(()(())(()(()))(()())()((()))()()))(()()(())))((()())()((())((())()()(((()))(())))((())())()((()())(()))))()(((()...

output:

126039

result:

ok single line: '126039'

Test #90:

score: 0
Accepted
time: 233ms
memory: 80348kb

input:

100000 12
((()((())(((()))()())()()((()))())((((()()))()()))))(((())(()))(((((())))((())))(()()((()()()))((())()()((()(())((()))()()))())(()((()())())(()()(()))())()(()(())(())))()((()(()))((()))()((()()((())(())))))())(((()()))(()((()()))()(((()()()())()())))())(()((()())(())()(((()()))(()()()()))(...

output:

130680

result:

ok single line: '130680'

Test #91:

score: 0
Accepted
time: 541ms
memory: 79504kb

input:

100000 18
((())(()()()()())()()(())((())()()()())()()()()((()()())((()))()()(()())()()()())(()())()(()(())))(()()((()()))(())()()(()())()(()())((()())()()(())()())((())(()))(()()()))((())(()())()(((())))(()(()))(()(()))()(())()(((())())()()())((())))((()())((()())))((()))(()(()()()()((())))()(()))((...

output:

525576

result:

ok single line: '525576'

Test #92:

score: 0
Accepted
time: 229ms
memory: 80328kb

input:

100000 24
((((((())()((())))()()(())((()())())()()(((()))()()(((())))())(()())(()(()()(())((()())(()())))(()())()(()(())()())(()((()))))()(((()(()()))())())((()))()()(()(()))())((()()()()(()(()))(()))()(()))()(((()))(()()(()(()))())()((()()())()((())(())((())(())()()())()())((())))()((()())((()()()(...

output:

118587

result:

ok single line: '118587'

Test #93:

score: 0
Accepted
time: 295ms
memory: 80364kb

input:

100000 30
((((())()()(((()()())())))((()))(())(()()(())))((())())((())(())())(((()(()(()))())(()())()()(())))(((()())(()))()((())((())()())((())()()()())()()()(())()()(()()))(((()()))(()()())(()(()()(())()))(())((())(()))(())()(()))))(((())(()()())()()((()))(()(()()()()((())))))((((()()()))(()((()))...

output:

132047

result:

ok single line: '132047'

Test #94:

score: 0
Accepted
time: 273ms
memory: 80536kb

input:

99999 2
()))())))))()))()))(()()))())))())(()))(((())(()(((()))(((()((((((((((((()))(())()(()((())(()())(())())()())()())()(()(((())())()(()(())(()))))))))))()))()()))())()(()())))((()(()((()))))))(()()())))()((())))))((()(((()()(())())()()))(())())())())))(())))(())()))())())(((((()()((((((()()(())...

output:

97853

result:

ok single line: '97853'

Test #95:

score: 0
Accepted
time: 264ms
memory: 79968kb

input:

100000 5
)()()())(()())()()(())()))(()((())))(((((()())()((())()((()))()))(((()))(((()())((())((()())())()())))((((()))))(()((())(((()))(()((((()(())(((()(((()()))))((()((()(()(()((((()()()()(((()())))(((()(()()))))))()(()))((())()(((()(()())))))(((((()(())())(((()())()(())(()))()()()))()()())(((())...

output:

96190

result:

ok single line: '96190'

Test #96:

score: 0
Accepted
time: 268ms
memory: 79852kb

input:

100000 15
)())((()))()((()()((()())()(((((())())()()((((()()(()())()(()((())))))(()()(()(()((())))))())(()())()))))())())()())()()(((((()()()()))))(((((()())())(()((()())()))(()()((()()((()((()))(((())()))(())((())(())))))())()((()()))(((())((()((()())(())))()()(())))(())(()()())))()())()((()(()(()(...

output:

93249

result:

ok single line: '93249'

Test #97:

score: 0
Accepted
time: 283ms
memory: 80372kb

input:

100000 29
)()()))))()(()()()))(()())()(((())()))()())))())(((())()())))))))))(((())())((()(())()))(()))())())((((((((()(()((((())()())(()())))())((()())(()))(()())()())(((()()())()(()))((((((()(())((())))((()))(((())(())(()))(())()(())((()())(((()(()((()(())((()()(()()(((())()))()(())))((()()))(()))...

output:

91679

result:

ok single line: '91679'

Test #98:

score: 0
Accepted
time: 283ms
memory: 82284kb

input:

100000 1
((((((((()((((((()(()))(((((())(()))(()))((((((((((((((((((())((())((()((((((())(())))(((()))(())))())))))))(()((())(()()))))))(((((()(()())))(((()))))(()))))(((((((())())((()())))))((()())((((()(((()(((()((((())()))())))()))((((())(())))(((())))))))))((())))))()))))))(()))())))((((((((((((...

output:

10653510

result:

ok single line: '10653510'

Test #99:

score: 0
Accepted
time: 273ms
memory: 79568kb

input:

100000 3
()((((((((((((()()))())())((((((((((((()())(()()))((((((((()(()((()())())))((()((()((((()()))(()))))))((((()))((((((())(()(((()))()))))(((((((((()(()))(((((()((())))))(()))(((((((())(()))))())((((()(()))))(())))))))()))((((((((((())())(((((())))(((((())()))(((()(((()())((()((()))))))))))(()...

output:

99072

result:

ok single line: '99072'

Test #100:

score: 0
Accepted
time: 550ms
memory: 79816kb

input:

99995 7
((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((...

output:

3068236

result:

ok single line: '3068236'

Test #101:

score: 0
Accepted
time: 393ms
memory: 78748kb

input:

99995 28
(((((()))()(()))()(()()((()))))())(((((((()(())(())))((((((((())))()(()(()))))((()))))(()()(())))))))(()())((())()))(((((()())())))((((((((((((())))())())))))(((())())(((())())())(()))())((())()())(()))(((((((()))(((()))((((((())()))(()())))(())()))(((((((()()())(()()))((())(()((()()))(()()...

output:

193063

result:

ok single line: '193063'

Test #102:

score: 0
Accepted
time: 641ms
memory: 80896kb

input:

99991 30
(((((((((((()())(((((((((((())(((()((()(((()())))))))(())))(()))((((()()))()))))((()(((((()()))(()))((())((((((((((())(())))))()))))(((())((()(()((()((())))(((((()(((((())((((((())((((()())))))))((())))())))))))))))))))(((()())(((((()(())))(())))(()())))(((((())())))))))))))((()())(((((()((...

output:

166229

result:

ok single line: '166229'

Subtask #7:

score: 1
Accepted

Test #103:

score: 1
Accepted
time: 219ms
memory: 72764kb

input:

80000 81
((((((()())((()((()))))(()())()(()(((()(()())(()())())(())))()(())(()()))()))(((()(()))((()))(())((((())))(())()((()))())((()(()())))(())(()()))(((()()))(()((())))())()(((()()))(()())()()(((()((()))(())))((())(()((())))())(()())))()()()((()()(()()(())()()((()))(())()))((()(())()()))(()(()()...

output:

87799

result:

ok single line: '87799'

Test #104:

score: 0
Accepted
time: 363ms
memory: 72836kb

input:

80000 729
(((())(()))(()()())(()(()))(()())(()()()())(((()()())))()(()()()(()())))(((())((()()())))())((()(())()()())((()()()))()(()()()())()()(((())(()))(()())()()()(())))((()))((()())()(()()())(()()()()())(())(((()))(()(()())())())(()()())(()(())()()()()(())())()())(((())()))(((()())(())()(())((()...

output:

76309

result:

ok single line: '76309'

Test #105:

score: 0
Accepted
time: 267ms
memory: 74616kb

input:

79770 6561
(((((((()()))(()())()()()(((())))(())(()((()))())()(()()(())()()))(()()(()())()(())(((())()))(()))(()()())(()((()(()())())(((()))())()(())()())(())))((()))()((((())()))(()())))()((()())(((()(())()())()(())((()())(())))))((((()((()())())(()(())()()))()(())(())(((())))(())()))(()(()())()))(...

output:

19831

result:

ok single line: '19831'

Test #106:

score: 0
Accepted
time: 234ms
memory: 76472kb

input:

80000 8
((()(()())((())()((()())))()(()(()(())())()))((())()()()()()(()))()((((())()())()(())(()))()((())()()(()((()))()(())()()())((()))(()(()())()))())((()(()))(((())()))(((())))((()))((())))(()((())()()()(()()())()())(()()()(()(())(())))))(()((()())((()))(()(()())())()()())(()((())(())()(()())(()...

output:

119650

result:

ok single line: '119650'

Test #107:

score: 0
Accepted
time: 282ms
memory: 72500kb

input:

80000 144
((()((()(())))((())(())(()()))())(()()(())((((()))())())(()())())(((()()()))((()())()()())(())(()())(((())()())(()()())((()()())()()))(()(())()())((()))((())(()())()()(()(()))(())()(()))(())((()())(((())())()((()))(()())(())())())())((()()()()((()))))(((())))(((())))()((((()()())()())()(()...

output:

94339

result:

ok single line: '94339'

Test #108:

score: 0
Accepted
time: 372ms
memory: 72796kb

input:

80000 2584
(()()()()(())()(((())))(()()()()(()(()())))((((()())()))()(()())())((())()(())(()))()((())()))((((())))(()(()())(()()()()))((()())())((())()((())()(()())())()()()()(())())()(())(((()))((())))(()((()))(())(()(()())())(())))((())((()()((()))))()((()()(())))(()(())(()())()(()()(())()))()(()(...

output:

45749

result:

ok single line: '45749'

Test #109:

score: 0
Accepted
time: 285ms
memory: 76480kb

input:

79993 1000
()))())(((())))))(())((()(())))()(((())(()()()()(((())()()()())(()()()())(((()()((()))()((())())()(((())()(())(())((((()()((()(((())((((()(())()())))())())((())()(())(())((())(((())((()()((((())())(())))(((()(()))()))(((())))))(((((((((()(((()(()())())()))()(()()()())()()((())((()(())()((...

output:

43241

result:

ok single line: '43241'

Test #110:

score: 0
Accepted
time: 320ms
memory: 73892kb

input:

79995 4000
)(()((())()((())))())()(()))(()((())))))))))(())(((()()))()))((()())())((((((()((((((((((())((())(()))(()()(())))))))()()(((())))()()()))))((()()(((((())())(((())()((()()()(((((())))(()(())))(((()))((()())()))((((()(((()()())())())))))())))(((((()())((((((((())))))()))))((((())())((((((((...

output:

23347

result:

ok single line: '23347'

Test #111:

score: 0
Accepted
time: 187ms
memory: 76424kb

input:

80000 101
(())(())(((())(()()(())())(((((()())()()))()()((())(()))()((()()))()()())(()()(())()())((()(()())))()())((()(()(((())())()))(()()()()((())))((()(())()()((()))(((())()()()()())))((()(()())))(()())()()()()()()())((((()(()))))())(()()(())()()((())((())(()())()()))(()()())))()(()))(()(()()(())...

output:

105978

result:

ok single line: '105978'

Test #112:

score: 0
Accepted
time: 221ms
memory: 72568kb

input:

80000 101
((()(())()(())(())()((()))()(()()()))(()()()(())()()()()()()()()()()()()((()))()()()(()()()(()()))()()()(())()()(())()()()((()))()()()(())()()()()()(())()()(())()()()()(())()()()()()()()(())()()()()(())()()()()()()()()(()())(()))(()()()(())()()()()()()()()()()(())()()()()()()()()()()()()()...

output:

297923

result:

ok single line: '297923'

Test #113:

score: 0
Accepted
time: 239ms
memory: 75684kb

input:

79993 500
)(((()(()())(()())(()()()())(()))(()(())()()()()())((()())(()))((())((()())(()(()())))(()())(()((()))()(((()))())()(()))(()()()())(((())(())())))(((())((()(()()))))(())(()()()())(((())()))(()()))(()(())())((()())()()(()())()(())(((()()))()())(()()(()))())(((())(()()()()()()())()(()())(())(...

output:

83615

result:

ok single line: '83615'

Test #114:

score: 0
Accepted
time: 267ms
memory: 74724kb

input:

80000 500
()()()(())()(())(((()())))(())(()()()(())()(())()()()()()()()()()()()()())(()((())())())(()(()(())))(()()()((()))()()())(()())(()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()(())()()()()()()()()(())()()()()()())(()()(())(())()()(()())(())(())()()()()()()()()()()()()()()(...

output:

200154

result:

ok single line: '200154'

Test #115:

score: 0
Accepted
time: 226ms
memory: 73444kb

input:

79995 1001
()((()()()()()))(()()()()(())(()())(()()()())(()()())(()()()()()(())()()(()()(()))))(()()()()(()()()()()(()()()())(())((()()()()))())(((()()(())()))((()()()()()()(()((())(()))))())(())()()()())((((()()(()()()(())(())))((())(((())))))()(())()()()())(())(())(()())())((((())(()()()()()()()()...

output:

73878

result:

ok single line: '73878'

Test #116:

score: 0
Accepted
time: 308ms
memory: 73108kb

input:

80000 1001
(((())(())(())(()()()())(()))()(()()()()()()()()(())()(())()()()()()()()()(())()()()()()()()()()()()()()(())()()((()))()()()()()(()()())()()()()()()()())()(()())((()())()(()())()()()()()())((())()()())((()())(())(((()))(()))()()(()))(()(())()()()()()()()(())()()()()()()()()(())()()()()()(...

output:

129694

result:

ok single line: '129694'

Test #117:

score: 0
Accepted
time: 264ms
memory: 72704kb

input:

79995 3001
((()()()()(()())((())(())(())))(()(())())(()()())(((()()())()(()(())()((((((())()()))()()(())()()()()))()()))(()()()()()())()((())()()()()()())(()(()))()())(((()))()(()()())()()()())(()(()()()))())(())(()()(())(()())(())(())((())()())(((()())(())()(())(())()))((()(()()(())(()())(()()()()(...

output:

47142

result:

ok single line: '47142'

Test #118:

score: 0
Accepted
time: 355ms
memory: 74632kb

input:

79991 3001
((())(()())()(())()((()))((()))(())()()()(())(()()()()()()())()()(())()()()((()()))()(())()()(())()((()))()()(())(())(())()(())(()()())()(())()()(()()()()()())(())(()))((()()()()()()()()()()()()()())(()()()(())(())()()()(())()()()()()((()))(())(())()()(())()()(())()(())()(())()(())()())((...

output:

65975

result:

ok single line: '65975'

Test #119:

score: 0
Accepted
time: 214ms
memory: 74612kb

input:

80000 1
((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((...

output:

21979221

result:

ok single line: '21979221'

Test #120:

score: 0
Accepted
time: 334ms
memory: 78088kb

input:

80000 5
(((((((((((((((()((()))))))())((()(()))((((())))((((((((((((((((())))))((((((((()))(()())))()))(()))))())(((((())()))))))))))(())))((((((((((((((((((((((((((())((((())(())))))()))))((((((()())((((((((((((((((((((((((()(((((()(()))())))))((()((((((())((())()))(())))(()()))))))(()(((((((((())(...

output:

89513

result:

ok single line: '89513'

Test #121:

score: 0
Accepted
time: 307ms
memory: 74452kb

input:

80000 50
)())()()())((()(()((((()))(()()()()))()((((()()))(())))(()()((()(())(((((()()(()()))()((()((())))(())()(()())())(()(()()())(((())()))))(())(()))))()((((())(()(((((()(()())((()((((((()))((())))(((((())((((()))(()((())()))()(((((()))()(()(())(()((((((()((()())()()))()))(())()((())))())()()())...

output:

58479

result:

ok single line: '58479'

Test #122:

score: 0
Accepted
time: 390ms
memory: 73996kb

input:

79997 300
((((((((((((()((())(((()()())()))))((((((((())())))((()())))))(((()())((()))()))(((())())(()()())())))((((()())(())((()))))((()((()(())((()))))(()))))(()((()(((()))()))))))(((((())(()()))))(())((())())))(((((()))((()))(()()))((((())(())()))(((((((()))((((())))((()))())(()))())))()(((()()))...

output:

31597

result:

ok single line: '31597'

Test #123:

score: 0
Accepted
time: 365ms
memory: 75152kb

input:

80000 600
((()()))(())(()())(()()()())(())(())((()))()((())())(()(()()))(())(()(()))(((()))()()())()(()()())((()()())(()))()((()()))((())()(())()())(()(()())()(())()()())((()()()))(((()))()(())()()(())(())()()()())((()))(())()(())(()())((())()())((()))()(())(()(()())()()())(())()(()(())())()(()())((...

output:

55476

result:

ok single line: '55476'

Test #124:

score: 0
Accepted
time: 374ms
memory: 75600kb

input:

79996 3000
(((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((...

output:

8310

result:

ok single line: '8310'

Test #125:

score: 0
Accepted
time: 445ms
memory: 77828kb

input:

79998 5001
(((((((())()(())))()())(())((((())((())(()())())((())()(()()())))(((((()()))()))()(()(((()())((((())(()())))))(()()(()(()(()())((()))))))((((()))()((((()))))))))))))((((((())(((((()())))()(()()(()))))))((((((()()())))((((((())(((())((())))))((()))(()(())))))))((())((((()))()(()))((()())()...

output:

5056

result:

ok single line: '5056'

Test #126:

score: 0
Accepted
time: 345ms
memory: 73048kb

input:

79997 7001
(((((((((())((()(((()(((())(())))))((()))))))(((((((())))(((((((())(((((((()(((())())))(((()(()))((((((()(()))))()))))))((())))((((((((((()((())((((())(((((()()))))))))))))()))(((()()))))))))))))))()))((()())))))(((())())((((((((((((()((()())))(()()))(())))(((((((((())(((()))()))())(())))...

output:

9887

result:

ok single line: '9887'

Test #127:

score: 0
Accepted
time: 1553ms
memory: 71532kb

input:

80000 40000
()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()...

output:

1

result:

ok single line: '1'

Test #128:

score: 0
Accepted
time: 935ms
memory: 72644kb

input:

80000 150
()(())()()(())()()()()(()())()(()()())()()()(())(())(())()()(())(()()())((()))()()()()()()(())()()(())(())(())()()()()(())()()()(())(())()()()(())()(())()()(())()()()(())()()(())()()()()()()()()()()(())(()()())(())()()()()()()()()()()()()()(())()()()()()(())()()()(())()()()()()()()(())()((...

output:

2783888

result:

ok single line: '2783888'

Subtask #8:

score: 1
Accepted

Test #129:

score: 1
Accepted
time: 740ms
memory: 72552kb

input:

79856 243
(())()(())(())(()()())()(())()(()())()(())()(())()((()))(())(()(())())()(()())()()(())(())((()()))(())(()()())(()())((()())()())(())()()(())()(())((()()))()()(()()())(())()()(()())(())(())((()))(())(())()()()()()(()(()))(()(())()(()))()()()()()()()()((()()))()()()()()(())()(())(()())()(()(...

output:

794572

result:

ok single line: '794572'

Test #130:

score: 0
Accepted
time: 261ms
memory: 71000kb

input:

79156 2187
((((((())))((()))()(()(())()()())(()))((()(())()))((((())()))(()(((()()))())(()())(())(())(()()(())(()))(((())))(()()))()(((()()()))(()(()())))(((())(()(()))(())()())()()(())))((())()(())())(((()()()()())(())(())()((((()))(())())))((()(()()))((()()))())(())(()(()(()))()()()())((()()())())...

output:

43675

result:

ok single line: '43675'

Test #131:

score: 0
Accepted
time: 187ms
memory: 72608kb

input:

80000 2
((())((()))()(()()(((()))))(()(((()())(()))(())(()()))()(())(()())()((()))((()()()())()(()())()())(()((()()))(()(()))(()))(()()(())()()()))(((()(())())((()))())((()()()(()))((()())(())())(()())))(())(()()((()(()()))()(())()())()((()))((())()))((()))(()()(())(())())()((()(()()()()())((()()))(...

output:

120005

result:

ok single line: '120005'

Test #132:

score: 0
Accepted
time: 285ms
memory: 75736kb

input:

80000 34
((((()))((()))((()(()())(())))()())((()())()((()()))()()()((())())(()(()))(()()()()())(())(()(()()()(()())())()())))(((()(()()))(()()(()))()((()))((())()(())()(())()()()((()())())())(()((()())()()())()(())()()(()()))()(()(()(()))(()))())((())()(()(()())()())(()(()())()()))(()(()))((((())))(...

output:

112242

result:

ok single line: '112242'

Test #133:

score: 0
Accepted
time: 252ms
memory: 75760kb

input:

80000 610
((()())((()(())(()))()((())))((((())())()())((())))()(()()(((())))(()()(()()))(()(())((()))(())()()(()))()(((()))(()))(()())()((()((()))(()()))()))()((()(()))(()())(((()())()())((()()))(()())()(()()))()(()(()()()()())()()(())))()((()(()())()))()((((())()()())())()(()()((()()())()())))(((((...

output:

72136

result:

ok single line: '72136'

Test #134:

score: 0
Accepted
time: 359ms
memory: 72976kb

input:

80000 10946
(())(((())(()(())())))((((()()))()((()()())))())(()((((())))()(())())((()((()))))((())()(()(()())()())((())()))()(()()()()))((((()())))((())()(()))())(((())(())(()(())))(()(()(())((())))())(())(()(())()()()))((((()())()))(()()()((()))()())(()(()))()((()())((())))()((()()))(()((()()))())(...

output:

12534

result:

ok single line: '12534'

Test #135:

score: 0
Accepted
time: 296ms
memory: 76380kb

input:

79994 3000
()()(((()()(())((())(()(()(()))))((()()()))))()((((((()((()))()()()(())())((((()))))((()(()(())()((())))()))(()))())((()((()()(()())((()()()()((()))(()(((()(((((()(())()()()()))())())(())))((()))(()())()(())))(((()(()(()(())(())))()))())()()))())))))()))()(()())()(((())()((())))())))())((...

output:

27732

result:

ok single line: '27732'

Test #136:

score: 0
Accepted
time: 172ms
memory: 72540kb

input:

80000 80000
(()))((()())(())()())()((((()())())())())(((()(((())()()())()(((()(()(())((((()(((((((())))()((())((((())))(()))(()((((((()))())(())()()())()(()))()())())()())))()()))())))(()()())(((())((()()()())(((()())))))))()()(()))((()(()((((()))))()()())(((()((((()))))((((()((()()()()))((()()(()((...

output:

0

result:

ok single line: '0'

Test #137:

score: 0
Accepted
time: 210ms
memory: 72608kb

input:

79991 101
(((()(()()())((()())))()(()())((()())()(()())(())()(())(())()(())())(((())))(()()()()()(())()()()()(())()(())()()())(()()()()()()()()())(()()()())((()(()()()()()()()()()()()()))(())(()()()()()()()()()))((())()()()()()()()()(()())()()(())()(())()()()()()()()()())(()()()(())()(()(()))(())))(...

output:

174618

result:

ok single line: '174618'

Test #138:

score: 0
Accepted
time: 263ms
memory: 73292kb

input:

79993 101
(()()(())()(())()(())((()))()()()()()(()()())(()((())())(())()()()()()()()())((()))(()((()(())))(()()(((()())))))(()()(()))(()()()()(()))(()(()))()(((()))()()()(())()(())()())((()((()))((((()))))(()()))(())()())(())(()())(((((())()))))(()()(()())(())()()()())((())()())((())(()(()))()(())()...

output:

469537

result:

ok single line: '469537'

Test #139:

score: 0
Accepted
time: 228ms
memory: 76472kb

input:

80000 500
()(())(())()(()(())()()(())()()()())(()()()()()()()()()()()()()()()()()(())(())(())()(())()()()()()()()()())(()(())(()))((()()()()()()()()()()()(())(())()((()))()()()()(()())(())()()()()((())(())))(()()()()(())()()(())()()()()()()(())(()()()()()()()())()()(()()(())()((())))(())(((())))((()...

output:

142093

result:

ok single line: '142093'

Test #140:

score: 0
Accepted
time: 322ms
memory: 75832kb

input:

79992 500
(((()())((()()))((()()()()()()())((())))(()())(()))((()(()))())((()()()()()()((()()))()(()()())(()(()))()()()(())()()()))(()()(()())(())(()())(())()()(()(()))(())()())(((()()()())()))((()()()))(()()()()()()()())((())(((((())))(((()))))))(()()()())(()()()((()))()(()())(()()()())(()())(()(((...

output:

174691

result:

ok single line: '174691'

Test #141:

score: 0
Accepted
time: 248ms
memory: 73828kb

input:

80000 1001
(((())(()()()()()()())(((()))()(())()()()()()()(()()())(((()()))))()((()))()((()()(())()()())(()(()())(())()(())(())()(()(()))()()()))(()((()))()(()))(()()(())()()())((()())()(())()()()()()())(())()(())((((()))()()))((()()())(())()((())()()()(())(())(())))(((()))()()()()()()()()()()())(()...

output:

98911

result:

ok single line: '98911'

Test #142:

score: 0
Accepted
time: 381ms
memory: 73108kb

input:

79998 1001
()(((()((()))())(()()()())(())())(()()()()(()))()()(())())(()())(()()()()()()()()()()()()()()()()()()()()()()(())()()()()()()()()()()()()()()()(())(())()()()()()()(())()()()()()()()()()(())()()(()()())()()()(())((()))(()()())()(())()()()()(())(())()())(()()()()()()()()()()()()()()()()()()...

output:

171234

result:

ok single line: '171234'

Test #143:

score: 0
Accepted
time: 340ms
memory: 74828kb

input:

80000 3001
((((())))(()(()())()()()(())(())(())()()()((())())(())()(())()()()((()))()((()))()()(())()())(((())(())(())()(()()()(())())()(())(())()(())()()()()(())()(()()())()(())()(())()()))(()()()()(())()()()()()())(()()(())()(()()()()())()()())(()()()()()()()()()()()()()(())()()()()()()()(())()())...

output:

57222

result:

ok single line: '57222'

Test #144:

score: 0
Accepted
time: 419ms
memory: 75936kb

input:

79999 3001
()()()()((()))(()())((()))(())((())((()))()((())((((())))())())(()()((()()()())))()()()()(())()())((())()((()))(())(())()()()())((()(()))(()())(())()(())()(())()()(())()()()(())(())()()()()()(())()()()(())()()()())((())((()))()(())(()()()())()()(()(()()()))(())(())((()))(())()()()()(())()...

output:

81628

result:

ok single line: '81628'

Test #145:

score: 0
Accepted
time: 294ms
memory: 73332kb

input:

80000 2
(((()())()((((((((((((()))()())((()())((()))))))()))))))))(((((((((((()))(((()()(()))()((())()))())((()(()()))((((())((())(())))((((((()((()()))(()))(((())(()(()))(()))(((()))))))(((((()))(())))(((()(())(())))(()()))))((()())(((()()())))(()()()))))(()(()()())))((())(())))))((((()()())()(()()...

output:

7982716

result:

ok single line: '7982716'

Test #146:

score: 0
Accepted
time: 299ms
memory: 72688kb

input:

80000 10
()((())()())()(()()()()()())()()()(()(()))()((())(()())()()()()())(()(()())())(()()())()(())(()())(())()((())())()()()()(()()()()(())()())()(()(()()(())())())(())()()(())((()())())()(())(()()(())()())()((()()())()((()))()()())(()(())()())((())(()))()(())(())(()()()()()()(())(()())()()(()())...

output:

40264

result:

ok single line: '40264'

Test #147:

score: 0
Accepted
time: 380ms
memory: 76744kb

input:

80000 100
(((((()((((()(((())()())))))((((((((())(()(()())(()()))((())()()))(()))((((()())(())))((((()))((()()())(()))))))(((())((())(()))())((())(()(()())))((()))))))((()(())(()()()))())((((()(())(())))((()))(((())((())(())(((())()(()))(((()()))())())))(())))()((((((()()())())((()))))))))((()(()))(...

output:

128492

result:

ok single line: '128492'

Test #148:

score: 0
Accepted
time: 459ms
memory: 75292kb

input:

80000 500
)()(())(()()()))((()(()(())(())((())(())())())))))))(()(())())))()))()((((()())(()()(())())))()(((((())())((())(()()()())())()())()()(((()(()((())((())((((())())))))())))((()))(()()))(())(())))(()(())(()))((((()()(())(())()()((((()()(())()()))(((((()()((()())()(()(()(())()))()())))))(((()(...

output:

58413

result:

ok single line: '58413'

Test #149:

score: 0
Accepted
time: 278ms
memory: 75932kb

input:

80000 1000
(())((()))(())(()(()()))(()())((())()(()()()))((())()()()())(()(())()()()()()())()(()()())()()(()()())()((()()))((())())()(())(()())()((()))(()())(())(()()()(())()())(()())(()())((()())()())()((()))()((()))()()(()(()))(()()(()))()(()(()()))(()())()(()())(()((()))()())((()))(()())((())()((...

output:

32493

result:

ok single line: '32493'

Test #150:

score: 0
Accepted
time: 373ms
memory: 75560kb

input:

80000 4001
(((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((...

output:

15516

result:

ok single line: '15516'

Test #151:

score: 0
Accepted
time: 359ms
memory: 74288kb

input:

79997 6001
((((()()((())()())))(((((()()())((((())())((((((((((()))())(()())(())))))))))))(((())(((())()(()(()())))())(()(()()(()))()))((()())()(()(((()(())))()))))((()(((()))))))((())(()()(((()()())()())))))((((((()(()(((()))))))((()())(((()()())((())()()))(()())((()())((()())(())()))))))((()())(((...

output:

15468

result:

ok single line: '15468'

Test #152:

score: 0
Accepted
time: 444ms
memory: 71600kb

input:

79998 10000
(()()(()((()))()(())))()(()(()()(())))()(()))))(()((()()()(((())(()())()))))()()(())(((())))())()())()))()(())(((()))))((())(()(((()()((()))))((()))))())(()(((((()))())()())(()())((((()()()())()()))((()))()((()())((())((()(())(()))(((()(()))(()))()))())()()(()(()()()(()()(()((((((()()(()...

output:

5669

result:

ok single line: '5669'

Test #153:

score: 0
Accepted
time: 166ms
memory: 76372kb

input:

80000 40001
()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()...

output:

0

result:

ok single line: '0'

Test #154:

score: 0
Accepted
time: 1027ms
memory: 74476kb

input:

80000 250
()()()()()()()(())()(())()(())()(()())()()(())()(())()()()()()()()()()()()()()()()()()()()()()()()()(())(())()(())()()()(())(())()()()(())()()()()()()()()()()()(()())(())()()()()(())()(())(())(()())()()(()())()()()()()()()(()())()()()()(())()(())(()())(())()(())()()()(())()(())(())()()()()...

output:

1669944

result:

ok single line: '1669944'

Subtask #9:

score: 1
Accepted

Test #155:

score: 1
Accepted
time: 278ms
memory: 80428kb

input:

99599 64
((((((()(((())()))))((((((()))()())())())(()(()(()())))(()(()()(())())((()(()()))((()))()(())()())()(()(())()((()()())()())()(((())()))(()))((())(()(())()))(()))())()(((())(((())()((())))())(()()(()))(()())()((())((()())()(())())(())()(())((())(()()(()))((()))(()()())))()(((()))(())))(())((...

output:

110447

result:

ok single line: '110447'

Test #156:

score: 0
Accepted
time: 310ms
memory: 78116kb

input:

100000 1024
((((((((()()))(((()()()(((())())))()(((())))((())()(()()())(()()))((()())(())()()))))(((((())())()))))(((((((()))))())(((())()()((())))((()()))())()(()()())((()()(((()))()())(()(()()))()((()(()))(())()(())()()(()())())()((()))(())())()()))())(((()()((()(())()))(()))((()())((()()()))()(()...

output:

74496

result:

ok single line: '74496'

Test #157:

score: 0
Accepted
time: 419ms
memory: 80376kb

input:

99065 16384
(((((((())((()())))()((())(((())))(()(())((()(()(()))))(()))())((()(((()())))()((())(())(()())(()()))((())()())(())(()(()(())(()))(()((()))))()(()))((()((()))()))()())(((()))(()(())())()(()(()(()(()()(())))(((())))))(((())(()())))(()()((()))()(())()((()))(()(())(())()))(()))(()(()))(()()...

output:

10056

result:

ok single line: '10056'

Test #158:

score: 0
Accepted
time: 313ms
memory: 79824kb

input:

100000 8
(((((())(())())(()()(()()))()((())()(())(())()))())()(((())(())())((())()))()((())(()()(((())))(()(()())(()())()))()(()(())()(()())())()()(()(())(()())))()(()((()()())()())((())))(()((()())(())()()(((())())()()()())()())(())(()))(((())()()())((())(())))((()()((())()()()))()(())((((()))()())...

output:

149395

result:

ok single line: '149395'

Test #159:

score: 0
Accepted
time: 272ms
memory: 80428kb

input:

100000 144
(((((())(()(())()()(())())(((()))(()()))))()((()()(()())(())((()(()()(())))))(())(()()))((())((((()))()()(()))()())((())()())()()(()()()()(())(()()(())())))()((()(())()(()))()(()((()))())(()(()(()))))((()((()))()))((((()(()))((())()))())(((())(())()(((())())))()))((((())))()()(()()()())((...

output:

110178

result:

ok single line: '110178'

Test #160:

score: 0
Accepted
time: 590ms
memory: 78140kb

input:

100000 2584
((())()((()))()(()((()))()(())()()()(())())()(()()()()))(()(()(()())))((())())((())()(()()())(()))(((())()())(()())()(()()))((()(()))((())())(())()(()))(((()))((()))(())(()()())()(((())))(())(()(()()(()()))()))(((()()))()(((())))()(())(())()(())()())((())(()()(())))(())(())(()(()()))(()(...

output:

68085

result:

ok single line: '68085'

Test #161:

score: 0
Accepted
time: 356ms
memory: 80484kb

input:

99994 501
()(()())()()))())(()(())()((())((((()((((()()())())))(((()))()())()))))(()()()()((())((()(()))()())()((()())))))))()()))(())))(())))((())()(()()))()))()))))))()))((()(())()((()(()((((((((())()))(((())(()())()()))())()))(()(((()())))()((((()((())()(()())(())(()()((((()())))(()())()(())())((...

output:

67411

result:

ok single line: '67411'

Test #162:

score: 0
Accepted
time: 424ms
memory: 79764kb

input:

100000 3000
()()()(())()))((()())(())((((()))()())))(())(()))()(()))((()))(())((()()())()(()((()))()))))(())(())(((((()(())())))((((()))((())()))())((()(())(()))(())()()(())((()(())))))()((())))()(((()))((())())()()()(())))))()(()())(()((()()()()()()((()()))()))((()(()()())))()()()))))(()((((())((()...

output:

39091

result:

ok single line: '39091'

Test #163:

score: 0
Accepted
time: 241ms
memory: 81456kb

input:

100000 101
()(()())(()(())()()()()())((()()()()()((()))(()())(()(()()()(()())))()(((()))()(()()()(((()))((())()))((()))(()()()()())((()))))))((()(())()())(((()()()()()())((())(()()))(()()()()()()()()()())(((()())))(()(()((()))))(())()())()(())))(()()(())(())((())(())()())(())(()()()()()()())((()()((...

output:

134322

result:

ok single line: '134322'

Test #164:

score: 0
Accepted
time: 275ms
memory: 79392kb

input:

100000 101
((()()(())()()()())(()())((())(((())(())()))()((())())(()))(()()((())(()))((()()()))()()()((()))(((()()))))(()()()()())((())(())(((()))())()()(()))(((())())()((())())()()()()(()()())()(())(((()))))((()()()())(())()())((())()())(()()()(()())()()()()()()()(())()(()))(()()()())((())()()(())(...

output:

376709

result:

ok single line: '376709'

Test #165:

score: 0
Accepted
time: 256ms
memory: 79756kb

input:

100000 500
(((((()()))(((()))(((())()()()()())(()())(()(())()(())))((((()())((())))(())(())(())((())())(()()()))(()(()()())()(()()())((())))(((()))()))((())((())()()()(())(())()()()((()())))((((((())()()()()()))()(()()))(()()())))(((())()())()(()())(()())((((())))((())))))((()()(())(())()((()))()))(...

output:

110012

result:

ok single line: '110012'

Test #166:

score: 0
Accepted
time: 370ms
memory: 80072kb

input:

99991 500
)(((((()()()()((()))()(()()())((()))(())()())()()()))((()())(())(())(())(())()(((())))()()(())()(())()()()(())()()()()()()()()()()()()())(()()()()(())(()()((())())()()))((((()))())())(()()()()()()()()()()()()()()()()()()()(())()()(())()()((()))()()(())()((()))())()(()()()()())(()()(()())((...

output:

280975

result:

ok single line: '280975'

Test #167:

score: 0
Accepted
time: 280ms
memory: 77928kb

input:

99993 1001
(()()()(()()(())(())(())(()()())()((())()(()))())(()(((()(())((()()))()()()()()())(()()()()()())(()())(())()()()())(()()(())(()())(()()((()))()())()(()()()(())))()()()()())(((()()(())(())(())(()(())))(()()()))))((()((()))(()())((()()()))(())(()()()()()()())()((((()))())))((((()(())()(((()...

output:

99251

result:

ok single line: '99251'

Test #168:

score: 0
Accepted
time: 390ms
memory: 78344kb

input:

99992 1001
((()()()()()()(())()()(())()()()()()())(()()()())(()(()))(()()()()())((()())(())()()()())((())(()())(())()(())(()()((())))((()))(()))((())()()()()()()()()()()()()()())(())((()()(())())(((()())((()))))(()(()))(()()()()()()()()()())(((())(())))(((()))()((()()()))))((()()))(((())))(()())(()(...

output:

183863

result:

ok single line: '183863'

Test #169:

score: 0
Accepted
time: 326ms
memory: 79924kb

input:

100000 3001
((()((())((()))((()()())()())(()())(()(())()()()()()()))((((()()()()(()(())()()(())()()()())((()()()()())((())()))((()()()()((())())(())()((()(())))((())()))((()()()(())())((()())())((()))()())())(()()()()()()()))(()()(()))((())((()()()())()))()()))(()()()(()()()()(()))(()()()()())(())((...

output:

66312

result:

ok single line: '66312'

Test #170:

score: 0
Accepted
time: 473ms
memory: 79732kb

input:

99992 3001
(((((()())))((())())(()()()())(())(()())(()())(())(()))(())(()()())(())(()()()()()()()()()()(())()()()(())()()()()()()()()()())((()()()()()()))(()(()()()())(())((()))()(())(()())()()())(()()(()()()))(()())((((()()))((()))((()))))(()()(())()()()())(()(()(())))()((()(())))(())((())()()()()(...

output:

97522

result:

ok single line: '97522'

Test #171:

score: 0
Accepted
time: 244ms
memory: 81352kb

input:

99996 1
((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((...

output:

1344330

result:

ok single line: '1344330'

Test #172:

score: 0
Accepted
time: 333ms
memory: 79888kb

input:

100000 5
(((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((...

output:

852358

result:

ok single line: '852358'

Test #173:

score: 0
Accepted
time: 427ms
memory: 80848kb

input:

100000 50
(((((((((((()()(()()()))))(((()((())()())((())()))((())((())())))((())(((())()(()))())((())(()()))))))(())))((((()())((((()(())))(())))))(((((()())(())(()))(()(())())((((((()(())((())))()())))))))()(()))))))((((((((((((()((()))(()()(())))((()())(())))(())(()(((()()()))((()(())((())()))())(...

output:

220152

result:

ok single line: '220152'

Test #174:

score: 0
Accepted
time: 446ms
memory: 81804kb

input:

99995 300
((((()(((((((())(()))))((()((((())((((()((((((((((((((()(()))((((())))))))))))((()())(()))))))))))))))))))(((((((((((((((((((((((((((())))(())))((())((((((()()))(()))((((((())(()(((()))))))(((((((((())))(((((((()())()))())))(((()())((((((((()))())())))(()()))()))(())))))))((((((())))(((()(...

output:

40670

result:

ok single line: '40670'

Test #175:

score: 0
Accepted
time: 466ms
memory: 81872kb

input:

100000 600
((((((()))())((((((()())((()())(()))(((())()())()()))(((((((()()(())))((()((())(()())()))))))))))(((((()(()(())))()(((())()(()))((()()))))((()((()()))(((())(()()))))(((((())(()(()))((())()()))(()))((()()())((())(())(()))))(()))()))))))))(((()(())((())()()))()(()))((((((((()((()())()(()))(...

output:

32350

result:

ok single line: '32350'

Test #176:

score: 0
Accepted
time: 830ms
memory: 78228kb

input:

100000 2001
(((())())(()())()()()()(()()))(())(())(())(()())(()()())(())((()()))(())(()())(())((()())(()))()(()()())(())(()()(())(())()(()))()(()(()))()(()(()))((())(()()))(())(()()(())())(()()(()(()))(()()))(())()(()(())()())(()(()())()()()(())()())()(()()(())(()()()()()(())))(()(()))()(())(()()())...

output:

84392

result:

ok single line: '84392'

Test #177:

score: 0
Accepted
time: 454ms
memory: 80420kb

input:

100000 4001
((()())(())(())(()))(()()()(())()())(())(()())(((())()))(()((()))())()(()(()))(()(())()())(()((())(()))()())(())(())((())(())()(())()()((()()()))())()()()(())(()()()(())()(()())()(()))(()())((())()(())()(())((()()))(()())()()(()()))(()(()))((()))(()()()())(())((()))()(())()()()((()))((()...

output:

22628

result:

ok single line: '22628'

Test #178:

score: 0
Accepted
time: 375ms
memory: 81608kb

input:

99990 7777
)()))))(()))((())))((((()())((()()())))(())()((()())((()(()))((((())())((((()()()))))))()())))())))))(()())()())()(())()()()()))))))()(()((()()())))())(())()()((()()))((()((()(((()()))())()())))()())())()))(()()))()))()(()((()()()(()(()())()()()(())()))))))))()((()(()(()())()(()(((())()))...

output:

15339

result:

ok single line: '15339'

Test #179:

score: 0
Accepted
time: 1971ms
memory: 80200kb

input:

100000 50000
()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()(...

output:

1

result:

ok single line: '1'

Test #180:

score: 0
Accepted
time: 225ms
memory: 77848kb

input:

100000 100000
()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()...

output:

0

result:

ok single line: '0'

Subtask #10:

score: 1
Accepted

Test #181:

score: 1
Accepted
time: 299ms
memory: 77840kb

input:

100000 256
((((())()(())())(((()))()((())()(()(())))))(((()(()))(((()))()()()()))()((((()))(())((()))))((()))(()((()()()()())()())(())(())()()(()()))(((()()))))())((((()))()((())()(()(())((()))))()((()()()()((()))))()(()(()()(()(())(()))))(())(((())))((()()((()))()())()())()((()())))()(((((()()))))(...

output:

107402

result:

ok single line: '107402'

Test #182:

score: 0
Accepted
time: 345ms
memory: 78232kb

input:

99728 4096
((((((()((()))))()))((((((()()(()())))(())()(()))()(()()()()()((()()()))()(((()))()(()))((()))(()()())()()))())(((()))(())((()((())()(()()))()))()(((())(())(()))(())((()(()(())()())()))((()())()())(()())(((()()()(())))))())(((())()())((()())())((()((()()())()()))()((()))))(()(((()((()))))...

output:

41913

result:

ok single line: '41913'

Test #183:

score: 0
Accepted
time: 228ms
memory: 81020kb

input:

100000 2
(((((()(())((()))))(()(((())((()))(()()))()()()))()()(((()())(((())()()))()(()))()(()))(())(((()))))((()((())(()()(())))(((()))()()((()))))()(((()())(())())()())(((()))()()((()(())(((())()())))())()(()(())(((()))()(())(())(()))(()()())())())((()(()((())())))))))((((())((()()((()())))()((())...

output:

125299

result:

ok single line: '125299'

Test #184:

score: 0
Accepted
time: 273ms
memory: 78436kb

input:

100000 34
(()((()()(())((()))(((()()))))()()(())()(((())((())))())(()(()(())())))()((()(()())()()()()))((()()(()(()()))(((())(())())())(()()()())))((()((()(())()(()))()(())))()()((()()(()()))(())((())())(())((())((())()))()((()))()()(((()())))()()()()((()()()(()())())))((()()())()(()()()())(()()()()...

output:

129202

result:

ok single line: '129202'

Test #185:

score: 0
Accepted
time: 288ms
memory: 80324kb

input:

100000 610
((((()(((()())()())())()()((()()))()())((((()))(()()(()))())(())(()()()(()))()(())))(((((()())()()()())())())(((()))()(()())()(((()))())()))((((((())()())())()()())()(()))((()(()()())((()()))())(()()()))()(((()())))()())()((((()))(()()())((())(())()((())))((()()())((()(()()))()(())()()))(...

output:

89431

result:

ok single line: '89431'

Test #186:

score: 0
Accepted
time: 621ms
memory: 80436kb

input:

100000 10946
(((()(()))())((()))(()())((()))(())()(()())((())(()()())()())(((()))(()))(()())()(()))(((())()())()(()())()(((()))))(((()())()(())())(()()((())(())()()()())((()()))())(()())()()(((())))()(()(())()))()(()(()(()(())))())(()(()((()()())))(()())()()(()()))(((())()()(())))(((()))())(((()()))...

output:

22048

result:

ok single line: '22048'

Test #187:

score: 0
Accepted
time: 355ms
memory: 81140kb

input:

99999 1001
(((())((()()())(()))))((())())))()()()((()(((()((()))(())))()(()(()))()((())(())))(()((()()))))()(((())))()))())((()()()))()()(())()())())(((()(())())(()())(()()(()()()()((()()()())(((()))((())()(()))(())()(())())(())))()()))()()())()))(())))))))()(())(((()))((())(()))))(((()(())))((())((...

output:

58142

result:

ok single line: '58142'

Test #188:

score: 0
Accepted
time: 202ms
memory: 79832kb

input:

100000 100000
)(()()(((())((())(())((()()((()((()))))(()(()()()()()()(()(()((()()((())((((())(()()(()((())()()(())((()(()((())((()(()((())((((())()()))())()))()((()()))))))(()()())())()())))()))((())())(()(((())))()()()()(((()((((()((()))()(())())))()()())((()())())((())())()))())())())()((((()))))(...

output:

0

result:

ok single line: '0'

Test #189:

score: 0
Accepted
time: 255ms
memory: 81012kb

input:

99997 101
(((((()()()))()()(())(()()()())()(()())()(()()())()((())(()))((())()(())()(())())(())()(()()())()(())(()())(()())((()))(((())()))(((())))(())(((())())))((()(())()(())()(())()()(())())(())(()()()(())()())(()(())))(())((())((())()((())())(()())()))((()(())))((()()())()()(())(())()(((())))(()...

output:

226645

result:

ok single line: '226645'

Test #190:

score: 0
Accepted
time: 337ms
memory: 80472kb

input:

99993 101
()()()()()(())()(()())()()((()()()())())(()()(()))(())()()()()(()()(()))(())()(())(()()())(()()(()())(()))((())())(()())(()(()()))(()(()(((()((()))()))))()())()(()()()()()()()()()()()()()()()()()()()()()(())()()()()()()()()()(())()()(())(())(())(())(())(())()()(()())()(())()((((())))())()(...

output:

628404

result:

ok single line: '628404'

Test #191:

score: 0
Accepted
time: 296ms
memory: 77960kb

input:

100000 500
()()(()((())()()()))((()))((())(())(())())((())()((())))((()))(()())(()()()()()()())((()())(()))(((((())))(()(())()()()()()()())()(())((()()()))(((())))(((())))((()))()(())()(())(()()())(((()))(()))()(()())()()(())()()()()()()()()()))((()())(()()()()())(())(()()()())(())(()()()()()()()())...

output:

187233

result:

ok single line: '187233'

Test #192:

score: 0
Accepted
time: 448ms
memory: 78960kb

input:

99992 500
(()(()((()))()(())((())()(()))()()(()())()(())((()))()(()()))(()()()()(())(()()()))(()()()()())((())()()()()()()(())()(())(())(()))(()())(()(())(()(()())()())()(())(()()()())()((()))(())()(()(()))()((()()))(())(())()()()()()(())((()()))()(()()())(()())(())(((())))(())(()))(((()))()()())(((...

output:

339045

result:

ok single line: '339045'

Test #193:

score: 0
Accepted
time: 311ms
memory: 80384kb

input:

100000 1001
(((((()()()(())()(())()()()()()()()())((()()()()()))))((())()()())(()()()()()(())()()()(()())(())())(()()()()()())((()))(((()))(())(())((()())())()(())(()()))((()()())()()()(())()()((()))())((())(())(()())((())())(())()(())())(((()()()(())()()))((())()()()()))(((())()()()()(())()()()())(...

output:

132487

result:

ok single line: '132487'

Test #194:

score: 0
Accepted
time: 441ms
memory: 79868kb

input:

100000 1001
()(())(()(())())(()()()()()()())(()(()))((())(()((()())())()(()()((()))()(())((())))))((())(((()))()(())())(())(()()()()()()()()()())(())()(())()(())(())()()(())()(()())(())()()()()()()()())(()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()(())()()()()(()())()()(...

output:

229454

result:

ok single line: '229454'

Test #195:

score: 0
Accepted
time: 386ms
memory: 80848kb

input:

100000 3001
((()(())()()(()(())())()((())())()()(()()()))(()(()())(())()()(())()()(())(())()()()()()((()))()()()()(())(())()()(()())()())(()(())()()()()()()()()()()()()())(()()()()()(())()(())(()())()()((()))()((()()()()))((()))((()))(()())(()())()(())(())((())(()()))()(())()(((())))(()())(()(())(()...

output:

82308

result:

ok single line: '82308'

Test #196:

score: 0
Accepted
time: 523ms
memory: 80444kb

input:

100000 3001
(()()()()()()()()()()()()()()()()()()()()()()()()(())()()()(())(())()()()()()()()(())(())()()()(((()))())(()())(())()()()()(())()()()()(())()((()))(())(())((()))()(())((()))(())(((())))()()()(()())(()()()())()(()()())(())(())(()())(())()(())(())((()))(((())))((()()()()()()()()())())(((()...

output:

115349

result:

ok single line: '115349'

Test #197:

score: 0
Accepted
time: 350ms
memory: 79292kb

input:

99993 2
((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((...

output:

6013753

result:

ok single line: '6013753'

Test #198:

score: 0
Accepted
time: 296ms
memory: 79452kb

input:

99991 10
(()())(()())(()()())(()())((()())())(())(()())()()()((()())())(())(())(()())(()()(()())()(()())(()(()))(())())(((()))()()(()))(()())(())()((())(())(()())(())(())())(((())))()(())(())(()())(()()())(()((())))((()()))()()(())()()(()()())(((())))()(()()()(()))((()))(()()())(((()))()()())()()()(...

output:

89461

result:

ok single line: '89461'

Test #199:

score: 0
Accepted
time: 383ms
memory: 81504kb

input:

99998 100
(()(())()()())(()(()))(())(((())))()()((()))(()()())(()()(())()()()(())())(())(()(())()(())()(())()((()))(())())((())()()()()()(()()))((()()()))((()()()()()))((()())()())()((()))()()()((()))(())(()()()()(())((())))((()))(()()(())(())())((()))(()())(())(((())()()))()()((()))((()())()()()(()...

output:

53969

result:

ok single line: '53969'

Test #200:

score: 0
Accepted
time: 418ms
memory: 81276kb

input:

99990 500
((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((...

output:

49676

result:

ok single line: '49676'

Test #201:

score: 0
Accepted
time: 380ms
memory: 80452kb

input:

100000 1000
((((((((((((())(((())(((()))())))(()(()())((((((()))((())())(()(()))))))))((((())(((((()))(()))(((())(((())))))(()(()))))(()(())()))))(((((((()))(((())()))(()))((())()())(()())))(()()()))((((()(()))(())(())))()(())))))))(((((((((()(()((())())))(((()()()))(((())((())(((()()()))))((()())((...

output:

45154

result:

ok single line: '45154'

Test #202:

score: 0
Accepted
time: 708ms
memory: 78492kb

input:

100000 3000
((((((((((((((((())((()((()(()))())))))((((((((((())((((((((((((((((((()(()))(()))(((())(((((())((()((())((())(((()(((((()))(()(())))((()())())))))))))))))))(((()())())))))))((((()(()())))(((((((((())((())))((((((()((()))))(()))))((()(((()(((((()())))))))))(())))))((((())(((()))())))(()(...

output:

53085

result:

ok single line: '53085'

Test #203:

score: 0
Accepted
time: 448ms
memory: 80588kb

input:

100000 5555
((((((((((())))())((((())(((((()())))())))))))(())))((((())((()((()))))))(((()())(((((((((()()))))(((((()())(()))(((((((())))))(()))((((((())(((())())(()())))()))((((())((()()))))((((())(()))))))))))))))(((()()))))(((((()(((()))((((((((((((()((((())))((()())))))))))))()))))))))((())((()(...

output:

24920

result:

ok single line: '24920'

Test #204:

score: 0
Accepted
time: 452ms
memory: 80396kb

input:

99997 12000
()()()(())(())(()()())(()())(()())()(((())()))()()((()()))(()(())((())()))(())()(())((()))(()(())(())())(()(()()))(()(()()))((())())((())(())())((()()())())()(()((()))()(()())())(()()()()()())(())(()()(()))(()())()(())()(()()())(()(()))(()()(()))()((()())(()))(())(()()()())(()(()()))((()...

output:

8147

result:

ok single line: '8147'

Test #205:

score: 0
Accepted
time: 216ms
memory: 80256kb

input:

100000 50001
()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()(...

output:

0

result:

ok single line: '0'

Test #206:

score: 0
Accepted
time: 209ms
memory: 80888kb

input:

100000 1
()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()(...

output:

1250025000

result:

ok single line: '1250025000'

Extra Test:

score: 0
Extra Test Passed