QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#587919#8806. Summer Drivingzhouhuanyi25 ✓2862ms145016kbC++173.9kb2024-09-24 22:37:372024-09-24 22:37:38

Judging History

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

  • [2024-09-24 22:37:38]
  • 评测
  • 测评结果:25
  • 用时:2862ms
  • 内存:145016kb
  • [2024-09-24 22:37:37]
  • 提交

answer

#include<iostream>
#include<cstdio>
#include<vector>
#define N 300000
using namespace std;
const int inf=(int)(1e9);
int read()
{
	char c=0;
	int sum=0;
	while (c<'0'||c>'9') c=getchar();
	while ('0'<=c&&c<='9') sum=sum*10+c-'0',c=getchar();
	return sum;
}
int n,sr,A,B,d,lengs,leng[N+1],sleng[N+1],lg[N+1],depth[N+1],minn[N+1],dfn[N+1],sz[N+1],sfa[N+1],tong[N+1],length,dp[N+1];
bool vis[N+1],vst[N+1];
vector<int>E[N+1];
vector<int>ES[N+1];
vector<int>p[N+1];
void add(int x,int y)
{
	E[x].push_back(y),E[y].push_back(x);
	return;
}
void dfs(int x)
{
	dfn[x]=++lengs,sz[x]=1,tong[++length]=x;
	if (length>A) sfa[x]=tong[length-A+1],p[tong[length-A]].push_back(x);
	for (int i=0;i<E[x].size();++i)
		if (!dfn[E[x][i]])
			ES[x].push_back(E[x][i]),depth[E[x][i]]=depth[x]+1,dfs(E[x][i]),sz[x]+=sz[E[x][i]];
	--length;
	return;
}
struct seg
{
	struct node
	{
		int l,r,lazy;
	};
	node tree[(N<<2)+1];
	void build(int k,int l,int r)
	{
		tree[k].l=l,tree[k].r=r,tree[k].lazy=inf;
		if (l==r) return;
		int mid=(l+r)>>1;
		build(k<<1,l,mid),build(k<<1|1,mid+1,r);
		return;
	}
	void add(int k,int l,int r,int d)
	{
		if (tree[k].l==l&&tree[k].r==r)
		{
			tree[k].lazy=min(tree[k].lazy,d);
			return;
		}
		int mid=(tree[k].l+tree[k].r)>>1;
		if (r<=mid) add(k<<1,l,r,d);
		else if (l>=mid+1) add(k<<1|1,l,r,d);
		else add(k<<1,l,mid,d),add(k<<1|1,mid+1,r,d);
		return;
	}
	int query(int k,int x)
	{
		if (tree[k].l==tree[k].r) return tree[k].lazy;
		int mid=(tree[k].l+tree[k].r)>>1;
		if (x<=mid) return min(tree[k].lazy,query(k<<1,x));
		else return min(tree[k].lazy,query(k<<1|1,x));
	}
};
seg T;
bool query(int x,int y)
{
	return !(leng[y]<=B||T.query(1,dfn[y])+depth[y]<=B);
}
void dfs2(int x)
{
	int cnt=0,cnt2=0,sx,sminn=inf,rt=0;
	leng[x]=sleng[x]=inf;
	for (int i=0;i<ES[x].size();++i)
	{
		dfs2(ES[x][i]),sleng[x]=min(sleng[x],sleng[ES[x][i]]+1);
		if (leng[ES[x][i]]+1<leng[x]) sminn=leng[x],leng[x]=leng[ES[x][i]]+1,rt=ES[x][i];
		else sminn=min(sminn,leng[ES[x][i]]+1);
	}
	if (x<d) sleng[x]=0;
	if (p[x].empty())
	{
		dp[x]=sleng[x]>B;
		if (sleng[x]<=B)
		{
			for (int i=0;i<ES[x].size();++i) T.add(1,dfn[ES[x][i]],dfn[ES[x][i]]+sz[ES[x][i]]-1,-depth[x]);
		}
	}
	else
	{
		dp[x]=sx=0;
		for (int i=0;i<p[x].size();++i)
		{
			if (query(x,p[x][i])) dp[x]=vis[sfa[p[x][i]]]=1;
			vst[sfa[p[x][i]]]=1;
		}
		for (int i=0;i<ES[x].size();++i) cnt+=vst[ES[x][i]],cnt2+=vis[ES[x][i]];
		if (cnt==1)
		{
			if (!cnt2)
			{
				for (int i=0;i<ES[x].size();++i)
					if (!vst[ES[x][i]])
						T.add(1,dfn[ES[x][i]],dfn[ES[x][i]]+sz[ES[x][i]]-1,-depth[x]);
			}
			int res=inf;
			for (int i=0;i<ES[x].size();++i)
				if (!vst[ES[x][i]])
					res=min(res,sleng[ES[x][i]]+1);
			if (x<d||res<=B)
			{
				for (int i=0;i<ES[x].size();++i)
					if (vst[ES[x][i]])
						T.add(1,dfn[ES[x][i]],dfn[ES[x][i]]+sz[ES[x][i]]-1,-depth[x]);
			}
		}
		else
		{
			if (!cnt2)
			{
				for (int i=0;i<ES[x].size();++i) T.add(1,dfn[ES[x][i]],dfn[ES[x][i]]+sz[ES[x][i]]-1,-depth[x]);
			}
			if (cnt2==1)
			{
				for (int i=0;i<ES[x].size();++i)
					if (vis[ES[x][i]])
						T.add(1,dfn[ES[x][i]],dfn[ES[x][i]]+sz[ES[x][i]]-1,-depth[x]);
			}
		}
	}
	for (int i=0;i<ES[x].size();++i)
	{
		if (ES[x][i]==rt) T.add(1,dfn[ES[x][i]],dfn[ES[x][i]]+sz[ES[x][i]]-1,sminn-depth[x]);
		else T.add(1,dfn[ES[x][i]],dfn[ES[x][i]]+sz[ES[x][i]]-1,leng[x]-depth[x]);
	}
	if (!dp[x]) leng[x]=0;
	return;
}
bool check(int x)
{
	for (int i=1;i<=n;++i) minn[i]=inf,vis[i]=vst[i]=0;
	d=x,T.build(1,1,n),dfs2(sr);
	return dp[sr];
}
int main()
{
	int x,y,res=0;
	for (int i=2;i<=N;++i) lg[i]=lg[i>>1]+1;
	n=read(),sr=read(),A=read(),B=read();
	if (A<=B)
	{
		puts("1");
		return 0;
	}
	for (int i=1;i<=n-1;++i) x=read(),y=read(),add(x,y);
	depth[sr]=1,dfs(sr);
	for (int i=lg[n];i>=0;--i)
		if (res+(1<<i)<=n&&check(res+(1<<i)))
			res+=(1<<i);
	printf("%d\n",res);
	return 0;
}

详细

Subtask #1:

score: 1
Accepted

Test #1:

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

input:

300000 110732 1 1
54285 169439
18968 45543
130988 134682
162292 70081
212010 121474
128140 292466
209394 38279
91706 225569
67647 188578
265505 84279
161782 137098
27472 221980
284973 79104
230628 268631
69945 205947
153720 168119
230161 32244
138981 44376
165008 136947
125742 123375
209131 122038
8...

output:

1

result:

ok single line: '1'

Test #2:

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

input:

300000 123141 300000 300000
35459 173656
6934 241069
183095 87288
269195 16957
19492 242321
24470 81747
25697 172188
171424 220229
160473 69937
172168 99268
220664 39397
8212 2407
46718 94855
279515 295195
205222 167038
185958 111515
172553 45818
141322 214355
61335 64490
183502 105408
234540 245525...

output:

1

result:

ok single line: '1'

Test #3:

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

input:

298765 30225 2 3
265195 252069
113697 255482
227617 218688
279488 136408
179394 139291
86777 211320
255097 13136
68860 173342
178971 175020
278041 278319
285893 289677
194438 44163
56223 283058
110392 123602
20729 89517
152134 176747
121481 243463
297305 139297
244189 117068
181785 39468
154302 1860...

output:

1

result:

ok single line: '1'

Test #4:

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

input:

