QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#493050#4583. Concerto de PandemicPetroTarnavskyi#AC ✓266ms63924kbC++202.7kb2024-07-26 19:01:162024-07-26 19:01:16

Judging History

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

  • [2024-07-26 19:01:16]
  • 评测
  • 测评结果:AC
  • 用时:266ms
  • 内存:63924kb
  • [2024-07-26 19:01:16]
  • 提交

answer

#include <bits/stdc++.h>

using namespace std;

#define FOR(i, a, b) for(int i = (a); i < (b); i++)
#define RFOR(i, a, b) for(int i = (a) - 1; i >= (b); i--)
#define SZ(a) int(a.size())
#define ALL(a) a.begin(), a.end()
#define PB push_back
#define MP make_pair
#define F first
#define S second

typedef long long LL;
typedef vector<int> VI;
typedef pair<int, int> PII;
typedef double db;

const int LOG = 18;
const int N = 1 << 18;

int f[N];
int g[LOG][N];
LL cnt[LOG][N];

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	int n, m, k, p;
	cin >> n >> m >> k >> p;
	if (p >= k)
	{
		cout << "0\n";
		return 0;
	}
	VI t(n), fan(n);
	while (m--)
	{
		int c;
		cin >> c;
		c--;
		cin >> t[c];
	}
	FOR(i, 0, k)
	{
		int d;
		cin >> d;
		d--;
		fan[d] = 1;
	}
	vector<LL> dist;
	int firstCity = 0;
	while (t[firstCity] != 0)
		firstCity++;
	VI goodCities = {firstCity};
	LL sum = 0;
	FOR(i, firstCity + 1, n)
	{
		if (t[i] == 0)
		{
			dist.PB(i - goodCities.back() + sum);
			goodCities.PB(i);
			sum = 0;
		}
		else
			sum += t[i];
	}
	FOR(i, 0, firstCity)
		sum += t[i];
	dist.PB(sum + n - goodCities.back() + firstCity);
	VI nextFan(SZ(goodCities));
	int nxtFan = -1;
	RFOR(i, SZ(goodCities), 0)
	{
		int city = goodCities[i];
		nextFan[i] = nxtFan;
		if (fan[city])
			nxtFan = i;
	}
	FOR(i, 0, SZ(goodCities))
		if (nextFan[i] == -1)
			nextFan[i] = nxtFan;
	LL fullCircle = accumulate(ALL(dist), 0LL);
	LL l = 0, r = fullCircle;
	while (r - l > 1)
	{
		LL mid = (l + r) / 2;
		int ptr = 0;
		LL s = 0;
		FOR(i, 0, SZ(goodCities))
		{
			while (ptr < i || s + dist[ptr % SZ(dist)] <= mid)
			{
				s += dist[ptr % SZ(dist)];
				ptr++;
			}
			s -= dist[i];
			f[i] = ptr % SZ(dist);
		}
		FOR(i, 0, SZ(goodCities))
		{
			int concert = f[i];
			int distLeft = concert - i;
			if (distLeft < 0)
				distLeft += SZ(goodCities);
			int distMid = f[concert] - concert;
			if (distMid < 0)
				distMid += SZ(goodCities);
			g[0][i] = nextFan[f[concert]];
			int distRight = g[0][i] - f[concert];
			if (distRight < 0)
				distRight += SZ(goodCities);
			cnt[0][i] = distLeft + distMid + distRight;
		}
		FOR(j, 1, LOG)
		{
			FOR(i, 0, SZ(goodCities))
			{
				g[j][i] = g[j - 1][g[j - 1][i]];
				cnt[j][i] = cnt[j - 1][i] + cnt[j - 1][g[j - 1][i]];
			}
		}
		bool ok = false;
		FOR(i, 0, SZ(goodCities))
		{
			if (!fan[goodCities[i]])
				continue;
			int curIndex = i;
			LL curCnt = 0;
			RFOR(j, LOG, 0)
			{
				if ((p >> j) & 1)
				{
					curCnt += cnt[j][curIndex];
					curIndex = g[j][curIndex];
				}
			}
			if (curCnt >= SZ(goodCities))
			{
				ok = true;
			}
		}
		if (ok)
			r = mid;
		else
			l = mid;
	}
	cout << r << "\n";
	return 0;
}