299987 224030 2 2
177674 20066
211112 287348
150440 136779
131528 209570
208840 36580
3395 152219
89118 44403
120439 274280
267578 80200
17796 257578
229408 211795
122773 147368
139779 842
94469 299092
211457 29057
9040 117449
216268 88141
40844 98163
183412 221031
230933 237086
147633 135982
282224...

output:

1

result:

ok single line: '1'

Test #5:

score: 1
Accepted
time: 3ms
memory: 28960kb

input:

2 1 1 2
2 1

output:

1

result:

ok single line: '1'

Subtask #2:

score: 4
Accepted

Test #6:

score: 4
Accepted
time: 2037ms
memory: 144964kb

input:

300000 226344 300 9
32176 183340
249597 14851
145160 92372
30564 242505
1140 169463
279867 14442
266653 32911
168819 26009
138049 133460
5327 103921
262703 112512
204338 84304
98144 9089
98632 238236
79093 101104
50327 237759
61236 275195
241153 116369
86842 272794
25675 121176
110170 225753
199931 ...

output:

1

result:

ok single line: '1'

Test #7:

score: 4
Accepted
time: 2379ms
memory: 145000kb

input:

299999 92073 2999 11
262905 260944
140896 162257
22797 193473
248112 247445
217760 68693
156294 167586
42291 233355
280566 247233
171395 239795
126564 179464
208554 185755
201665 156263
74786 85307
116366 163760
57326 143227
243541 149484
287792 283934
293052 265098
294245 296048
14582 36967
202999 ...

output:

245417

result:

ok single line: '245417'

Test #8:

score: 4
Accepted
time: 850ms
memory: 144832kb

input:

298989 2 303 302
291949 291950
71254 71253
32103 32104
194290 194289
155694 155693
178665 178664
278674 278675
63793 63794
280321 280320
209075 209074
141282 141283
298423 298424
145067 145068
115803 115802
88974 88975
199766 199767
73340 73339
106776 106777
20786 20787
57085 57086
51034 51035
88299...

output:

3

result:

ok single line: '3'

Test #9:

score: 4
Accepted
time: 858ms
memory: 143756kb

input:

298989 2 30001 30000
227255 227254
149938 149939
159449 159448
6194 6193
239990 239989
95657 95658
280931 280932
65015 65014
221854 221855
65661 65662
36912 36911
184778 184779
74520 74521
217578 217577
234314 234315
266126 266125
96469 96470
158616 158615
12920 12919
207237 207236
72167 72166
20226...

output:

3

result:

ok single line: '3'

Test #10:

score: 4
Accepted
time: 2185ms
memory: 140320kb

input:

289898 68514 42345 35
247935 196903
238347 177303
95489 261552
14797 183922
175677 109839
85928 186661
124668 74629
172100 214045
217602 46031
73083 257282
268102 276634
94408 248387
202292 208128
250155 61752
240022 256152
281659 223534
18580 272515
36 46287
247306 163047
90365 36426
241702 92561
6...

output:

289093

result:

ok single line: '289093'

Test #11:

score: 4
Accepted
time: 2338ms
memory: 135256kb

input:

298765 191954 298765 29876
158145 67683
17628 136757
153101 176403
952 52270
139224 227583
289601 4565
200272 19860
139873 277812
229381 251631
55892 22383
102701 27390
252623 286705
27875 223439
180032 271744
28933 296138
97573 294210
108654 126487
31902 223049
180647 68619
9869 147781
255029 23743...

output:

14

result:

ok single line: '14'

Test #12:

score: 4
Accepted
time: 2131ms
memory: 135304kb

input:

298765 33562 298764 29876
110929 69221
276688 201887
264415 65460
166102 272335
248892 186840
206217 296235
283621 86931
238780 122705
200845 137749
30491 75339
159784 24393
240809 7087
193364 245493
287660 2903
214506 285716
181040 49286
37334 6088
276968 3658
52998 220919
289624 131115
274518 6204...

output:

1

result:

ok single line: '1'

Test #13:

score: 4
Accepted
time: 2433ms
memory: 140340kb

input:

300000 1 150000 149999
139488 266956
75499 115106
197111 266846
75931 86565
243441 135464
194765 22597
286803 214206
236086 46031
227314 88097
71817 83460
61640 293618
211868 156133
1709 4302
274196 125332
204068 41865
21111 98062
21173 99704
125957 168343
251218 116725
230029 252274
195016 31148
11...

output:

2

result:

ok single line: '2'

Test #14:

score: 4
Accepted
time: 2ms
memory: 27408kb

input:

291234 289232 2 291234
56299 134830
146619 165289
230113 123453
264835 93343
140869 286284
36462 175435
204256 11688
180367 256764
193570 229161
64489 177626
22842 55205
118191 162946
194148 194973
96663 95195
157427 215291
227692 47027
219226 31692
198993 60149
39787 77693
127485 148991
216628 1999...

output:

1

result:

ok single line: '1'

Test #15:

score: 4
Accepted
time: 2224ms
memory: 144972kb

input:

300000 5 12 1
104098 71288
155929 237155
194885 110614
288708 131509
260955 5677
152237 222368
152814 51702
131846 277511
32293 143328
95240 144359
158319 206926
95983 78186
223795 104895
179277 77519
247023 263601
141002 229603
168689 271469
125125 273621
143596 40101
112050 30987
268143 178476
249...

output:

78

result:

ok single line: '78'

Test #16:

score: 4
Accepted
time: 2639ms
memory: 145016kb

input:

300000 18710 912 1
193195 34459
260311 292739
133324 164168
66161 138261
49021 172781
285599 274251
46667 124835
249174 273094
57936 232787
100855 137993
117133 208961
204288 165919
118007 11717
209150 1905
122223 56208
170266 110094
203532 80994
281756 254059
648 18645
264367 270340
276680 247873
2...

output:

246042

result:

ok single line: '246042'

Test #17:

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

input:

2 2 1 1
2 1

output:

1

result:

ok single line: '1'

Subtask #3:

score: 5
Accepted

Test #18:

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

input:

300 42 3 2
114 268
132 105
187 17
191 127
14 62
162 126
39 143
72 159
199 184
295 138
71 277
293 103
288 54
231 196
57 220
110 117
38 136
295 258
41 76
291 8
59 131
161 278
244 233
81 76
12 236
21 240
228 262
255 159
236 60
277 33
29 123
170 290
89 154
220 139
193 81
31 53
163 77
148 274
181 76
15 2...

output:

83

result:

ok single line: '83'

Test #19:

score: 5
Accepted
time: 3ms
memory: 37776kb

input:

300 178 3 2
277 106
123 105
235 290
273 34
300 180
43 55
239 74
19 138
110 201
295 18
207 97
238 177
114 24
195 219
154 186
151 294
143 291
47 293
33 99
2 46
101 39
109 240
15 256
43 121
205 261
267 257
81 167
82 23
300 182
13 46
195 221
163 17
109 93
144 23
110 17
153 129
91 243
281 74
135 72
145 1...

output:

4

result:

ok single line: '4'

Test #20:

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

input:

300 130 4 2
74 70
137 178
142 56
106 137
154 190
162 96
218 173
261 37
206 72
136 93
293 159
145 94
221 97
76 189
149 282
79 62
258 37
35 20
215 8
143 207
216 38
262 241
37 68
221 258
156 8
213 50
180 238
132 300
256 136
79 281
179 128
177 202
20 229
43 12
290 230
26 105
135 20
146 84
10 184
254 27
...

output:

126

result:

ok single line: '126'

Test #21:

score: 5
Accepted
time: 9ms
memory: 33668kb

input:

300 49 4 2
199 123
264 232
60 265
215 2
226 189
160 11
200 217
194 175
295 203
20 165
203 63
132 127
42 259
170 293
230 269
20 166
141 96
149 210
246 122
5 185
90 156
297 21
300 78
24 94
139 154
268 258
53 15
267 67
221 248
298 154
136 254
192 234
142 170
56 217
90 25
228 216
216 186
61 90
14 221
27...

output:

26

result:

ok single line: '26'

Test #22:

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

input:

300 250 3 1
91 120
269 191
244 235
202 92
3 146
190 210
175 190
243 20
280 75
81 296
179 85
278 283
123 134
98 35
29 65
219 268
242 135
143 238
274 127
99 243
141 231
285 68
269 76
15 61
179 157
165 139
52 49
247 50
151 50
262 161
132 270
224 15
228 144
56 100
293 35
80 98
188 65
263 43
267 234
243 ...

output:

149

result:

ok single line: '149'

Test #23:

score: 5
Accepted
time: 3ms
memory: 33280kb

input:

300 205 3 1
43 211
182 106
31 159
33 141
50 122
33 108
65 275
218 285
263 71
39 211
41 91
264 151
211 286
298 228
84 96
292 176
78 239
107 28
247 265
132 182
225 257
70 58
165 61
162 35
221 23
168 234
279 130
111 261
157 34
61 47
299 97
129 233
247 245
280 60
137 252
241 248
275 91
251 178
288 181
2...

output:

45

result:

ok single line: '45'

Test #24:

score: 5
Accepted
time: 6ms
memory: 33308kb

input:

300 151 10 4
106 66
88 78
279 12
92 142
298 168
98 117
8 108
104 192
50 216
227 176
77 297
149 195
94 11
72 69
235 267
261 11
131 35
115 146
140 73
132 251
185 145
29 193
52 90
287 39
261 300
24 206
223 59
270 35
225 35
32 95
184 244
52 164
276 118
220 268
249 251
187 217
288 71
297 34
171 198
178 2...

output:

2

result:

ok single line: '2'

Test #25:

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

input:

300 203 300 10
2 182
179 26
120 101
281 271
236 75
260 242
121 271
32 66
277 14
98 47
152 83
231 39
145 93
23 127
203 76
76 252
65 31
33 62
60 201
154 147
42 83
13 203
203 2
265 292
96 30
23 85
23 64
220 30
189 277
296 44
63 110
107 202
61 93
134 286
65 122
133 241
152 142
97 84
209 202
267 47
255 8...

output:

1

result:

ok single line: '1'

Test #26:

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

input:

123 33 3 3
63 85
6 68
37 58
78 86
111 69
36 110
115 56
41 63
112 15
99 61
55 96
123 88
45 16
37 54
95 41
54 24
26 108
40 83
60 36
83 25
71 19
83 7
56 53
123 30
46 93
20 104
99 23
52 84
49 31
110 109
53 97
33 18
90 94
80 3
82 58
108 100
97 14
32 99
8 60
54 119
101 35
23 48
42 8
54 5
10 73
35 18
113 1...

output:

1

result:

ok single line: '1'

Test #27:

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

input:

231 165 100 50
114 20
131 183
182 20
31 36
210 93
13 188
175 5
154 63
48 24
205 90
146 153
129 186
156 106
27 82
49 198
89 42
111 146
203 142
87 20
98 188
65 63
196 118
15 102
137 75
101 67
143 160
130 197
186 209
50 172
47 224
4 220
59 41
148 16
32 182
131 90
87 225
177 77
149 30
93 33
51 106
185 1...

output:

1

result:

ok single line: '1'

Test #28:

score: 5
Accepted
time: 6ms
memory: 33768kb

input:

300 11 30 16
90 227
152 287
67 39
165 50
242 139
278 177
51 148
129 214
94 124
37 201
53 254
84 202
267 183
95 171
251 32
45 170
161 275
272 268
209 49
34 272
106 75
223 285
42 72
130 138
91 263
230 158
31 59
80 209
262 45
136 131
162 121
297 287
32 207
228 171
112 58
273 70
173 176
169 34
155 54
37...

output:

29

result:

ok single line: '29'

Subtask #4:

score: 3
Accepted

Dependency #3:

100%
Accepted

Test #29:

score: 3
Accepted
time: 12ms
memory: 33916kb

input:

3000 63 3 2
2155 250
1688 831
522 631
1755 1764
55 2251
2127 1756
1135 387
600 1437
182 1020
1802 1849
399 2974
1809 574
402 2032
2147 2561
1186 830
829 2804
1086 1237
82 414
892 375
107 2688
1857 1972
1162 324
1758 1763
1255 918
1553 908
849 1670
132 2126
2503 861
1906 1836
305 1063
922 6
2068 1435...

output:

878

result:

ok single line: '878'

Test #30:

score: 3
Accepted
time: 8ms
memory: 34008kb

input:

3000 528 3 2
2749 507
78 1098
1114 832
608 2375
2044 319
1549 1782
2146 1096
2728 817
1542 394
1362 2837
2714 2424
141 1693
190 2792
424 2422
2891 1525
1796 1932
2241 1427
790 1721
1044 1909
1240 2843
2964 1850
1587 2274
1249 1126
1 1689
2558 994
2911 2148
1160 1580
2530 2574
1402 1723
961 1518
2520...

output:

4

result:

ok single line: '4'

Test #31:

score: 3
Accepted
time: 7ms
memory: 33996kb

input:

3000 458 4 2
943 1128
2440 1236
1649 2508
2922 420
1540 1811
1710 566
1260 668
2124 858
78 373
551 1017
1611 1744
536 104
1999 2934
2391 354
765 675
301 316
301 1613
2919 2533
2604 301
443 1540
2287 1580
397 1970
1925 1439
2478 2414
2189 1169
521 2182
1700 163
2575 334
477 1728
581 332
45 2170
1485 ...

output:

1318

result:

ok single line: '1318'

Test #32:

score: 3
Accepted
time: 8ms
memory: 33956kb

input:

3000 2841 4 2
1502 2819
421 217
1423 1914
1968 2313
1207 544
2752 1319
2459 1345
2192 2421
1320 1368
2936 971
637 1964
1328 1901
1568 1868
1544 1357
308 2198
1883 2064
978 685
336 2521
2173 1402
1288 1166
1514 684
2369 771
1339 738
1446 2786
1060 1543
375 1947
1756 1912
1397 288
609 2230
1015 1187
2...

output:

174

result:

ok single line: '174'

Test #33:

score: 3
Accepted
time: 15ms
memory: 33252kb

input:

3000 2364 3 1
1809 381
674 1824
2549 125
1469 1465
1144 2486
1177 862
2559 1927
1211 36
630 739
2926 1555
1169 2479
2984 2956
1669 1009
398 2796
469 991
1886 2628
2770 2725
1216 1394
703 76
2016 1162
722 1840
78 2793
326 1057
918 1887
1291 2478
1160 1312
2990 801
2969 212
1727 2594
1727 1862
2541 62...

output:

2143

result:

ok single line: '2143'

Test #34:

score: 3
Accepted
time: 12ms
memory: 40232kb

input:

3000 2398 3 1
1889 2450
812 2135
1493 638
1854 1137
1252 648
166 265
1679 1601
1655 2909
1715 1976
1546 1236
2328 2749
983 332
515 133
1557 2018
2253 2065
756 358
2707 1881
706 944
2950 1419
359 2541
1612 628
2622 2164
2567 1293
1984 336
2502 2151
2056 780
59 374
1830 1407
102 1355
2783 1881
1798 15...

output:

149

result:

ok single line: '149'

Test #35:

score: 3
Accepted
time: 11ms
memory: 33484kb

input:

3000 1828 10 4
2915 1223
1673 262
2847 1682
2587 2184
1017 2101
847 948
882 1914
2341 737
1979 1325
1760 1181
2399 742
1265 589
2879 946
1350 1387
2257 460
2101 1349
1985 1386
2132 1234
2582 2928
1454 1911
2819 2291
2016 1584
2738 1284
1523 1881
2630 1557
2830 2492
2967 509
195 2535
2119 1901
1356 2...

output:

82

result:

ok single line: '82'

Test #36:

score: 3
Accepted
time: 8ms
memory: 33904kb

input:

3000 796 3000 10
1508 2938
1186 502
322 2126
1138 1034
1829 1180
897 2854
2944 1095
139 1107
934 599
2851 2720
2328 237
910 796
2326 2751
2034 1301
40 2974
1657 52
684 1644
1610 1646
273 2528
290 2608
2701 2094
1070 837
1574 834
1765 990
2457 1107
2239 449
129 2697
2871 1560
352 2310
1795 2670
673 9...

output:

1

result:

ok single line: '1'

Test #37:

score: 3
Accepted
time: 4ms
memory: 28772kb

input:

1234 899 3 3
232 1227
294 768
507 1064
255 524
116 946
1017 462
850 518
158 912
1190 127
451 1172
671 1119
279 853
706 634
144 243
1160 103
921 917
1078 748
320 1095
695 368
443 1089
186 39
548 540
1062 539
105 546
91 1188
333 462
930 1180
295 417
403 95
280 700
355 432
146 766
267 831
904 324
1047 ...