詳細信息

Test #1:

score: 100
Accepted
time: 3ms
memory: 59080kb

input:

10 4 3 2
1 2
4 4
6 2
7 5
2 5 8

output:

4

result:

ok single line: '4'

Test #2:

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

input:

8 1 3 5
1 5
4 2 7

output:

0

result:

ok single line: '0'

Test #3:

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

input:

5 2 2 1
1 14
2 14
3 5

output:

1

result:

ok single line: '1'

Test #4:

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

input:

2 1 1 1
1 200000
2

output:

0

result:

ok single line: '0'

Test #5:

score: 0
Accepted
time: 130ms
memory: 61764kb

input:

190976 113222 55610 23475
51263 120558
10007 171596
46671 108981
117183 169457
18187 84735
149298 124718
79376 129184
28117 76880
109791 87521
114840 59510
38014 178362
41701 11344
27561 192741
173835 54534
71368 76692
122745 95537
152595 158352
43901 162441
98927 105784
22484 96000
19443 113614
370...

output:

170531

result:

ok single line: '170531'

Test #6:

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

input:

198722 26425 169256 110599
33948 74442
51729 66300
40369 173859
42274 73043
117803 108716
149794 151005
147161 2675
148063 166634
132585 51612
141999 182365
32951 159790
120932 290
82655 150138
49337 10396
171146 129572
33311 193079
195115 171691
180568 77905
65397 110312
156436 149966
9377 55490
12...

output:

1

result:

ok single line: '1'

Test #7:

score: 0
Accepted
time: 83ms
memory: 61328kb

input:

200000 150000 50000 24998
187150 200000
81420 200000
167617 200000
100616 200000
135362 200000
156943 200000
83069 200000
48837 200000
179969 200000
138130 200000
133131 200000
196045 200000
169575 200000
163857 200000
106717 200000
191966 200000
131394 200000
145647 200000
160212 200000
75181 20000...

output:

200002

result:

ok single line: '200002'

Test #8:

score: 0
Accepted
time: 81ms
memory: 59396kb

input:

200000 150000 50000 2
99352 200000
85760 200000
126279 200000
78681 200000
191980 200000
123278 200000
90780 200000
183926 200000
92668 200000
92156 200000
157074 200000
104604 200000
87593 200000
183454 200000
38009 200000
132806 200000
96071 200000
135445 200000
123768 200000
80039 200000
199215 2...

output:

1250012500

result:

ok single line: '1250012500'

Test #9:

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

input:

200000 199999 1 1
44417 200000
47743 200000
134710 200000
118852 200000
9605 200000
150296 200000
80589 200000
3336 200000
66496 200000
90172 200000
190899 200000
3355 200000
107595 200000
111949 200000
146872 200000
72419 200000
115626 200000
127077 200000
173509 200000
194749 200000
109608 200000
...

output:

0

result:

ok single line: '0'

Test #10:

score: 0
Accepted
time: 151ms
memory: 62056kb

input:

200000 100000 100000 25746
186550 200000
85622 200000
21024 200000
59750 200000
76456 200000
87534 200000
76522 200000
103422 200000
165806 200000
138372 200000
166050 200000
176354 200000
15168 200000
69928 200000
187102 200000
130486 200000
182278 200000
161502 200000
95032 200000
119864 200000
17...

output:

400004

result:

ok single line: '400004'

Test #11:

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

input:

200000 199990 10 9
185044 200000
96615 200000
172973 200000
82849 200000
162889 200000
59668 200000
20522 200000
193263 200000
70559 200000
140931 200000
147680 200000
26312 200000
133330 200000
74332 200000
149589 200000
61277 200000
173461 200000
152403 200000
174666 200000
56706 200000
9288 20000...

output:

3865019326

result:

ok single line: '3865019326'

Test #12:

score: 0
Accepted
time: 21ms
memory: 60204kb

input:

200000 199998 2 1
67932 200000
165398 200000
653 200000
12879 200000
179014 200000
173052 200000
19237 200000
31754 200000
83892 200000
67089 200000
172429 200000
20736 200000
19809 200000
195941 200000
165861 200000
192485 200000
50670 200000
154401 200000
183669 200000
160442 200000
96158 200000
4...