output:

1

result:

ok single line: '1'

Test #38:

score: 3
Accepted
time: 11ms
memory: 35928kb

input:

2345 36 100 50
1483 1104
731 1472
259 409
1410 1081
1914 802
45 1156
833 790
1092 900
1089 159
2235 2043
797 572
1616 1807
2027 1124
285 1920
607 1280
1034 114
1231 1540
777 1440
1507 2039
1603 3
681 1260
1053 2300
809 1913
1361 1763
1628 463
118 289
1395 2121
882 417
111 472
1279 1336
2324 136
2013...

output:

1

result:

ok single line: '1'

Test #39:

score: 3
Accepted
time: 11ms
memory: 33416kb

input:

3000 2763 10 5
2045 2874
920 2652
1567 2728
1201 2754
1503 1773
940 2797
440 1785
1936 2493
1789 1034
720 2004
1437 617
2787 256
427 757
224 2778
532 2547
2949 2504
1406 2895
1516 2218
2276 1366
742 2277
2636 2820
2465 1978
1742 696
553 697
930 421
1998 1400
188 684
423 2224
371 2083
471 3000
709 27...

output:

10

result:

ok single line: '10'

Test #40:

score: 3
Accepted
time: 5ms
memory: 32948kb

input:

3000 1809 100 50
970 2578
1613 803
2543 868
703 1731
1015 146
1894 806
2367 2708
704 2144
405 532
1795 1918
1337 1208
1084 1674
2609 2253
1847 1747
918 1461
1229 126
873 1948
2963 2499
1069 491
451 441
679 1752
2460 2688
149 557
1344 1848
2218 2066
31 895
1819 1349
37 750
2819 2216
504 2588
1571 226...

output:

1

result:

ok single line: '1'

Test #41:

score: 3
Accepted
time: 3ms
memory: 36028kb

input:

3000 428 1000 500
1235 2483
1038 1248
1686 1427
2539 417
1375 1120
1014 1266
647 2715
918 67
1920 1640
2892 543
2060 1215
816 292
2020 2318
2626 2711
1422 2207
605 2528
1035 1638
2716 2636
2101 2731
1720 2467
2239 1502
1418 2581
2039 2763
342 1047
2214 1403
2508 1845
330 2864
2069 1601
2439 1432
682...

output:

1

result:

ok single line: '1'

Test #42:

score: 3
Accepted
time: 6ms
memory: 33968kb

input:

3000 1830 10 5
707 2455
238 293
2333 1830
2357 142
2284 917
1948 951
626 1368
1644 2504
1736 552
2787 749
2072 626
1030 1830
2398 1863
1077 1265
1334 1117
681 1690
1552 890
2710 612
2675 1268
1755 1736
432 138
2902 1739
1692 1074
1443 1579
130 138
155 2440
469 2119
2537 784
1413 1830
1745 2420
1721 ...

output:

1

result:

ok single line: '1'

Test #43:

score: 3
Accepted
time: 4ms
memory: 33952kb

input:

3000 447 100 50
2018 1373
2585 1432
1765 2078
101 1994
2830 1867
2834 1388
2767 1133
2378 434
185 2560
1241 850
762 750
961 1204
1847 1893
481 304
2749 1149
994 447
2142 2480
1057 573
2080 1204
165 1133
285 1299
2403 985
447 438
2592 463
2561 729
2296 447
563 2749
205 382
2139 528
888 2378
1850 1861...

output:

1

result:

ok single line: '1'

Test #44:

score: 3
Accepted
time: 10ms
memory: 35876kb

input:

3000 2724 1000 500
2050 1598
989 1852
125 1601
2439 1517
497 2510
618 2747
486 1367
1942 527
400 136
1471 2724
2875 486
2471 2594
1328 667
824 2802
607 391
240 2849
2711 2439
1202 1944
1347 989
2375 2168
933 1827
1106 178
2194 734
2419 2811
601 528
2890 822
635 2395
832 2594
1383 2202
2088 1041
933 ...

output:

1

result:

ok single line: '1'

Test #45:

score: 3
Accepted
time: 4ms
memory: 34092kb

input:

3000 1779 3 2
2992 2251
1763 2992
691 2992
2992 2102
2344 57
1163 2559
2798 2992
534 394
719 1163
139 2992
1163 946
203 181
588 2992
2992 2825
1370 1349
2992 962
2992 2856
2584 863
1786 2992
2743 2992
434 2992
2992 1293
20 2992
2477 706
2992 251
2853 517
2612 2992
2992 1350
2992 310
2311 1163
2992 1...

output:

1

result:

ok single line: '1'

Test #46:

score: 3
Accepted
time: 7ms
memory: 33312kb

input:

2999 7 3 2
2618 877
314 2309
698 2889
717 877
877 2045
1747 111
698 2915
877 1558
698 1157
1369 877
1442 698
877 1466
698 883
877 87
1479 910
877 2221
2217 877
410 877
877 2048
1692 877
1868 877
537 1913
795 678
1013 877
2174 877
877 2385
608 698
877 1476
94 698
877 422
1297 698
1774 1002
698 2264
1...

output:

1

result:

ok single line: '1'

Test #47:

score: 3
Accepted
time: 11ms
memory: 35896kb

input:

2998 1036 3 2
2608 498
2961 1017
2608 2159
39 1501
1686 2608
2608 1494
428 2608
2681 1713
2608 2226
2608 1961
1800 2577
434 2681
186 1561
2608 2666
1772 2608
2197 2416
2608 1651
1797 457
2903 2608
2385 2608
2400 1937
2608 2051
1424 372
2608 1034
2791 2608
2608 27
2608 659
900 2608
2028 1866
2681 397...

output:

2

result:

ok single line: '2'

Test #48:

score: 3
Accepted
time: 7ms
memory: 33972kb

input:

3000 40 300 160
52 244
261 122
1943 809
993 895
2718 1514
1252 1384
1376 2663
2050 2398
704 335
1045 1867
2846 2330
851 1543
2756 875
99 105
1765 2714
2218 1170
2586 2581
2340 2594
897 447
2235 2369
1648 1017
1353 1209
2553 2198
595 929
1928 2104
1523 1173
2526 2565
1696 474
2523 1581
1053 1968
1932...

output:

281

result:

ok single line: '281'

Subtask #5:

score: 4
Accepted

Test #49:

score: 4
Accepted
time: 479ms
memory: 43204kb

input:

100000 20749 3 2
89778 51257
2293 75317
20142 42260
55350 69024
2419 90402
2248 71914
60607 94307
33933 57799
79884 93934
9788 53542
18109 28742
7700 93763
12102 78825
34580 61577
84344 12887
63610 12371
30988 75638
47533 66209
95296 22495
12638 545
36347 57495
41813 49592
60342 1881
38899 62345
524...

output:

43056

result:

ok single line: '43056'

Test #50:

score: 4
Accepted
time: 475ms
memory: 48324kb

input:

100000 81436 3 2
30487 98338
75456 42340
35081 95919
14744 79324
12767 72910
10330 15285
18425 40190
49306 55115
27041 60644
82901 10649
43365 29415
57822 86861
83007 50520
39798 89642
44146 63575
29824 89809
23549 45972
89791 83570
13656 1315
63396 74190
21244 80244
90922 97110
38966 92339
84884 89...

output:

717

result:

ok single line: '717'

Test #51:

score: 4
Accepted
time: 455ms
memory: 42708kb

input:

100000 8852 4 2
40452 57256
17799 88040
60724 53958
13290 90136
19267 49330
97135 48815
91159 71145
11677 334
6176 11175
2311 36476
80261 78319
22343 42921
53692 9431
20138 8540
15962 57516
66603 41779
22916 82799
36377 26000
46797 3889
5764 3600
76457 13146
41675 46067
65577 93967
3461 31914
46191 ...

output:

66085

result:

ok single line: '66085'

Test #52:

score: 4
Accepted
time: 510ms
memory: 46352kb

input:

100000 16035 4 2
43071 56048
63171 4393
98259 47823
2561 96442
9238 88690
85973 58025
9308 88080
16242 96064
88566 55956
57022 90692
84895 82151
27964 28817
24774 35654
35624 93885
37408 43501
89095 11303
1737 8666
378 67623
56302 11639
22263 32297
12188 72428
49974 80854
29579 370
70340 55421
4511 ...

output:

13134

result:

ok single line: '13134'

Test #53:

score: 4
Accepted
time: 424ms
memory: 43320kb

input:

100000 85235 3 1
94738 24340
59327 27917
90855 27869
97393 55723
50462 24028
27405 59525
40629 84195
41269 21311
97793 12448
94822 90533
96359 70118
59964 12798
51098 68286
58527 7816
41817 19034
10924 54535
63191 97115
60743 79349
6864 76498
29085 92310
8063 41260
11214 91868
23225 2976
50822 99018...

output:

86829

result:

ok single line: '86829'

Test #54:

score: 4
Accepted
time: 435ms
memory: 43680kb

input:

100000 96572 3 1
36159 41653
67667 34037
37976 63963
45201 5393
52221 59416
54961 13650
28764 99209
60804 67606
48624 79765
41041 83510
51667 65582
53730 45676
22269 64403
52565 21021
64941 4761
62855 69936
67203 18060
91572 33888
52593 86981
38287 22045
72710 6674
19970 36871
12501 91926
14428 9425...

output:

12008

result:

ok single line: '12008'

Test #55:

score: 4
Accepted
time: 434ms
memory: 46068kb

input:

100000 73324 10 4
71933 28912
87834 88149
44971 99521
60861 82846
97055 92782
56244 87280
53155 84157
70530 70324
79371 71634
21639 40110
75095 53060
6988 96059
21201 57449
65138 12755
88230 54355
87152 56089
86570 76587
79256 65685
16310 13946
41916 10874
9161 88963
90203 58683
76300 29464
25230 30...

output:

513

result:

ok single line: '513'

Test #56:

score: 4
Accepted
time: 238ms
memory: 40564kb

input:

100000 15636 100000 10
10243 50231
32391 7992
18149 2934
33787 51982
96445 22322
41361 80285
17777 24611
69149 49364
87021 54306
89564 43531
90973 83603
85869 90213
27390 88410
38427 49151
77811 41575
32541 86212
92924 21286
47549 65738
76763 15623
17786 10339
32880 76070
9809 67114
91819 43885
7140...

output:

1

result:

ok single line: '1'

Test #57:

score: 4
Accepted
time: 463ms
memory: 46072kb

input:

100000 42996 20 10
74902 50663
7097 23701
45735 7288
52375 46377
46724 63127
89073 24467
29104 28729
83469 85669
70860 88962
78797 72790
27570 86063
24686 20963
90850 57413
17431 29758
84798 67397
74951 85193
37009 12044
56862 33692
23929 61577
18914 38454
58446 32853
69649 68901
55638 59986
47751 1...

output:

221

result:

ok single line: '221'

Test #58:

score: 4
Accepted
time: 481ms
memory: 45596kb

input:

100000 98739 100 10
85414 42813
17848 77599
42506 71989
1918 745
9097 91249
79539 71491
71938 77961
66338 99594
19970 52870
38371 91469
69665 44311
13354 45803
56738 89880
46844 51870
38831 48646
37471 66852
2177 16313
35195 71674
8625 70549
1856 78239
9309 43203
4214 95780
29103 47895
69129 78296
4...

output:

14017

result:

ok single line: '14017'

Test #59:

score: 4
Accepted
time: 367ms
memory: 44604kb

input:

100000 29573 10000 10
54397 69025
83525 16322
69843 91831
18296 65353
43293 19327
70856 30469
80150 62236
40232 32171
68933 90628
66837 2965
54776 47328
62998 65584
23455 70312
34594 26099
90702 38631
99042 75615
83802 53660
60219 72548
22411 34554
71451 67910
31284 17953
55582 86186
80488 79094
180...

output:

4314

result:

ok single line: '4314'

Test #60:

score: 4
Accepted
time: 221ms
memory: 44340kb

input:

100000 80902 11 10
90717 1067
6057 7613
33217 91418
62156 49414
35712 58370
3406 3782
14422 36383
13121 54659
75065 82970
75833 76063
45137 74130
15269 84206
55939 35132
58683 99724
10608 64362
97967 78859
87661 3406
18955 76762
80678 25453
18179 44046
76792 92120
94865 94823
41467 53099
16426 15081...

output:

1

result:

ok single line: '1'

Test #61:

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

input:

100000 10278 10 10
22080 78739
83644 60650
84023 10536
67793 39227
64817 3246
95349 11887
32894 95918
57769 72231
70181 74963
19829 86171
64925 17589
77353 21140
73018 75509
80759 72751
77187 23048
67991 3801
84230 36205
67544 76682
47475 7799
55601 5047
33506 35435
84123 96632
55627 68456
12697 632...

output:

1

result:

ok single line: '1'

Test #62:

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

input:

56789 52146 3 3
5472 30471
5612 23037
21888 4725
9673 14647
40053 18588
21170 12453
8765 7882
10193 30274
4849 41647
31241 54244
14257 31966
15987 54036
16735 44259
53171 6717
55365 38027
42958 27812
48238 1399
3252 46229
5390 16924
29962 31185
34680 46655
43807 6253
1971 15286
53171 8341
8324 41346...

output:

1

result:

ok single line: '1'

Test #63:

score: 4
Accepted
time: 449ms
memory: 45184kb

input:

87654 33545 100 10
76907 51162
2915 42413
34214 66794
26541 46255
64067 84944
39351 71693
45020 7870
24345 49823
43523 68748
18308 78976
46430 4311
73739 13607
4941 68811
33354 64770
22269 605
65058 33589
73005 12430
4881 65990
15196 24871
74977 64963
26162 16647
25414 25820
62913 18924
45927 6426
5...

output:

312

result:

ok single line: '312'

Test #64:

score: 4
Accepted
time: 368ms
memory: 43972kb

input:

100000 15972 3 2
4042 27219
48452 50004
24050 15265
98768 92464
84229 32638
37774 25749
60779 4042
22693 4042
20459 60049
31647 92464
85570 4042
32048 66569
15807 66317
4042 40632
58038 4042
4042 42309
91476 92464
56479 4042
4042 99680
44063 92464
91388 4042
4042 20396
90085 4042
92464 42365
52267 4...

output:

1

result:

ok single line: '1'

Test #65:

score: 4
Accepted
time: 356ms
memory: 44420kb

input:

99999 81648 3 2
9887 25839
25256 91573
49540 29303
57225 9887
9887 70368
71428 9887
75119 43654
49540 10823
9887 46802
67383 9887
39690 78526
15448 9887
9887 74383
2408 35602
27412 26263
9887 5426
68446 21949
22730 9887
40208 9887
85864 9887
9887 29904
9887 43673
27973 9887
9887 76950
9887 18302
535...

output:

1

result:

ok single line: '1'

Test #66:

score: 4
Accepted
time: 362ms
memory: 41268kb

input:

99998 21401 3 2
86802 83093
22689 98078
98078 27135
86802 27190
86802 24635
86802 48361
86802 15404
91042 86802
55168 80091
58962 86802
86802 63714
92439 12924
86802 91316
42935 86802
86802 77106
25977 86802
86802 36711
81148 17527
13300 86802
29366 86802
70356 66339
55207 86802
51397 86802
86802 33...

output:

2

result:

ok single line: '2'

Test #67:

score: 4
Accepted
time: 571ms
memory: 70768kb

input:

100000 19380 10000 10
29035 13872
72983 17203
73146 17085
96627 62817
82836 37282
7304 48599
99013 20988
19677 50106
6143 51794
67680 23396
66608 38204
64941 92480
9700 67672
76815 73041
48776 50729
93872 94057
95160 30168
71242 31768
15672 49775
4195 55846
92771 77623
11578 31199
44029 7070
9075 90...

output:

99529

result:

ok single line: '99529'

Subtask #6:

score: 6
Accepted

Dependency #4:

100%
Accepted

Dependency #5:

100%
Accepted

Test #68:

score: 6
Accepted
time: 488ms
memory: 42544kb

input:

100000 79681 3 2
65943 25943
64751 74801
57286 6984
13774 36580
23143 82174
51469 96068
24596 77451
94363 13896
18470 19474
68028 3059
77 13602
54700 3984
8188 60238
6007 78575
95532 21455
13378 39417
45536 60395
98017 33987
84394 70544
93145 46410
48606 72175
73854 64081
49684 71878
99672 4760
6897...