output:

19999900000

result:

ok single line: '19999900000'

Test #13:

score: 0
Accepted
time: 87ms
memory: 59412kb

input:

200000 150000 50000 14589
9852 200000
146233 200000
81635 200000
153688 200000
180401 200000
131217 200000
147689 200000
175789 200000
157008 200000
82379 200000
197870 200000
158300 200000
136907 200000
90916 200000
133283 200000
115911 200000
178151 200000
52380 200000
125603 200000
17720 200000
5...

output:

400004

result:

ok single line: '400004'

Test #14:

score: 0
Accepted
time: 77ms
memory: 61336kb

input:

200000 150000 50000 3
92863 200000
143656 200000
177807 200000
82115 200000
127226 200000
153355 200000
195151 200000
183196 200000
56488 200000
105395 200000
174745 200000
9192 200000
122947 200000
102569 200000
71127 200000
198334 200000
140867 200000
91775 200000
176858 200000
78928 200000
116317...

output:

1666816667

result:

ok single line: '1666816667'

Test #15:

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

input:

10 2 2 4
1 45
9 45
5 6

output:

0

result:

ok single line: '0'

Test #16:

score: 0
Accepted
time: 58ms
memory: 58656kb

input:

184056 156924 27132 5487
31071 76922
182522 95921
153369 55991
171710 52252
41681 88855
80541 147855
17375 23664
166681 99712
85334 139650
91006 107711
183992 133132
18219 116694
10973 36327
29655 3541
9566 121602
20135 150626
165572 199426
34139 114077
172106 9046
111675 183349
52859 2653
162895 48...

output:

1391357

result:

ok single line: '1391357'

Test #17:

score: 0
Accepted
time: 190ms
memory: 62328kb

input:

198946 85509 113437 16454
55928 11746
151106 176741
67787 119235
6964 121879
87064 105123
182446 67770
148232 164626
84669 181152
177124 116910
124895 83907
65566 65423
153714 197476
67769 108011
8201 139194
91192 80237
84858 168819
73079 185222
55701 151129
60694 17931
179882 117777
154826 119669
1...

output:

251741

result:

ok single line: '251741'

Test #18:

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

input:

184845 184844 1 1
159765 128047
129626 3304
35698 88302
142782 113626
46033 196503
94300 101851
148700 52627
101827 122109
34448 104944
94260 154823
32130 48872
72954 199176
50529 151953
53369 38890
35837 195530
107050 68183
105336 41797
127928 74999
144029 51097
16189 75339
119777 179826
94102 1624...

output:

0

result:

ok single line: '0'

Test #19:

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

input:

183091 183090 1 1
12308 23858
135357 5256
150368 37499
118187 37965
54415 24892
125817 38590
81315 186626
13463 164488
136540 24565
145451 98230
130596 163280
80257 160167
131667 188684
43557 68858
77488 104306
25073 144258
104735 157480
23991 28887
67302 68251
127993 120450
93683 52143
127786 13219...

output:

0

result:

ok single line: '0'

Test #20:

score: 0
Accepted
time: 21ms
memory: 59916kb

input:

185561 185559 2 1
97801 136363
66008 136066
173944 59291
84394 162605
136281 88025
155011 701
184637 86732
87309 98378
70530 162334
162566 153674
158032 185895
127014 172074
65742 28387
102936 28533
84549 125060
652 51442
70185 182692
1996 112759
101772 21021
34755 15804
92317 146543
97125 153712
13...

output:

1579892162

result:

ok single line: '1579892162'

Test #21:

score: 0
Accepted
time: 20ms
memory: 57876kb

input:

183182 183180 2 1
63223 3168
141520 69479
102948 133687
168811 61676
1040 131270
96738 46087
44583 80530
34917 198354
143916 73083
90118 136430
143264 19353
102753 197144
4376 71023
132710 140871
61456 141299
39456 46272
36213 130567
156330 173816
154675 195443
14550 106176
147487 91753
77544 28222
...

output:

7692313709

result:

ok single line: '7692313709'

Test #22:

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

input:

195431 195367 64 30
36156 60535
180283 153306
192146 194701
124139 127831
76060 17748
148550 69471
69448 1188
179162 186722
188498 44999
11250 67523
27826 144158
191515 18496
127589 12954
127966 24839
9285 26855
110964 28073
167740 98491
65303 92934
162830 75852
64299 156312
61352 100260
172221 7723...