output:

54486

result:

ok single line: '54486'

Test #69:

score: 6
Accepted
time: 474ms
memory: 45888kb

input:

100000 15840 3 2
88368 32222
72516 57332
71137 45652
77873 56262
17321 97378
24618 90143
49976 42914
68448 43878
26069 61922
66409 18799
2863 2605
26978 13318
61711 22341
32818 34273
50934 1012
78542 98376
31868 61940
4802 84964
23060 90806
12184 16593
48704 99283
91878 58705
63067 58968
66058 42911...

output:

877

result:

ok single line: '877'

Test #70:

score: 6
Accepted
time: 437ms
memory: 45188kb

input:

100000 73721 4 2
46271 35241
36492 95324
35040 65653
3396 11262
86051 42210
7656 47964
45764 93238
80057 74793
20067 84113
55042 51695
70839 11606
47168 88124
99709 62149
61079 56998
1321 35438
72354 52617
76073 68697
73197 45844
8059 17400
50545 3861
60037 17731
27907 90079
93031 41726
4140 68737
4...

output:

48942

result:

ok single line: '48942'

Test #71:

score: 6
Accepted
time: 504ms
memory: 48140kb

input:

100000 15578 4 2
10111 53492
9632 67579
38724 95534
49283 80843
19512 41050
39897 18101
79808 87308
66915 22116
78652 36288
60878 44610
85811 34036
91901 93037
36311 74017
31790 10603
24695 61447
86163 32832
30865 43354
11672 29472
67030 54060
62821 74540
45414 69779
52870 32616
91156 45581
46750 85...

output:

7354

result:

ok single line: '7354'

Test #72:

score: 6
Accepted
time: 444ms
memory: 46076kb

input:

100000 6124 3 1
40762 76226
78347 57394
42752 9861
45489 22823
97528 13512
62525 17178
14194 85285
81172 58828
45011 4468
13452 59004
41399 15658
87883 49748
30178 94468
38448 50063
54553 31024
82794 18937
93680 89151
9925 52234
64352 21350
3317 11169
77606 94917
141 68896
55015 84146
85623 72438
16...

output:

86867

result:

ok single line: '86867'

Test #73:

score: 6
Accepted
time: 518ms
memory: 43932kb

input:

100000 66738 3 1
89639 69778
97184 25998
88179 69822
33957 26151
64809 22942
53225 83132
62441 90673
45849 68376
91087 15230
64047 25497
47739 61833
30108 24118
66142 14266
96942 43993
56876 60628
46767 66099
26036 18948
6706 14340
21439 63182
13202 5528
18019 74383
63793 98431
87351 86472
72529 747...

output:

30

result:

ok single line: '30'

Test #74:

score: 6
Accepted
time: 492ms
memory: 46084kb

input:

100000 96793 10 4
34642 34513
32968 61036
33772 17291
85054 7799
82168 14086
7392 19287
9364 92784
79175 25948
19843 8845
49235 23348
6666 97397
20732 5709
77156 38850
59993 90802
89186 34888
62803 58581
93237 34131
68467 55638
97575 87364
97572 57676
28223 2964
93324 79533
57578 44083
53803 8191
84...

output:

902

result:

ok single line: '902'

Test #75:

score: 6
Accepted
time: 250ms
memory: 41432kb

input:

100000 31181 100000 10
63022 92673
71462 25888
96677 29578
40335 3175
37598 54692
87495 95461
74095 66117
87555 59227
23600 62523
61412 89310
11847 26874
16359 50211
64895 16886
97596 53308
94245 45884
2139 67854
68955 32836
58723 55149
46463 77115
26337 59216
77087 4813
93502 63267
34202 59007
2482...

output:

1

result:

ok single line: '1'

Test #76:

score: 6
Accepted
time: 6ms
memory: 29060kb

input:

56789 39098 3 3
3481 5161
8435 13125
14466 50352
50533 50600
47604 33073
24477 8464
51147 44938
9183 52936
31467 16896
55568 3221
25223 34105
7469 20422
10345 38508
19441 44228
50779 46533
11647 28715
56050 19508
24770 13778
17071 35596
53790 1570
6184 30111
32063 18940
51267 46295
56724 33863
45912...

output:

1

result:

ok single line: '1'

Test #77:

score: 6
Accepted
time: 459ms
memory: 42776kb

input:

87654 56358 100 50
72317 47978
78856 36640
56770 18011
61973 67563
39185 24373
26244 45718
53264 41636
7511 7878
20021 84381
18394 54550
76972 86488
9599 57482
7435 75084
16143 50154
14905 40301
80886 11064
66613 84558
82371 6010
54230 3706
31448 65385
47640 15115
70498 26741
12831 48221
56635 38218...

output:

21

result:

ok single line: '21'

Test #78:

score: 6
Accepted
time: 323ms
memory: 41344kb

input:

100000 3380 3 2
95383 48360
7742 14053
48360 64436
48360 68606
86415 14053
14053 66772
13208 48360
63092 48360
66713 48360
84475 48360
48360 9230
43859 48360
75049 48360
48360 86137
6625 14053
70128 48360
14053 64172
86581 48360
48360 5797
48360 87148
48360 66607
62350 14053
45081 69852
48360 62061
...

output:

3

result:

ok single line: '3'

Test #79:

score: 6
Accepted
time: 371ms
memory: 41380kb

input:

99999 283 3 2
18003 77557
18003 73195
18003 11504
84779 18003
60285 18003
12091 18003
18003 63586
18003 87953
75864 54787
18003 15884
88267 18003
65215 68596
1668 18003
19890 1733
18003 73447
41965 19890
83746 19890
19890 62816
74315 41461
18003 33472
97612 18003
19890 79178
30835 18003
18003 88576
...

output:

2

result:

ok single line: '2'

Test #80:

score: 6
Accepted
time: 330ms
memory: 41648kb

input:

99998 86848 3 2
30752 74647
74647 28077
88760 93457
8086 64715
47530 70402
46833 74647
64362 70402
958 70402
69672 74647
95576 74647
16639 74647
74647 3331
61704 85738
70402 64904
74647 6261
32964 71233
17337 74647
92328 74647
59157 74647
70402 96228
57055 67097
74647 35812
74647 30326
74647 36722
7...

output:

4

result:

ok single line: '4'

Test #81:

score: 6
Accepted
time: 255ms
memory: 51540kb

input:

100000 1 33333 33328
94382 66665
43697 43699
43843 43844
1775 1776
66665 90038
12053 12054
13919 13921
15801 15802
27739 27740
1737 1735
66665 80744
50031 50032
61407 61409
12298 12297
50393 50394
43195 43197
61597 61598
76614 66665
72865 66665
13863 13864
71983 66665
74061 66665
35661 35663
3685 36...

output:

11

result:

ok single line: '11'

Test #82:

score: 6
Accepted
time: 604ms
memory: 69012kb

input:

100000 2 49997 49996
30182 32936
77595 21981
20003 45252
40044 67777
53886 34134
1385 53439
85622 80855
76058 73770
61477 46723
31775 33113
76864 67259
34565 75668
99797 35534
86877 44523
93890 66595
82568 69278
36734 23229
66325 90336
63054 44201
40689 8074
98229 28489
38172 12835
55741 74112
13232...

output:

3

result:

ok single line: '3'

Test #83:

score: 6
Accepted
time: 469ms
memory: 45584kb

input:

100000 23650 10 5
6859 14146
23398 9444
13470 12125
14605 49681
94926 36754
44629 38656
69557 49347
80719 13804
35100 77977
81231 81049
20843 1399
32621 50817
57927 4514
17141 47658
59273 1469
35638 12421
85111 67386
70981 90375
22037 18096
29074 50820
17370 51159
85602 73431
31092 94880
3608 36076
...

output:

33

result:

ok single line: '33'

Test #84:

score: 6
Accepted
time: 349ms
memory: 41296kb

input:

100000 7634 1000 500
26044 18744
20860 11629
30315 82992
66874 77260
90681 77225
7716 64640
79644 51041
56528 32972
45743 36456
68388 47032
32036 73640
24008 7603
64360 89766
30115 60265
36728 98245
84409 9646
99108 91167
82750 96204
61774 88997
53081 49206
95785 65194
27079 83951
10170 25471
93531 ...

output:

4

result:

ok single line: '4'

Test #85:

score: 6
Accepted
time: 365ms
memory: 42064kb

input:

100000 50421 10000 5000
42449 770
50346 12283
66063 47493
90198 42136
92907 57042
81469 22353
51160 4455
48973 77857
55044 58108
46191 96928
87025 41563
93925 22658
71490 71127
83482 59187
79881 83962
77717 71456
31681 50447
98014 64711
49166 14558
96049 60117
94924 1718
57224 89983
24710 54449
4590...

output:

1

result:

ok single line: '1'

Test #86:

score: 6
Accepted
time: 205ms
memory: 40136kb

input:

100000 28604 10 5
76715 37086
82111 70907
38220 49776
81068 85777
10761 25003
24093 92795
17142 37290
74598 5574
75843 70852
75456 62758
18128 73283
3436 89461
77282 13159
41088 1729
69015 88993
55182 44879
8000 73441
27521 38465
62850 68916
32073 76871
44311 30880
32015 56897
67265 9504
13885 88290...

output:

1

result:

ok single line: '1'

Test #87:

score: 6
Accepted
time: 203ms
memory: 41640kb

input:

100000 70083 1000 500
79817 74215
98708 70083
49220 42573
8890 98801
6676 14305
33040 61966
28387 2752
53585 220
24896 89007
57711 72529
76140 14929
40341 40434
49748 64622
6536 45952
78825 81216
42300 25903
88124 14721
27015 57021
327 93146
20736 24202
11404 18409
9217 72420
95437 20947
21350 51505...

output:

1

result:

ok single line: '1'

Test #88:

score: 6
Accepted
time: 221ms
memory: 44312kb

input:

100000 49562 10000 5000
46498 10815
15301 81790
53499 96895
25387 93111
22587 68868
49916 40273
97590 28896
23455 23544
27726 18526
16305 83834
79034 62591
73816 49801
53963 31994
64514 37320
40421 78013
5956 20002
53211 70013
51300 76968
80718 8602
54413 85265
88046 90969
6153 69178
6073 85535
8226...

output:

1

result:

ok single line: '1'

Test #89:

score: 6
Accepted
time: 585ms
memory: 69276kb

input:

100000 46154 50000 49999
47016 38897
66925 18825
48698 77234
30283 12445
86129 46153
45150 25969
79369 31992
75455 8768
47253 47772
10254 32169
60935 67226
92351 62295
93937 1162
25602 11603
58899 13959
69361 69866
54500 95204
23487 36100
82384 8308
43341 78933
44496 2751
30240 23478
68152 33192
132...

output:

1

result:

ok single line: '1'

Test #90:

score: 6
Accepted
time: 495ms
memory: 71816kb

input:

100000 1 50000 49999
62814 81308
83268 72606
90333 10041
59862 24350
522 42186
7635 22675
84956 21271
32197 2726
19300 95110
67592 4855
63062 43807
38925 33677
14431 28147
763 32650
64829 26232
21616 4751
7883 98794
11936 49487
44782 89199
49831 71583
59058 42561
5103 2354
47803 28007
64252 36786
88...

output:

2

result:

ok single line: '2'

Test #91:

score: 6
Accepted
time: 298ms
memory: 41956kb

input:

100000 1 35 16
61195 30615
11466 22898
79689 39862
8743 4389
9984 5009
83343 41689
19770 39505
16986 8510
88240 44137
28192 56350
12176 24318
66328 33181
47343 94651
33090 16562
6714 3374
5449 2742
2267 4500
39411 19723
18100 9067
22159 44283
5258 10482
34539 69043
29935 59835
46988 23511
48206 9637...

output:

20

result:

ok single line: '20'

Test #92:

score: 6
Accepted
time: 389ms
memory: 44728kb

input:

100000 86267 25 13
31258 30976
55837 34236
13603 66227
17602 74672
45672 36434
75574 77180
69881 3266
11502 55644
35400 14755
2033 86491
91832 32566
73769 65604
93477 71194
1543 92861
19242 89206
12774 16599
46244 99939
15099 87663
72373 12062
44723 15389
51573 51867
80435 41110
30656 84423
9645 140...

output:

1

result:

ok single line: '1'

Subtask #7:

score: 2
Accepted

Dependency #1:

100%
Accepted

Dependency #2:

100%
Accepted

Dependency #3:

100%
Accepted

Dependency #4:

100%
Accepted

Dependency #5:

100%
Accepted

Dependency #6:

100%
Accepted

Test #93:

score: 2
Accepted
time: 2153ms
memory: 67844kb

input:

300000 290458 3 2
89761 242981
239856 72617
49395 258412
214882 238523
3741 219396
149053 261989
143898 100394
236293 214322
183884 127661
253450 172599
127103 222607
121038 286388
253783 260105
262460 11641
223888 141812
139608 211436
52679 225192
121955 200346
66338 244580
281902 252206
202908 121...

output:

126815

result:

ok single line: '126815'

Test #94:

score: 2
Accepted
time: 2241ms
memory: 68688kb

input:

300000 86076 3 2
192090 92834
200602 23391
275886 155394
175446 187906
189963 139779
82798 235190
273267 282337
222837 107550
182767 287331
170630 202465
176885 99079
113728 12960
155256 115856
285506 263655
28762 212259
178240 101131
270358 111895
220430 235930
103834 124132
283107 23817
65663 2068...

output:

4855

result:

ok single line: '4855'

Test #95:

score: 2
Accepted
time: 2008ms
memory: 67192kb

input:

300000 170191 4 2
16574 147311
288893 73391
43950 140133
74896 207857
271478 267503
194299 128859
299909 54527
100286 242939
85436 183966
125702 53056
115594 161896
170191 222795
110979 73759
299352 123549
156411 212807
188697 146351
231330 257460
82761 67078
230489 123981
247793 246240
264858 66564...

output:

211431

result:

ok single line: '211431'

Test #96:

score: 2
Accepted
time: 2512ms
memory: 68868kb

input:

300000 67839 4 2
122158 220335
181421 41073
80274 176431
24875 7209
48672 9983
2146 83291
23974 240091
32270 245573
157650 8719
295275 141835
194195 64245
161688 251783
236149 147863
150823 100887
43776 105861
135220 49060
95987 269789
258161 27722
247979 276974
195838 88170
117013 181619
221335 206...

output:

3206

result:

ok single line: '3206'

Test #97:

score: 2
Accepted
time: 1971ms
memory: 67472kb

input:

300000 253332 3 1
234880 197301
205934 281725
111844 62266
218532 74288
260502 173488
221078 6258
182874 76732
225788 36888
91168 88859
109931 222053
259698 113858
170110 282913
187448 20575
296641 76912
26580 210930
133813 60018
169211 279314
298320 286804
183289 67738
110675 267060
271764 296175
1...

output:

277508

result:

ok single line: '277508'

Test #98:

score: 2
Accepted
time: 2568ms
memory: 69232kb

input:

300000 251657 3 1
4992 249899
196161 133998
87909 268432
87422 194568
168919 135619
252547 132113
194530 125463
250006 252692
43479 97786
261448 18200
155902 171878
190185 293686
214697 295642
30402 24431
10153 238214
131296 140542
127891 177424
177138 12341
50445 189862
98605 143563
229389 273076
1...

output:

61573

result:

ok single line: '61573'

Test #99:

score: 2
Accepted
time: 2249ms
memory: 67500kb

input:

300000 293301 10 4
102251 187866
296151 13576
236821 246660
183203 193550
221660 99413
113982 121315
211748 86782
270705 205531
202933 270912
41554 140278
121800 214485
286689 117927
253194 76580
261878 47329
88906 40729
82853 76309
109640 116207
228876 234613
181642 19781
234536 127666
271615 10870...

output:

12815

result:

ok single line: '12815'

Test #100:

score: 2
Accepted
time: 1084ms
memory: 63928kb

input:

300000 155627 300000 10
40858 150635
126587 136137
236524 156676
43350 148390
5297 193787
55897 3503
30015 99455
78725 49413
162963 257357
206359 247685
41894 78801
257900 218692
8262 243269
94649 202127
48607 74232
107474 45731
28923 161101
29189 57940
162692 65960
173051 165824
206709 171516
19041...