output:

287022566

result:

ok single line: '287022566'

Test #23:

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

input:

195507 195443 64 28
107028 104100
106907 193032
45258 195130
168641 198440
90592 198719
31617 88887
72796 79245
41191 20722
53917 159740
34173 21748
127611 171540
186506 92330
189538 141942
41574 122048
69615 93751
59046 89045
176461 111632
74703 8471
5065 42899
1888 179533
150575 88597
72116 37233
...

output:

302878794

result:

ok single line: '302878794'

Test #24:

score: 0
Accepted
time: 15ms
memory: 59968kb

input:

184543 183830 713 203
108924 161080
101919 104871
50685 182714
52699 74184
180944 142023
55277 4859
4461 153623
141162 149967
8865 72164
148155 80178
10817 75920
2978 41235
7205 55147
13738 2734
171075 142707
115453 95060
31261 172373
86949 71831
32714 5579
53948 168389
485 99005
121956 131933
11897...

output:

42317159

result:

ok single line: '42317159'

Test #25:

score: 0
Accepted
time: 15ms
memory: 59904kb

input:

189799 189086 713 111
41639 177678
133461 10900
13692 152687
185198 182955
17643 5391
139287 15315
99971 126465
30778 73425
144220 183083
102181 95818
4416 13181
67758 117233
17022 49027
156528 184034
150532 173950
60128 35969
143614 82248
162094 92672
94051 127859
19768 130931
50065 62212
28095 132...

output:

81374116

result:

ok single line: '81374116'

Test #26:

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

input:

4 2 2 1
1 2
3 2
2 4

output:

4

result:

ok single line: '4'

Test #27:

score: 0
Accepted
time: 25ms
memory: 59980kb

input:

182652 180020 2632 427
148103 28327
118881 143601
66544 93306
98324 88713
111079 141633
137208 24194
94888 188951
272 70612
118701 128800
67012 121878
32737 133925
161758 101003
57546 68806
112070 90206
103631 170676
132438 78285
112805 166403
45911 172555
145479 96958
159030 100240
30297 89145
7512...

output:

20954707

result:

ok single line: '20954707'

Test #28:

score: 0
Accepted
time: 23ms
memory: 58164kb

input:

198844 196212 2632 735
78461 167318
118429 157481
141228 199462
168970 120477
48125 87282
88870 190003
24595 22332
33767 186866
142932 36313
113726 46047
138880 51749
42038 193616
12754 154506
144684 13867
33847 20778
2628 78074
152674 44161
136007 140434
6442 183542
176716 151126
124899 93285
9788 ...

output:

12810308

result:

ok single line: '12810308'

Test #29:

score: 0
Accepted
time: 124ms
memory: 59748kb

input:

189610 119689 69921 5991
164960 7372
178298 92501
49043 122790
4949 141312
6688 19818
110244 53106
37455 147574
187994 134897
176097 166967
45890 169799
102327 118838
7199 109268
29167 66183
156290 196754
175268 121900
56409 80971
117030 34287
16346 33801
111951 467
86336 90748
120982 145426
155859 ...

output:

995854

result:

ok single line: '995854'

Test #30:

score: 0
Accepted
time: 126ms
memory: 61160kb

input:

181153 111232 69921 14891
61153 187956
81419 72744
80967 100067
128595 124185
38436 112881
66913 26052
156254 67588
87223 83823
47660 106990
4479 21237
129684 86007
134966 169981
25178 57652
90184 42558
116245 167189
136200 70697
19251 43067
11523 54079
58693 148387
113897 82626
130603 25056
84720 1...

output:

352086

result:

ok single line: '352086'

Test #31:

score: 0
Accepted
time: 120ms
memory: 61636kb

input:

187670 121624 66046 40220
85947 180988
142838 38976
77666 147901
166637 51007
147090 37075
158080 56050
124234 190040
18136 4422
170815 139856
56047 88348
61317 108670
177199 39817
47663 155319
99556 189269
7659 48517
135859 129790
73269 95600
15591 1249
89545 92438
143046 180286
1593 71318
16779 12...

output:

32418

result:

ok single line: '32418'

Test #32:

score: 0
Accepted
time: 182ms
memory: 61996kb

input:

185665 76666 108999 102379
82751 129276
170767 6258
51779 92897
4415 105658
51875 194398
12614 116050
1457 58872
184476 178587
72266 40479
112888 174833
128404 132114
176724 157832
100491 163419
106710 103082
9479 37696
77430 111356
35587 29434
4861 140402
145375 50650
28288 163050
119709 160000
183...

output:

1

result:

ok single line: '1'

Test #33:

score: 0
Accepted
time: 165ms
memory: 61700kb

input:

180016 82053 97963 45780
44951 129698
5995 40353
137012 45586
61149 141943
118870 129916
129797 16588
37808 107029
169839 182878
113777 65601
11 96478
4513 164369
75569 65964
78575 180841
37756 59222
155499 35167
6636 165955
105326 41660
157174 28809
38040 22098
127757 126029
168370 50812
84664 1595...

output:

3

result:

ok single line: '3'

Test #34:

score: 0
Accepted
time: 128ms
memory: 61624kb

input:

186895 112521 74374 1
177659 27707
75115 2987
16384 36906
129595 166103
7346 143245
59382 114280
186691 84440
13076 78300
161731 23662
32098 31484
90029 119182
179235 126045
147032 185998
173318 161230
18246 65427
53887 134126
50968 132426
114943 18662
148085 99748
65603 94694
110581 191032
159157 1...

output:

5631712881

result:

ok single line: '5631712881'

Test #35:

score: 0
Accepted
time: 132ms
memory: 60544kb

input:

188057 108632 79425 1
140591 156066
59647 162012
27155 94742
167179 163620
24004 179694
92719 111005
150571 147125
127710 608
155395 15348
86913 53339
50854 75946
164930 192216
136259 163149
174016 107270
121563 130578
19510 8438
99655 105867
7364 160771
16632 70208
58443 129384
28577 167023
99311 5...

output:

5444327782

result:

ok single line: '5444327782'

Test #36:

score: 0
Accepted
time: 137ms
memory: 60124kb

input:

199541 119827 79714 1
92851 147568
64441 107207
71295 56456
52919 30325
184051 91939
30124 85079
189945 169846
116558 61714
128741 107150
64360 114408
99127 2471
94092 93892
2192 113465
11424 113980
104251 125804
38491 161533
105136 195145
63287 82599
122362 177289
196114 19491
40967 87051
53634 126...

output:

5995603335

result:

ok single line: '5995603335'

Test #37:

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

input:

6 2 2 1
1 3
4 3
2 5

output:

5

result:

ok single line: '5'

Test #38:

score: 0
Accepted
time: 151ms
memory: 61920kb

input:

191163 99320 91843 2
165037 156055
112018 137
175134 89405
65043 21227
30731 10359
23978 150270
161318 170752
12454 88498
128029 108548
33878 17260
110936 93589
75638 137826
138829 192467
112763 160262
152908 52175
62955 175247
44257 108483
121519 122251
18785 153893
118176 59652
105159 124252
17818...

output:

2484259320

result:

ok single line: '2484259320'

Test #39:

score: 0
Accepted
time: 143ms
memory: 61704kb

input:

185059 96150 88909 2
143135 120045
52102 25926
151556 47121
44098 154863
135618 139419
10757 146976
96319 149003
135264 145046
3329 100450
88416 195923
110380 118066
106356 10892
19864 158807
154613 145957
64190 33585
78063 30301
9798 3863
31917 46416
171920 49144
146756 108219
172974 34258
99913 18...

output:

2399521505

result:

ok single line: '2399521505'

Test #40:

score: 0
Accepted
time: 190ms
memory: 61628kb

input:

193167 64435 128732 2
111238 64095
76668 75649
130313 95115
74357 28304
94279 73602
124270 184099
35068 182875
83498 168797
11614 104972
69950 95063
136213 131063
2658 126739
159162 198908
178265 53771
130229 35882
50257 150170
28047 189484
160117 137135
80026 175456
35298 40883
51181 100936
4484 13...

output:

1611488935

result:

ok single line: '1611488935'

Test #41:

score: 0
Accepted
time: 191ms
memory: 62364kb

input:

195828 77975 117853 17
16821 189080
58397 74614
99575 197415
25159 13746
80530 188647
153482 14446
72931 85317
89466 186789
52023 174809
38000 190985
185801 157349
140089 21566
169161 176786
193236 125463
161687 74472
54728 187865
173339 161446
154937 154232
81285 15190
73474 27612
187038 80531
4221...

output:

228980136

result:

ok single line: '228980136'

Test #42:

score: 0
Accepted
time: 161ms
memory: 60724kb

input:

193850 95749 98101 17
192865 121309
155387 40102
50456 113134
95770 96316
58617 19920
97813 51659
135905 133409
66772 9433
103156 100149
189590 189503
144831 172066
126703 119045
192631 39571
180119 145834
48504 24259
134122 52517
31222 135424
150136 31698
26476 99848
66444 9426
109658 86304
34781 1...

output:

281712105

result:

ok single line: '281712105'

Test #43:

score: 0
Accepted
time: 144ms
memory: 60332kb

input:

184005 95030 88975 17
166190 154934
97423 98252
857 34130
165435 101574
161874 124144
123097 169487
50451 3805
153411 13337
34860 120686
2745 129877
164947 102446
117590 118938
58990 68874
72636 199348
66283 1925
178462 30838
7047 11286
133479 173128
23979 106110
46778 36828
116717 87938
148667 6200...

output:

280225664

result:

ok single line: '280225664'

Test #44:

score: 0
Accepted
time: 108ms
memory: 61356kb

input:

183418 120752 62666 55
109248 28544
39534 76648
60373 107381
10014 74487
118694 75970
95994 111836
143187 189435
40796 37708
39928 124712
2173 40512
122845 20920
13111 182042
108888 61465
122567 93551
143958 125873
96465 58431
169981 8964
136560 10265
31804 58467
45946 33999
28410 33071
155917 34027...

output:

109996135

result:

ok single line: '109996135'

Test #45:

score: 0
Accepted
time: 196ms
memory: 61468kb

input:

191054 66306 124748 55
36375 130965
84941 51392
180666 196201
42895 169066
144783 193876
86555 97765
33083 79036
8566 36471
95840 77077
164908 109929
161956 151550
57151 85099
26503 184099
127392 170377
83224 107970
93336 2039
164670 6736
105723 81904
47701 115683
166044 35050
65998 39514
43577 8370...

output:

60449325

result:

ok single line: '60449325'

Test #46:

score: 0
Accepted
time: 113ms
memory: 61708kb

input:

186863 113085 73778 55
5331 181392
156366 87291
21226 63213
119238 47590
19587 13580
132363 38
1931 150489
118174 165340
173210 106577
171178 84482
91324 76976
40320 176970
140545 11435
140095 75864
182076 40566
114115 97555
146912 115110
119656 181754
28860 47010
182619 114559
173537 6686
129493 70...

output:

102689221

result:

ok single line: '102689221'

Test #47:

score: 0
Accepted
time: 147ms
memory: 62004kb

input:

186138 95396 90742 145
5188 20955
152391 71943
179174 169627
101910 6961
99898 193627
156454 65430
49616 74677
5349 22197
130782 194962
172710 174763
34066 5776
23607 138884
146853 56530
171991 93308
100979 92282
158311 156663
54106 169002
99256 39121
125792 80396
45797 76575
67921 85107
110179 8146...

output:

32939180

result:

ok single line: '32939180'

Test #48:

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

input:

10 2 4 2
4 22
9 43
5 7 1 3

output:

1

result:

ok single line: '1'

Test #49:

score: 0
Accepted
time: 120ms
memory: 60204kb

input:

199656 123674 75982 145
21533 29603
113912 7637
112345 70308
124617 198709
64655 17034
88628 146372
105929 17530
149735 120159
15844 82110
136455 160303
59633 54459
170682 56809
192650 79539
102718 156896
126008 62929
145785 155077
182604 81934
188079 129665
35327 66681
26624 138353
167084 29182
706...

output:

42569301

result:

ok single line: '42569301'

Test #50:

score: 0
Accepted
time: 141ms
memory: 61936kb

input:

181121 92921 88200 145
142310 49571
80829 40449
155139 196435
119390 35775
172760 156591
79441 17877
156191 183387
5877 169914
132354 30445
73967 91675
19110 135972
78974 159837
73774 183000
78241 124857
38464 188565
67157 892
30531 17096
150523 34505
137878 95214
80068 181799
14006 63797
170654 146...

output:

32018154

result:

ok single line: '32018154'

Test #51:

score: 0
Accepted
time: 156ms
memory: 60656kb

input:

182046 83315 98731 333
20103 34600
112185 32101
156629 48683
31662 184928
53736 29611
4897 94296
118743 121643
123095 91055
45453 11731
137949 196163
6382 64483
68929 158551
103172 161554
85477 121051
67524 106858
111457 188853
87463 31542
84354 7445
87267 63545
153837 26967
47467 174716
14232 44750...

output:

12487339

result:

ok single line: '12487339'

Test #52:

score: 0
Accepted
time: 194ms
memory: 62348kb

input:

198444 77854 120590 333
62591 165704
133844 5125
45016 171923
183836 94756
125830 141875
33597 110403
105841 36388
9104 53744
178524 134175
128727 83738
80116 52827
50253 137373
171022 140732
71285 143094
96424 120073
169044 54863
109815 145142
198114 163188
116652 189692
164294 23243
48598 41277
34...

output:

11682996

result:

ok single line: '11682996'

Test #53:

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

input:

189882 75574 114308 333
691 162698
189300 121028
140021 39606
105260 57722
136734 136602
187005 174604
138935 88069
127073 47889
105203 192752
88147 87581
120603 110665
44996 109496
114971 141224
109799 51188
8783 191398
73653 104576
117443 79133
74347 133743
186826 4426
89629 121421
140901 106475
3...

output:

11300831

result:

ok single line: '11300831'

Test #54:

score: 0
Accepted
time: 149ms
memory: 61944kb

input:

194340 115121 79219 1874
191686 91554
130936 72846
163370 24244
69072 87360
99682 74587
149552 37205
80765 163309
58366 11045
111057 35489
60998 24329
101211 781
157117 136975
130489 192317
96452 106641
146807 9211
193602 38825
42787 166288
14379 5976
173408 57819
75944 109407
11284 147584
39410 139...

output:

3067668

result:

ok single line: '3067668'

Test #55:

score: 0
Accepted
time: 203ms
memory: 62988kb

input:

195301 71183 124118 1874
85262 151516
49345 178464
108980 178761
170865 177628
119536 70487
183234 66734
84315 137824
177991 191737
157131 150497
146729 163715
29565 87952
16273 163943
157673 192028
48659 161777
164104 37997
167394 52149
49100 5837
103348 109318
184216 64078
64408 23909
42687 48118
...

output:

1900949

result:

ok single line: '1900949'

Test #56:

score: 0
Accepted
time: 143ms
memory: 61592kb

input:

181439 99249 82190 1874
12974 2306
173466 52124
152737 129353
21404 52710
48158 195745
107279 106834
98442 89411
162166 54975
150529 58892
135650 846
161769 85466
108244 1973
157021 138892
134574 1262
175245 54376
44430 10923
133785 69596
92229 41925
14639 45423
132892 192299
6071 91595
136988 11414...

output:

2652052

result:

ok single line: '2652052'

Test #57:

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

input:

10 5 5 2
2 4
4 5
6 8
8 5
10 4
1 3 5 7 9

output:

7

result:

ok single line: '7'

Test #58:

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

input:

11 5 5 2
2 4
4 5
6 8
8 5
10 4
1 3 5 7 9

output:

7

result:

ok single line: '7'

Test #59:

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

input:

200000 199998 2 1
44159 200000
25721 200000
120282 200000
184009 200000
147724 200000
50203 200000
18450 200000
123126 200000
27117 200000
173400 200000
49103 200000
182408 200000
363 200000
155535 200000
100097 200000
151461 200000
171242 200000
116841 200000
107770 200000
143114 200000
73601 20000...

output:

19999900000

result:

ok single line: '19999900000'

Test #60:

score: 0
Accepted
time: 127ms
memory: 63924kb

input:

200000 5 5 2
2 200000
10 200000
11 200000
14 200000
18 200000
199994 199997 1 13 16

output:

200002

result:

ok single line: '200002'