output:

1

result:

ok single line: '1'

Test #101:

score: 2
Accepted
time: 4ms
memory: 29452kb

input:

123456 97061 3 3
36201 20383
72504 17901
113906 110459
45160 119290
88126 56049
51576 106238
76991 106556
13724 51300
72397 79347
121708 60994
51197 102699
103764 2993
19149 75835
105123 116056
5671 49130
111421 5719
4327 104838
96789 55536
20866 100325
81615 108178
26363 29011
41151 72783
11898 108...

output:

1

result:

ok single line: '1'

Test #102:

score: 2
Accepted
time: 1703ms
memory: 56288kb

input:

234567 41757 100 50
163988 175287
4714 34399
167778 55032
121173 182879
86304 65616
132400 175558
185865 113945
212313 204991
10861 146094
104443 83009
96696 230946
14524 30230
149764 67520
133628 232100
176691 209619
97994 1896
120782 13574
124669 103304
33302 138431
211232 69531
123862 104422
2202...

output:

167

result:

ok single line: '167'

Test #103:

score: 2
Accepted
time: 1529ms
memory: 63244kb

input:

300000 42115 3 2
158430 54017
125298 158430
158430 52707
134630 158430
295323 158430
158430 218355
244742 107425
135194 251000
158430 35359
135194 20534
167594 135194
180229 135194
175132 210310
261554 158430
215134 158430
135194 161995
252523 158430
22550 158430
194447 158430
251627 135194
189429 1...

output:

3

result:

ok single line: '3'

Test #104:

score: 2
Accepted
time: 1572ms
memory: 63232kb

input:

299999 123015 3 2
43267 274745
7856 274745
199438 67591
28239 164187
274745 190891
156106 69573
274745 31165
274745 282561
274745 130029
219980 274745
88356 274745
274745 119066
69573 167954
12336 102991
15025 274745
263487 274745
255001 274745
274745 35038
274745 60968
259392 274745
274745 38760
15...

output:

3

result:

ok single line: '3'

Test #105:

score: 2
Accepted
time: 1590ms
memory: 63776kb

input:

299998 147099 3 2
135683 191977
15452 135683
135683 258805
5362 135683
135683 65145
135683 90649
135683 150419
195201 135683
58287 135683
93365 135683
125237 205676
135683 27337
135683 83990
135683 282255
135683 276620
114589 135683
203668 135683
135683 12349
8972 135683
19343 252642
160348 135683
1...

output:

1

result:

ok single line: '1'

Test #106:

score: 2
Accepted
time: 985ms
memory: 85184kb

input:

300000 1 100000 99995
228565 199999
164245 164246
20687 20688
165127 165129
30061 30062
199999 233044
199999 237685
117203 117205
182380 182379
227768 199999
153046 153045
51481 51483
57857 57858
38700 38699
199999 253412
273619 199999
186127 186125
42137 42135
261945 199999
2363 2365
65055 65057
19...

output:

11

result:

ok single line: '11'

Test #107:

score: 2
Accepted
time: 2862ms
memory: 140348kb

input:

300000 2 149997 149996
103876 154476
290403 103399
121986 102822
224408 75127
218876 152753
149690 241597
162318 285564
220962 55945
199129 144008
38064 105046
163598 21703
185682 134544
162514 256468
78340 240242
171359 23964
181690 201790
247680 229546
52285 83680
297092 229030
164908 61752
58460 ...

output:

3

result:

ok single line: '3'

Test #108:

score: 2
Accepted
time: 2248ms
memory: 68156kb

input:

300000 153275 10 5
57007 270358
292455 58806
113253 53959
82971 149250
111658 194090
23743 90634
239745 238756
190461 76153
142527 139298
21540 64839
264560 97331
215734 249630
280487 28684
145425 51850
69951 97411
56350 72946
5150 218152
225137 80140
3779 8274
250534 260817
159548 125312
120085 260...

output:

377

result:

ok single line: '377'

Test #109:

score: 2
Accepted
time: 1690ms
memory: 65544kb

input:

300000 56122 1000 500
246373 20136
104868 177579
100842 150848
15078 235482
19856 184750
134314 8915
58979 222496
212411 268221
36949 84430
148081 30710
126133 160752
97886 115389
119983 23729
51289 3725
183583 171240
197491 114140
246857 84944
9813 14295
66599 287014
116416 2606
77767 128126
221865...

output:

39

result:

ok single line: '39'

Test #110:

score: 2
Accepted
time: 1717ms
memory: 66048kb

input:

300000 98831 10000 5000
4239 35126
99874 192127
265897 50401
69434 229928
95860 49388
168392 267856
189823 175233
82158 151132
194071 127447
156599 103159
196171 58144
34403 283834
291414 96086
35473 248369
233530 221294
191449 198016
90215 155610
123062 137560
85938 80477
11163 88070
80492 218879
2...

output:

1

result:

ok single line: '1'

Test #111:

score: 2
Accepted
time: 889ms
memory: 62848kb

input:

300000 212269 10 5
46564 268709
32227 2609
101942 34886
104834 18648
240730 186632
143277 187160
174786 75074
243711 243429
97064 156744
230737 293552
186857 170262
34886 176348
189923 127221
145930 135537
273328 254691
80534 18036
141741 113307
101175 189154
198049 33816
84822 97166
160678 204198
1...

output:

1

result:

ok single line: '1'

Test #112:

score: 2
Accepted
time: 865ms
memory: 62824kb

input:

300000 251749 1000 500
35439 61509
189598 41088
176523 232044
124688 86626
43566 103515
120785 45632
127042 200459
43124 261083
160724 208283
26546 156263
118925 280264
67757 285991
120910 299264
221863 225018
96511 198980
120538 199052
149704 249354
267371 85710
278505 219190
299918 62321
180716 15...

output:

1

result:

ok single line: '1'

Test #113:

score: 2
Accepted
time: 980ms
memory: 63920kb

input:

300000 172 10000 5000
55932 68691
87348 227644
228603 53019
84441 174413
80117 45127
167355 155721
66182 28788
259714 165825
32678 49925
211070 94693
240041 146882
8172 296581
90926 151556
260560 81718
136291 31760
5017 37681
31476 47785
153621 222893
41121 204659
79187 244542
19044 292291
85789 872...

output:

1

result:

ok single line: '1'

Test #114:

score: 2
Accepted
time: 2816ms
memory: 137172kb

input:

300000 149359 150000 149999
129991 293025
46422 119528
229449 139502
123467 39703
122920 21527
74087 11061
19505 280399
99852 282861
276885 202410
164338 75723
275167 228020
297453 26274
206564 95117
108348 178597
27564 233240
148000 129627
183726 231811
245199 194668
221999 134597
235830 173092
105...

output:

1

result:

ok single line: '1'

Test #115:

score: 2
Accepted
time: 2355ms
memory: 140400kb

input:

300000 1 150000 149999
164998 106271
26192 297974
24769 243344
114798 106556
170625 134814
203289 196660
187507 30083
72441 18245
275800 170178
7556 23647
127682 295756
126792 171169
296870 93092
45815 61096
168145 60968
165268 120227
242565 186568
298589 166203
199915 159804
234696 181293
78621 281...

output:

2

result:

ok single line: '2'

Test #116:

score: 2
Accepted
time: 1040ms
memory: 65960kb

input:

300000 1 40 20
53283 106526
98238 196437
155871 77955
135507 67773
39226 78412
140415 280790
145324 290609
95763 191487
33415 16727
7268 14496
11768 23497
6261 12482
229160 114600
125423 250806
114263 228487
39121 19580
16597 8318
56196 112352
81775 40907
129268 258497
48047 24043
16525 33010
118836...

output:

21

result:

ok single line: '21'

Test #117:

score: 2
Accepted
time: 1880ms
memory: 64696kb

input:

300000 47555 20 10
85793 201771
49365 14072
175087 163257
293254 71137
96418 30434
215168 177212
76848 290622
8163 296487
281972 252186
296151 170649
214588 170735
35406 104857
32795 201951
26479 299251
124069 141132
287994 65733
192747 19487
42244 291234
63598 240315
254716 23884
247129 109235
4767...

output:

1

result:

ok single line: '1'

Extra Test:

score: 0
Extra Test Passed