QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#485578#4938. Writing TasksPetroTarnavskyiAC ✓230ms63944kbC++143.1kb2024-07-20 20:13:432024-07-20 20:13:46

Judging History

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

  • [2024-07-20 20:13:46]
  • 评测
  • 测评结果:AC
  • 用时:230ms
  • 内存:63944kb
  • [2024-07-20 20:13:43]
  • 提交

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;

mt19937 rng;

struct Graph
{
	int szL, szR;
	
	vector<VI> g;
	VI mateForR, mateForL, usedL;
	
	void init(int L, int R)
	{
		szL = L, szR = R;
		g.resize(szL);
		mateForL.resize(szL);
		usedL.resize(szL);
		
		mateForR.resize(szR);
	}
	
	void addEdge(int from, int to)
	{
		assert(0 <= from && from < szL);
		assert(0 <= to && to < szR);
		
		g[from].PB(to);
	}
	
	int iter;
	
	bool kuhn(int v)
	{
		if (usedL[v] == iter) return false;
		usedL[v] = iter;
		shuffle(ALL(g[v]), rng);
		for (int to : g[v])
		{
			if (mateForR[to] == -1)
			{
				mateForR[to] = v;
				mateForL[v] = to;
				return true;
			}
		}
		for (int to : g[v])
		{
			if (kuhn(mateForR[to]))
			{
				mateForR[to] = v;
				mateForL[v] = to;
				return true;
			}
		}
		return false;
	}
	
	int doKuhn()
	{
		fill(ALL(mateForR), -1);
		fill(ALL(mateForL), -1);
		fill(ALL(usedL), -1);
		
		int res = 0;
		iter = 0;
		while (true)
		{
			iter++;
			bool ok = false;
			FOR (v, 0, szL)
			{
				if (mateForL[v] == -1)
				{
					if (kuhn(v))
					{
						ok = true;
						res++;
					}
				}
			}
			if (!ok)
				break;
		}
		return res;
	}
};

const int N = 200'447;

VI g[N];

int used[N];
bool ok = 1;

int col[N];
void dfs(int v)
{
	used[v] = 1;
	for(int to : g[v])
	{
		if(used[to])
		{
			if(col[to] == col[v])
				ok = 0;
		}
		else
		{
			col[to] = col[v] ^ 1;
			dfs(to);
		}
	}
}



int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	
	int a, c, t;
	cin >> a >> c >> t;
	
	FOR (i, 0, a)
	{
		int l;
		cin >> l;
		FOR (j, 0, l)
		{
			int x;
			cin >> x;
			g[i].PB(a + x - 1);
		}
	}
	FOR (i, 0, a)
	{
		int l;
		cin >> l;
		FOR (j, 0, l)
		{
			int x;
			cin >> x;
			g[i].PB(a + c + x - 1);
		}
	}
	
	FOR (i, 0, c)
	{
		int l;
		cin >> l;
		FOR (j, 0, l)
		{
			int x;
			cin >> x;
			g[a + i].PB(a + c + x - 1);
		}
	}
	
	map<PII, VI> m;
	
	int cnt = 0;
	
	FOR (i, 0, a)
	{
		set<int> susids;
		for (auto to : g[i])
			susids.insert(to);
		for (auto u : g[i])
		{
			for (auto v : g[u])
			{
				if (!susids.count(v))
					continue;
				m[{i, u}].PB(cnt);
				m[{i, v}].PB(cnt);
				m[{u, v}].PB(cnt);
				cnt++;
			}
		}
	}
	FOR(i, 0, a + c + t)
		g[i].clear();
	
	Graph G;
	G.init(cnt, cnt);
	for (auto [p, v] : m)
	{
		assert(SZ(v) <= 2);
		if (SZ(v) == 2)
		{
			G.addEdge(v[0], v[1]);
			G.addEdge(v[1], v[0]);
			
			g[v[0]].PB(v[1]);
			g[v[1]].PB(v[0]);
		}
	}
	int num = 0;
	FOR(i, 0, cnt)
	{
		if(used[i])
			continue;
		ok = 1;
		dfs(i);
		if(!ok)
			num++;
	}
	int ans = cnt - G.doKuhn() / 2;
	ans -= (num + 1) / 2;
	
	cout << ans << '\n';
	
	
	
	return 0;
}

詳細信息

Test #1:

score: 100
Accepted
time: 0ms
memory: 9484kb

input:

2 3 2
2 1 2
2 2 3
1 1
1 1
1 1
1 1
1 2

output:

2

result:

ok single line: '2'

Test #2:

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

input:

2 2 2
0
1 2
0
2 1 2
2 1 2
0

output:

0

result:

ok single line: '0'

Test #3:

score: 0
Accepted
time: 171ms
memory: 50448kb

input:

40623 39265 42226
2 14643 37432
2 29610 20181
2 6441 7614
2 17559 3238
2 39001 17644
2 6431 37097
2 6347 12246
2 1130 1688
2 38583 9078
2 8746 27832
2 13090 39048
2 32647 18777
2 27505 19277
2 31201 25824
2 6133 20344
2 11625 20997
2 18528 35730
0
2 22986 5273
2 10942 38791
2 19025 35679
2 32321 124...

output:

78528

result:

ok single line: '78528'

Test #4:

score: 0
Accepted
time: 163ms
memory: 50596kb

input:

41022 39421 42288
2 26413 2168
2 24182 14199
2 18798 17846
2 3398 19624
2 16796 33998
2 7209 25883
2 26356 13537
2 56 30294
2 34909 20218
2 29727 22116
2 16349 1704
2 9254 18036
2 16197 16096
2 21562 31470
2 14773 10518
2 38025 12573
2 15509 32276
2 9613 12321
2 19146 11395
2 7186 36431
0
2 10098 22...

output:

78840

result:

ok single line: '78840'

Test #5:

score: 0
Accepted
time: 186ms
memory: 55252kb

input:

49395 43808 45888
2 13031 11323
2 41375 4393
2 32137 17908
2 29053 42691
0
2 38335 30970
2 38318 43773
2 22999 22444
0
2 39248 30837
0
2 29807 2360
2 29363 3536
2 8515 41137
2 7890 31441
0
2 31070 6987
2 24295 15517
2 14204 13069
2 32996 40146
2 38164 1478
2 40032 19143
0
2 18430 24119
2 37845 33290...

output:

87616

result:

ok single line: '87616'

Test #6:

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

input:

3 4 3
1 2
2 4 2
2 1 3
1 1
2 2 3
2 3 2
1 3
2 1 3
1 2
1 2

output:

5

result:

ok single line: '5'

Test #7:

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

input:

15 17 18
1 12
2 13 4
2 2 6
2 11 14
2 7 3
2 17 11
2 4 8
2 5 1
1 1
1 16
1 3
2 10 16
1 8
2 15 5
1 6
2 6 1
2 7 3
1 13
2 12 9
2 8 18
1 9
2 1 15
2 5 13
2 18 14
2 15 7
1 4
2 10 2
1 2
1 17
2 14 17
1 18
1 13
1 4
1 1
1 5
2 14 3
2 8 16
2 2 16
1 10
1 10
2 12 14
1 6
2 7 15
2 6 3
2 17 12
1 15
1 9

output:

15

result:

ok single line: '15'

Test #8:

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

input:

769 869 792
1 254
2 210 794
1 863
2 40 403
2 279 773
2 54 328
2 196 473
1 804
1 261
1 174
1 219
1 22
1 429
1 195
2 769 100
1 33
1 457
1 604
2 473 714
2 423 227
2 453 654
1 864
2 220 243
2 520 321
2 421 805
2 721 11
2 216 793
1 360
1 169
2 121 613
2 714 594
1 692
2 642 607
2 538 781
2 800 387
2 494 5...

output:

769

result:

ok single line: '769'

Test #9:

score: 0
Accepted
time: 51ms
memory: 24824kb

input:

46352 41211 38602
2 11300 5679
2 2876 4114
2 28525 6628
1 23785
1 30940
1 26982
1 8056
1 13748
2 25254 21974
1 3446
2 2294 13453
0
1 16724
2 36970 18406
2 7688 17413
1 25901
1 39238
1 16098
1 29911
2 15113 849
1 31293
2 32195 13287
0
1 12670
2 40732 19567
2 24195 23787
1 40913
2 18820 10009
0
0
2 23...

output:

38602

result:

ok single line: '38602'

Test #10:

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

input:

3 4 3
1 4
2 1 3
2 3 4
2 1 2
2 3 1
1 2
1 3
0
1 2
2 1 2

output:

3

result:

ok single line: '3'

Test #11:

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

input:

15 15 20
2 12 14
2 1 3
1 11
2 5 13
2 8 9
1 13
1 9
2 15 11
2 3 6
2 6 7
1 10
1 2
2 7 12
1 14
1 4
1 3
1 1
2 12 20
2 18 2
2 10 15
2 2 10
2 15 18
2 17 3
2 6 7
2 16 17
1 19
2 13 6
1 14
2 4 11
2 8 16
2 1 4
1 13
2 6 1
1 8
1 18
2 16 7
1 14
2 10 11
2 15 19
2 19 18
1 12
1 3
1 2
2 4 16
2 17 15

output:

16

result:

ok single line: '16'

Test #12:

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

input:

942 753 814
2 429 543
1 228
1 442
0
0
2 215 635
1 199
2 735 727
1 335
2 56 209
2 668 570
2 748 190
2 719 571
0
1 650
1 468
1 646
2 150 547
2 551 53
0
1 203
0
2 544 664
1 100
2 388 321
1 94
1 77
2 535 253
1 306
0
2 753 342
2 690 529
2 204 712
2 621 693
1 253
1 549
2 712 639
2 43 323
2 206 585
2 82 45...

output:

753

result:

ok single line: '753'

Test #13:

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

input:

15 20 16
2 8 7
2 7 13
2 11 20
2 4 9
2 18 6
2 10 13
2 11 5
2 10 3
2 8 1
2 12 5
2 9 2
2 17 3
2 20 1
2 17 18
2 16 19
2 4 12
2 7 6
2 11 13
2 8 3
2 7 3
2 11 14
1 9
2 5 2
2 6 13
2 15 1
2 14 1
2 15 2
2 9 10
2 12 5
2 8 4
2 9 8
2 9 6
2 7 16
2 14 10
2 10 8
2 1 13
1 15
1 16
2 11 5
2 11 12
2 14 3
0
2 4 13
2 7 1...

output:

5

result:

ok single line: '5'

Test #14:

score: 0
Accepted
time: 52ms
memory: 26852kb

input:

48398 47836 40164
2 18023 23816
0
0
1 14256
1 47537
2 40419 28208
2 24335 20756
2 11563 31099
2 11298 27901
1 43928
1 4795
2 33599 41395
1 40893
2 24858 20153
1 16524
2 73 9844
2 18804 12559
1 47263
1 36093
2 19492 7210
2 10991 38704
2 44074 26169
1 9493
2 23707 40251
1 19203
2 14974 45727
1 15661
2...

output:

40164

result:

ok single line: '40164'

Test #15:

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

input:

4 5 4
2 2 4
1 3
1 4
2 1 3
1 2
1 4
2 1 3
2 3 4
2 3 1
2 2 3
1 4
1 1
0

output:

4

result:

ok single line: '4'

Test #16:

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

input:

19 20 20
1 16
2 10 7
1 13
2 11 2
1 8
1 7
2 20 17
2 5 13
1 2
2 6 8
2 3 15
2 9 5
1 4
1 18
2 19 1
2 12 1
2 14 19
2 17 11
1 15
1 8
1 10
1 13
2 17 1
2 20 4
2 16 6
2 4 9
1 14
1 5
1 7
1 18
1 15
1 1
2 6 11
2 2 16
2 9 14
2 3 17
1 19
1 12
0
1 5
1 18
2 1 8
2 14 12
2 7 2
1 16
2 20 5
2 15 11
2 10 13
2 17 1
2 9 4...

output:

19

result:

ok single line: '19'

Test #17:

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

input:

858 936 831
1 78
2 132 126
0
2 761 378
1 914
1 36
2 884 480
2 344 531
2 718 395
2 30 270
2 503 495
2 717 520
1 833
2 483 636
1 498
2 181 250
2 538 311
0
2 246 552
1 201
2 598 595
2 672 747
2 823 508
2 429 369
1 705
2 929 659
1 866
2 423 31
2 425 921
2 422 313
2 927 726
1 194
2 553 919
2 733 323
1 12...

output:

831

result:

ok single line: '831'

Test #18:

score: 0
Accepted
time: 57ms
memory: 27480kb

input:

49781 42895 45291
1 29407
1 9103
2 5324 6026
1 31374
2 5841 29212
2 23318 30169
0
2 25579 21864
1 32335
2 23800 806
2 25593 11060
2 15157 69
1 34355
2 2925 14080
2 33167 18126
2 7104 5549
2 40443 5056
2 28415 696
1 4790
1 7018
2 3471 21650
2 2916 40765
1 34240
2 42308 18364
1 38483
0
2 1698 11488
1 ...

output:

42895

result:

ok single line: '42895'

Test #19:

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

input:

2 2 2
1 2
2 2 1
1 1
2 1 2
2 1 2
1 1

output:

2

result:

ok single line: '2'

Test #20:

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

input:

2 2 2
1 2
2 2 1
1 2
2 2 1
2 2 1
1 2

output:

2

result:

ok single line: '2'

Test #21:

score: 0
Accepted
time: 69ms
memory: 29288kb

input:

19293 19293 19293
2 15559 6355
2 18678 12383
2 10518 2914
2 9321 5480
2 2515 9636
2 348 6411
2 8068 5686
2 13171 5869
2 3983 3883
2 11207 18235
2 6332 13692
2 9259 8353
2 18013 1039
2 14419 10593
2 14504 3897
2 3936 12241
2 7111 14415
2 9387 11892
2 6697 4039
2 8091 9046
2 4286 14361
2 17222 5305
2 ...

output:

28939

result:

ok single line: '28939'

Test #22:

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

input:

20 20 20
1 1
2 1 2
2 2 3
2 3 4
2 4 5
1 6
2 6 7
2 7 8
2 8 9
2 9 10
1 11
2 11 12
2 12 13
2 13 14
2 14 15
2 15 16
0
0
0
0
1 1
2 1 2
2 2 3
2 3 4
2 4 5
1 6
2 6 7
2 7 8
2 8 9
2 9 10
1 11
2 11 12
2 12 13
2 13 14
2 14 15
2 15 16
0
0
0
0
1 1
2 1 2
2 2 3
2 3 4
2 4 5
1 6
2 6 7
2 7 8
2 8 9
2 9 10
1 11
2 11 12
2...

output:

22

result:

ok single line: '22'

Test #23:

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

input:

1000 1000 1000
1 1
2 1 2
2 2 3
2 3 4
2 4 5
2 5 6
2 6 7
2 7 8
2 8 9
2 9 10
2 10 11
2 11 12
2 12 13
2 13 14
2 14 15
2 15 16
2 16 17
2 17 18
2 18 19
2 19 20
2 20 21
1 22
2 22 23
2 23 24
2 24 25
2 25 26
2 26 27
2 27 28
2 28 29
2 29 30
2 30 31
2 31 32
2 32 33
2 33 34
2 34 35
2 35 36
2 36 37
2 37 38
2 38 ...

output:

1292

result:

ok single line: '1292'

Test #24:

score: 0
Accepted
time: 28ms
memory: 12344kb

input:

42099 49103 43206
2 2436 21573
2 9996 23380
2 18655 46120
2 12927 46150
2 40795 5903
2 21860 35021
2 35508 10085
2 15704 5818
2 4284 22266
2 21850 28412
2 25375 24412
2 5997 38671
2 14067 26688
2 29986 225
2 8819 39574
2 28550 12704
2 6055 4336
2 14012 21939
2 13223 10017
2 36352 23453
2 41234 13597...

output:

6

result:

ok single line: '6'

Test #25:

score: 0
Accepted
time: 104ms
memory: 50348kb

input:

50000 50000 50000
1 1
2 1 2
2 2 3
2 3 4
2 4 5
2 5 6
2 6 7
2 7 8
2 8 9
2 9 10
2 10 11
2 11 12
2 12 13
2 13 14
2 14 15
2 15 16
2 16 17
2 17 18
2 18 19
2 19 20
2 20 21
2 21 22
2 22 23
2 23 24
2 24 25
2 25 26
2 26 27
2 27 28
2 28 29
2 29 30
2 30 31
2 31 32
2 32 33
2 33 34
2 34 35
2 35 36
2 36 37
2 37 38...

output:

65098

result:

ok single line: '65098'

Test #26:

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

input:

797 781 965
2 542 265
2 613 195
2 483 758
2 387 62
2 9 45
2 146 38
2 305 457
2 374 18
2 776 273
2 475 432
2 691 108
2 264 284
2 70 598
2 741 673
2 393 480
2 250 145
2 740 748
2 35 221
2 442 229
2 204 326
2 304 538
2 721 685
2 58 778
2 51 740
2 750 227
2 25 389
2 142 462
2 557 370
2 30 147
2 28 300
2...

output:

960

result:

ok single line: '960'

Test #27:

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

input:

48703 42977 49346
2 8620 24764
2 14087 32876
0
2 8945 5627
2 41296 34519
0
2 29062 5131
2 816 1371
2 29401 1787
0
2 10358 19458
2 611 26890
2 32600 33419
2 7484 25258
2 18804 27934
2 40145 24038
2 10559 8176
2 17733 7525
2 12422 37383
2 1438 41231
2 40252 30643
0
0
2 6532 38724
2 19246 9753
2 19848 ...

output:

56108

result:

ok single line: '56108'

Test #28:

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

input:

802 787 751
2 138 295
2 572 302
2 575 580
2 556 248
2 642 441
2 638 379
2 650 79
2 397 313
2 464 757
2 753 483
2 461 61
2 506 367
2 582 62
2 350 616
2 19 284
2 196 658
2 483 683
2 588 526
2 106 333
2 478 23
2 640 442
2 781 525
2 362 193
2 323 691
2 648 627
2 784 355
2 399 51
2 662 105
2 107 53
2 417...

output:

928

result:

ok single line: '928'

Test #29:

score: 0
Accepted
time: 134ms
memory: 43512kb

input:

41866 41104 47356
2 14498 27153
2 11889 11501
2 24507 26825
2 9375 38374
2 36646 26596
2 27810 2781
2 18125 31616
2 28814 7751
2 3726 32390
2 24020 9158
2 23175 26847
2 30193 20375
2 33609 14680
2 12657 26318
2 36465 1173
2 40844 30906
0
2 17851 11228
2 15337 33580
0
2 35061 16536
2 1967 3490
2 1256...

output:

54184

result:

ok single line: '54184'

Test #30:

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

input:

849 766 854
1 150
2 721 416
2 716 277
1 336
2 471 535
1 621
2 661 638
2 201 751
0
2 705 67
2 350 24
2 118 131
2 124 704
2 66 511
2 577 200
2 406 733
2 749 312
0
2 114 168
2 472 18
2 83 398
2 261 591
2 627 433
2 60 454
2 371 351
2 70 706
2 143 35
2 477 133
2 365 38
1 126
1 525
2 587 74
0
2 162 225
2 ...

output:

935

result:

ok single line: '935'

Test #31:

score: 0
Accepted
time: 136ms
memory: 42464kb

input:

40473 42204 46693
2 17306 29840
2 21655 27206
2 1577 30755
2 9303 38135
2 13899 38726
2 25718 5486
0
2 13674 32709
2 3258 1310
2 19078 6271
2 32222 38810
2 18668 28018
2 9005 31601
2 31888 40637
2 32991 7539
2 40415 29067
2 33572 39589
2 26823 19361
2 38360 8413
2 4352 12745
2 40742 38924
2 14996 19...

output:

53046

result:

ok single line: '53046'

Test #32:

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

input:

3 3 3
2 3 1
2 2 1
2 3 2
2 1 3
2 2 3
2 1 2
2 2 3
2 1 2
2 1 3

output:

4

result:

ok single line: '4'

Test #33:

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

input:

4 4 4
2 3 2
2 3 4
2 1 2
2 4 1
2 2 3
2 2 4
2 1 3
2 4 1
2 4 1
2 1 3
2 2 3
2 2 4

output:

6

result:

ok single line: '6'

Test #34:

score: 0
Accepted
time: 230ms
memory: 63944kb

input:

50000 50000 50000
2 45046 28892
2 26220 33823
2 46837 49104
2 3917 21543
2 22880 20259
2 25075 24819
2 28379 7777
2 801 36871
2 44187 21466
2 8706 16158
2 15338 39721
2 39723 29802
2 34539 5470
2 10200 49750
2 21699 20778
2 6058 31648
2 38204 40071
2 23548 503
2 49337 49734
2 38822 41362
2 47146 283...

output:

75000

result:

ok single line: '75000'

Test #35:

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

input:

1 1 2
0
0
0

output:

0

result:

ok single line: '0'

Test #36:

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

input:

39951 46036 43531
2 35094 23951
2 18866 21023
2 32805 10424
2 35955 45509
2 189 5168
2 34865 13037
2 8649 20563
2 24042 31856
2 25255 38915
2 7464 35453
2 25282 29391
1 20283
0
2 34325 20208
2 4126 28607
2 30645 33252
2 16224 5621
2 785 29439
0
2 4746 31449
2 27519 15163
2 41348 17178
2 42965 18260
...

output:

51923

result:

ok single line: '51923'

Test #37:

score: 0
Accepted
time: 148ms
memory: 45812kb

input:

44783 49830 49790
2 8746 41966
2 19509 46070
2 20178 7125
2 16285 45020
2 4496 4008
2 13356 8478
2 28700 37404
0
2 21492 45729
2 11918 45500
0
2 6903 29645
2 4740 31748
2 906 650
2 26064 47318
2 17948 34431
2 14018 48718
0
2 18253 16054
2 49493 19858
0
2 49756 22092
2 11338 21122
2 37123 14213
2 394...

output:

57811

result:

ok single line: '57811'

Test #38:

score: 0
Accepted
time: 121ms
memory: 41208kb

input:

39021 44325 47486
2 35008 9443
2 28471 33372
2 7953 2706
2 37141 12326
2 11568 206
2 40796 34337
2 14524 13996
2 18020 33257
2 20594 25779
0
2 27590 19820
2 6303 25250
2 941 15601
2 1653 885
2 9376 19697
2 31716 18151
0
2 1540 2581
2 5459 20532
2 41650 4570
2 37175 31784
2 41241 32020
2 32862 3017
2...

output:

50800

result:

ok single line: '50800'

Test #39:

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

input:

16 19 18
1 1
2 2 3
2 2 3
2 4 5
2 4 5
1 6
2 6 7
2 7 8
2 8 9
0
0
0
0
0
0
0
1 1
2 2 3
2 2 3
2 4 5
2 4 5
1 6
2 6 7
2 7 8
2 8 9
0
0
0
0
0
0
0
1 1
2 2 3
2 2 3
2 4 5
2 4 5
1 6
2 6 7
2 7 8
2 8 9
0
0
0
0
0
0
0
0
0
0

output:

14

result:

ok single line: '14'

Test #40:

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

input:

15 19 15
2 5 10
2 5 10
2 11 17
2 2 6
2 2 6
0
2 3 9
0
2 15 11
2 13 8
2 14 18
2 3 13
2 15 7
1 16
2 8 9
1 3
2 3 11
2 12 1
2 10 6
2 10 6
0
2 13 15
0
2 9 12
2 7 5
1 8
2 13 7
2 9 2
0
2 5 15
0
1 10
2 13 15
1 4
2 11 3
2 10 6
0
2 7 5
2 5 15
2 11 3
2 9 12
0
2 13 7
2 8 4
1 9
0
2 12 1
0
0

output:

17

result:

ok single line: '17'

Test #41:

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

input:

940 954 772
0
2 205 95
1 913
0
0
0
2 895 2
2 432 381
0
0
2 449 193
2 896 626
1 929
2 321 698
2 700 949
2 817 600
2 158 917
2 556 787
0
0
0
2 550 422
0
0
0
2 462 877
2 401 90
2 234 508
2 860 674
0
0
0
2 573 372
2 410 217
2 801 70
0
2 844 928
0
2 470 592
0
0
2 775 649
0
2 565 362
0
0
2 740 237
0
2 694...

output:

897

result:

ok single line: '897'

Test #42:

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

input:

943 953 929
2 848 399
2 303 774
2 111 670
2 153 691
0
2 137 531
2 425 938
2 666 133
2 340 554
1 222
2 594 931
2 349 259
2 24 599
2 359 849
1 235
2 362 501
2 334 140
2 829 685
2 10 283
1 42
2 185 93
2 36 552
2 80 428
0
0
2 787 162
2 553 13
1 117
2 180 345
0
1 441
1 720
2 735 245
1 417
2 266 421
1 612...

output:

835

result:

ok single line: '835'

Test #43:

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

input:

843 813 843
2 557 521
1 749
2 504 327
2 7 131
2 623 106
0
0
2 503 323
2 617 751
0
2 107 768
2 722 189
1 325
0
2 566 472
2 148 603
2 650 215
2 649 469
2 794 489
0
1 743
1 56
2 690 452
2 155 414
2 139 309
2 275 565
2 226 33
1 548
1 758
0
1 387
2 26 717
2 276 373
2 304 513
2 813 662
2 146 442
2 652 214...

output:

800

result:

ok single line: '800'

Test #44:

score: 0
Accepted
time: 105ms
memory: 33032kb

input:

41238 39253 44143
0
0
1 10744
2 33488 22314
1 11040
2 11412 25343
2 21277 33538
2 17082 18260
2 17880 7562
2 23073 35830
2 25260 34839
2 1134 33324
1 23101
2 25104 17231
2 33407 20740
0
0
2 12030 37938
0
0
2 33764 6367
2 18680 3022
2 6780 34410
2 39106 17096
2 3485 11967
0
0
0
2 7781 4825
0
2 357 36...

output:

38301

result:

ok single line: '38301'

Test #45:

score: 0
Accepted
time: 110ms
memory: 35696kb

input:

48153 37872 45496
2 34264 37711
0
2 22927 631
2 16809 35441
2 19288 28176
2 11754 35224
2 14233 15039
0
2 15340 24502
2 4075 29456
0
2 18217 17234
2 13664 34253
2 5807 24427
1 33420
1 3311
2 14083 16744
2 6205 6802
2 20883 28070
2 2455 20710
0
0
2 17053 19317
2 17690 11483
0
1 24009
1 1734
2 16390 4...

output:

41743

result:

ok single line: '41743'

Test #46:

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

input:

2 3 3
0
0
0
0
0
0
0

output:

0

result:

ok single line: '0'

Test #47:

score: 0
Accepted
time: 57ms
memory: 22132kb

input:

49187 45881 38066
1 101
2 42754 40288
0
2 40272 1246
1 5376
1 25024
0
0
2 39113 3072
2 7493 31709
2 4244 7525
2 26779 22307
2 5826 10176
2 15479 1710
1 22211
1 9896
2 28803 40744
2 16755 3953
0
2 37009 38332
2 11073 38469
2 30342 35527
2 12982 12430
1 11060
2 20783 9081
2 43052 213
1 3437
1 18106
1 ...

output:

18896

result:

ok single line: '18896'

Test #48:

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

input:

20 18 17
1 1
1 2
2 3 4
2 3 4
1 5
2 5 6
2 6 7
2 7 8
2 9 11
2 9 10
2 10 11
0
0
0
0
0
0
0
0
0
1 1
1 2
2 3 4
2 3 4
1 5
2 5 6
2 6 7
2 7 8
2 9 11
2 9 10
2 10 11
0
0
0
0
0
0
0
0
0
1 1
1 2
2 3 4
2 3 4
1 5
2 5 6
2 6 7
2 7 8
2 9 11
2 9 10
2 10 11
0
0
0
0
0
0
0

output:

15

result:

ok single line: '15'

Test #49:

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

input:

19 17 20
2 17 1
2 12 13
2 8 14
2 15 4
2 6 7
1 3
0
1 2
2 2 12
2 5 9
2 6 4
0
0
2 5 9
2 13 11
1 16
1 17
2 8 10
2 7 15
2 15 8
2 17 5
0
2 11 18
2 14 20
0
0
2 9 2
2 9 17
2 13 10
2 14 18
1 12
0
2 13 10
2 5 2
1 7
1 3
2 1 3
2 20 11
0
1 9
2 3 15
2 11 18
2 13 10
2 14 18
2 14 20
1 1
2 13 10
1 19
2 5 2
2 9 17
2 ...

output:

17

result:

ok single line: '17'

Test #50:

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

input:

793 990 822
2 187 315
0
1 579
0
0
0
2 688 658
2 227 907
1 241
1 956
2 696 842
2 889 457
1 846
2 97 832
2 876 625
1 979
2 293 273
2 669 404
0
2 178 177
2 898 511
2 574 880
2 601 535
2 499 85
2 361 120
0
2 988 446
2 885 735
2 820 444
2 13 119
0
2 525 130
2 476 816
0
2 257 693
1 578
0
1 968
1 610
2 766...

output:

933

result:

ok single line: '933'

Test #51:

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

input:

884 926 807
0
2 278 91
2 169 742
2 874 122
1 404
1 740
2 145 402
2 94 378
0
1 262
2 272 505
0
0
0
2 413 317
0
2 351 716
0
2 461 194
2 97 568
0
2 721 112
0
2 168 362
2 865 705
2 234 252
1 84
2 703 767
2 171 428
1 144
2 765 463
2 803 690
1 344
2 51 527
2 417 753
2 677 805
1 333
2 704 416
2 760 521
2 4...

output:

819

result:

ok single line: '819'

Test #52:

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

input:

884 863 953
1 712
1 217
2 693 429
2 512 38
2 452 463
2 631 316
1 652
1 487
1 51
2 246 478
2 396 36
1 333
1 528
2 696 70
2 686 773
2 79 837
2 747 713
2 370 834
2 856 752
2 122 377
2 631 236
1 85
2 93 412
2 160 638
2 182 688
2 549 338
2 140 672
1 336
2 744 449
2 420 251
2 562 452
0
2 506 64
2 203 4
2 ...

output:

787

result:

ok single line: '787'

Test #53:

score: 0
Accepted
time: 106ms
memory: 34112kb

input:

45123 46859 41314
2 18779 7218
2 28334 42034
0
0
2 30938 2179
2 5732 23988
2 9559 15481
2 3071 13814
0
2 8051 22891
0
2 29952 20511
0
0
2 14145 20001
2 35145 13821
0
1 2390
2 2807 7829
2 10388 37801
2 14342 31087
2 10365 41792
0
2 16435 5630
2 7755 619
2 6896 32324
2 19984 6464
2 13104 13792
0
1 529...

output:

39514

result:

ok single line: '39514'

Test #54:

score: 0
Accepted
time: 104ms
memory: 34948kb

input:

48529 43479 42580
2 42089 11836
2 24116 2160
1 33665
2 17701 32472
1 35025
2 7126 17899
2 20261 17600
0
2 21548 4635
2 37733 23444
2 2435 25281
2 19672 27700
0
2 6414 34455
0
0
0
2 21688 22173
1 6843
2 42019 40963
2 29336 35882
2 34546 13936
2 31239 32024
0
0
2 20121 1116
1 23293
2 25489 681
0
2 100...

output:

40665

result:

ok single line: '40665'

Test #55:

score: 0
Accepted
time: 66ms
memory: 23332kb

input:

37717 46700 43401
2 31096 43592
1 369
2 25513 26447
2 9732 29833
2 34865 34749
0
1 15924
2 12548 20705
2 12497 33915
2 10995 40624
2 26864 4280
2 4534 36656
0
2 43586 43210
2 45251 38577
1 41321
2 34369 26052
2 39150 28220
0
1 19556
2 21485 1564
2 13789 38797
1 3200
2 43268 25172
0
2 8326 41022
2 42...

output:

21081

result:

ok single line: '21081'

Test #56:

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

input:

16 20 15
1 1
1 2
2 3 4
2 3 4
2 5 6
2 5 6
2 7 10
2 7 8
2 8 9
2 9 10
1 11
2 11 12
2 12 13
0
0
0
1 1
1 2
2 3 4
2 3 4
2 5 6
2 5 6
2 7 10
2 7 8
2 8 9
2 9 10
1 11
2 11 12
2 12 13
0
0
0
1 1
1 2
2 3 4
2 3 4
2 5 6
2 5 6
2 7 10
2 7 8
2 8 9
2 9 10
1 11
2 11 12
2 12 13
0
0
0
0
0
0
0

output:

20

result:

ok single line: '20'

Test #57:

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

input:

849 970 796
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
...

output:

0

result:

ok single line: '0'

Test #58:

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

input:

19 17 20
1 4
2 2 5
0
0
2 3 11
2 14 15
2 2 5
0
0
1 8
0
2 16 11
2 16 3
1 15
1 10
0
0
1 1
2 6 14
1 1
2 15 2
0
1 19
2 7 20
2 10 4
2 15 2
1 8
0
0
0
2 9 20
2 9 7
1 6
2 12 14
0
0
0
0
1 13
2 15 2
2 9 7
0
2 15 2
2 17 19
1 4
0
1 8
1 12
2 7 20
1 1
0
2 14 4
1 6
2 9 20
1 1

output:

11

result:

ok single line: '11'

Test #59:

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

input:

990 855 833
2 389 331
2 589 850
2 399 265
2 680 529
1 168
2 636 493
2 463 230
0
2 648 798
2 687 150
0
0
0
0
2 112 127
2 361 654
0
1 120
2 163 714
0
2 453 437
2 470 563
0
0
2 332 338
2 812 72
1 585
2 52 45
2 349 322
0
2 348 485
0
2 85 334
1 433
0
1 60
0
0
2 797 216
2 7 685
0
2 670 103
2 62 281
0
2 51...

output:

970

result:

ok single line: '970'

Test #60:

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

input:

964 937 802
2 845 367
2 513 873
2 222 592
1 53
0
1 538
0
2 215 668
2 556 760
1 528
2 715 799
1 841
2 816 788
2 550 477
2 49 272
2 216 142
2 381 18
0
2 117 745
2 522 250
0
2 790 385
2 377 660
2 532 198
2 611 455
0
0
2 736 301
0
0
2 902 228
2 413 407
2 907 704
2 777 132
2 839 255
0
0
2 111 919
2 562 5...

output:

836

result:

ok single line: '836'

Test #61:

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

input:

772 941 935
2 329 342
2 736 602
2 174 97
2 102 242
2 30 28
2 388 542
1 344
2 545 52
2 75 152
1 65
2 809 598
2 614 697
2 784 196
1 623
2 779 451
2 685 694
1 853
2 305 884
2 263 731
2 853 483
2 147 691
2 420 159
2 553 262
2 198 291
0
0
1 338
2 671 86
2 783 343
2 56 281
2 210 768
2 936 641
0
1 169
2 65...

output:

725

result:

ok single line: '725'

Test #62:

score: 0
Accepted
time: 109ms
memory: 33896kb

input:

46538 47347 44950
0
2 8318 43318
2 38213 27820
0
1 41008
2 41309 18114
2 26852 7310
0
2 35605 38806
2 21842 34517
0
2 18657 43861
2 18538 12107
2 23747 37403
0
0
2 8859 20557
0
2 12482 46481
2 17711 12582
1 31096
2 40814 39179
2 10654 44398
1 16040
2 19658 46723
2 27556 11136
2 14266 23058
2 36294 2...

output:

39517

result:

ok single line: '39517'

Test #63:

score: 0
Accepted
time: 110ms
memory: 34644kb

input:

41902 48936 48090
2 6427 27825
1 11049
2 17322 17798
2 27046 1254
2 9023 11269
2 46118 42903
0
0
2 34368 4736
2 11166 13062
2 48495 9549
2 12788 42989
2 44548 12628
0
2 33643 31923
2 23184 28894
2 42964 8220
2 16193 2026
1 34242
2 27251 21068
2 46706 19182
2 35187 9561
2 16559 32555
2 17161 10760
2 ...

output:

40956

result:

ok single line: '40956'

Test #64:

score: 0
Accepted
time: 64ms
memory: 22572kb

input:

46741 49571 45567
2 12119 16527
0
1 46174
1 12470
2 33861 32915
2 25323 42168
2 49368 4543
2 42607 46286
0
2 30256 26746
2 5650 29612
2 41121 9477
0
2 10101 7197
2 25999 35002
2 25352 27460
1 17670
2 12624 26907
2 324 22873
2 16233 33673
2 45217 48785
2 15963 1597
1 1775
2 35623 10296
0
2 47509 9410...

output:

19958

result:

ok single line: '19958'

Test #65:

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

input:

8895 8443 10664
2 6822 131
2 4882 6918
0
1 7904
0
1 3042
2 1172 4324
1 3827
2 715 4192
2 5231 2922
2 7691 8402
2 1769 3408
2 4235 8324
2 26 7210
0
2 5564 7354
1 3553
1 4257
1 5003
2 3958 7257
2 5851 4356
1 1128
0
1 5217
0
2 7090 6985
2 7359 8382
1 7478
1 3294
2 416 4979
2 1725 1078
2 3618 2510
2 363...

output:

4964

result:

ok single line: '4964'

Test #66:

score: 0
Accepted
time: 59ms
memory: 28088kb

input:

28374 34094 34914
1 22508
2 8864 12759
2 6570 8693
2 32339 5727
2 2673 29683
1 32318
2 22104 19210
2 22784 234
2 25162 22937
1 29762
2 16484 5835
2 20542 13516
2 31975 28296
2 12822 18749
2 2370 19468
2 2708 22026
2 13627 1124
1 16049
2 1601 9225
2 29432 8821
2 2951 10669
2 25026 4336
1 14039
1 2504...

output:

35639

result:

ok single line: '35639'

Test #67:

score: 0
Accepted
time: 28ms
memory: 15432kb

input:

39214 31125 34084
0
2 12210 21748
1 14281
2 10781 24671
2 28629 16980
0
1 17455
1 5627
1 27400
1 6791
2 14176 9600
1 9886
2 25159 12163
1 5512
2 18674 30070
2 17469 23834
2 16560 6724
2 16665 14321
1 4113
2 2715 22226
0
0
1 23003
2 10281 13071
1 10974
1 12394
0
0
0
1 2386
1 6524
2 27392 2337
1 27005...

output:

8788

result:

ok single line: '8788'

Test #68:

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

input:

2 2 2
2 1 2
2 1 2
2 1 2
2 1 2
2 1 2
2 1 2

output:

4

result:

ok single line: '4'

Test #69:

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

input:

1582 1458 1341
2 1226 215
2 1058 760
2 1171 78
2 92 1200
1 737
2 1292 955
2 1130 1260
2 503 403
2 1258 423
2 1211 153
1 388
2 69 122
2 798 441
2 427 626
2 1229 250
2 232 542
2 972 554
2 356 472
2 333 745
2 275 1000
2 205 242
2 592 774
2 46 1215
2 681 838
2 1090 10
2 253 521
2 194 84
2 1360 919
2 554...

output:

1343

result:

ok single line: '1343'

Test #70:

score: 0
Accepted
time: 32ms
memory: 17176kb

input:

16037 17855 15266
2 3574 12317
2 5510 16480
2 2535 14442
2 17402 17412
0
2 15776 7926
2 14723 16728
2 5322 9624
2 13621 7115
2 17715 11192
2 5989 15790
2 4294 17525
2 9369 4185
0
2 16359 7566
2 13214 16899
1 16572
2 3177 1950
1 12569
2 3548 17832
1 2472
0
2 10374 842
2 8227 14305
2 9779 17493
1 450
...

output:

14823

result:

ok single line: '14823'

Test #71:

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

input:

14991 13441 15043
2 10392 3546
2 6039 4451
1 7620
2 13127 10792
2 9309 8814
2 9010 7709
2 645 7854
2 3531 7470
2 5259 6063
2 7945 9096
2 122 1208
1 10214
2 8306 10410
2 11677 7117
2 10873 6764
2 1619 8041
2 6684 203
0
2 6978 7437
2 789 12416
2 8029 4589
2 2119 6282
2 7469 11751
0
1 7794
2 9816 4406
...

output:

5502

result:

ok single line: '5502'

Test #72:

score: 0
Accepted
time: 34ms
memory: 17120kb

input:

20773 19295 22772
0
0
0
0
0
2 16419 2906
1 425
1 6064
1 4214
2 5035 16837
2 3244 7538
2 13603 12101
1 5315
1 3877
2 15732 231
1 12280
1 10184
2 6003 11605
2 8731 7618
1 15491
1 13327
2 17133 8223
2 12940 10302
2 8387 19275
0
0
2 5202 17803
0
2 7919 10401
1 441
0
1 18894
1 8985
0
1 769
1 5256
1 11723...

output:

14043

result:

ok single line: '14043'

Test #73:

score: 0
Accepted
time: 60ms
memory: 23100kb

input:

37640 31835 29028
0
2 29229 20815
0
0
2 11414 3917
0
0
0
2 5023 28508
0
0
0
2 28575 18392
2 14540 7483
1 31588
1 28316
0
2 3573 8817
2 15224 2514
2 26102 30608
2 6031 17807
1 12398
0
0
2 4971 15844
0
2 11851 17608
1 9976
0
0
2 16737 13997
0
1 25437
2 23047 2891
1 10724
1 20416
1 1874
1 6931
2 17851 ...

output:

21732

result:

ok single line: '21732'

Test #74:

score: 0
Accepted
time: 27ms
memory: 15084kb

input:

34342 34019 35220
1 3470
1 22468
1 24896
0
2 8227 18557
1 17639
1 26048
0
1 23545
2 13695 26701
2 21691 14577
2 14478 21011
2 28119 1084
1 2080
1 29358
2 9798 33955
1 19301
2 26363 16367
0
0
2 10134 29254
2 29785 29510
2 19044 22394
2 21601 10625
2 26695 15121
2 3971 1633
2 20808 20935
1 1948
1 2056...

output:

11164

result:

ok single line: '11164'

Test #75:

score: 0
Accepted
time: 56ms
memory: 23484kb

input:

34594 29770 33485
0
2 13480 3887
2 17544 16057
2 9932 9146
0
0
2 28821 26522
1 24854
2 2784 12025
1 28791
0
2 1314 18215
1 25161
2 4108 14324
2 13100 12506
1 723
1 19929
2 27690 1657
1 17515
1 3918
1 4654
2 14338 25856
2 19954 21020
2 4859 25517
2 15526 4847
0
2 6832 17177
2 2098 10752
2 25863 13814...

output:

23778

result:

ok single line: '23778'

Test #76:

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

input:

836 744 693
2 5 643
2 55 183
2 431 133
2 64 415
0
0
2 144 170
2 598 221
2 692 278
2 415 184
2 235 246
0
2 146 124
0
2 26 128
1 379
2 160 582
2 265 108
1 523
2 734 389
2 20 103
2 84 744
2 498 639
2 507 225
2 657 350
2 733 200
2 52 484
2 288 10
2 381 181
2 205 724
2 628 389
2 153 355
2 504 670
2 63 31...

output:

587

result:

ok single line: '587'

Test #77:

score: 0
Accepted
time: 57ms
memory: 24836kb

input:

27764 27583 33546
2 11048 13630
2 14807 17063
2 17106 152
1 3008
2 25109 9170
2 668 253
2 8464 9484
2 4611 5591
2 17114 5111
2 13890 8282
2 23800 23830
2 5805 16643
2 25446 14265
2 9837 7632
2 12668 19322
2 4636 5023
2 16135 3908
2 17279 314
2 14628 16690
2 5137 25402
1 9050
2 9187 2701
0
2 26727 45...

output:

27798

result:

ok single line: '27798'

Test #78:

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

input:

6512 6706 6660
2 6043 6552
2 500 6386
2 2429 4583
2 4159 2570
2 4872 3327
2 460 1743
2 2527 1092
2 4423 4654
2 3957 5755
2 2367 663
2 5 3902
2 2933 2385
2 6558 2882
2 5866 1318
2 1742 4025
2 1419 402
2 2103 1
2 2097 3098
2 3688 3315
2 1097 3622
2 5591 6612
1 5147
2 58 905
2 3304 237
2 972 6403
2 125...

output:

3536

result:

ok single line: '3536'

Test #79:

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

input:

4 4 4
2 1 2
2 1 2
2 3 4
2 3 4
2 1 2
2 1 2
2 3 4
2 3 4
2 1 2
2 1 2
2 3 4
2 3 4

output:

8

result:

ok single line: '8'

Test #80:

score: 0
Accepted
time: 44ms
memory: 21668kb

input:

36149 40364 39687
1 15713
0
0
0
2 22088 38138
0
1 20659
0
1 27169
2 13114 22088
2 38161 7718
0
0
0
0
1 34768
1 27686
2 22093 17458
2 1938 3870
2 22343 11870
2 31895 19826
1 22037
1 15208
1 22419
2 29926 13804
0
2 37406 20148
0
0
2 27054 15480
0
2 35033 6594
1 31765
2 6645 4585
0
2 23896 24026
2 3175...

output:

22779

result:

ok single line: '22779'

Test #81:

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

input:

637 538 588
2 283 18
2 85 10
0
2 537 356
1 393
0
2 465 11
2 365 70
1 532
2 245 163
2 384 519
1 362
0
1 192
2 38 528
1 220
2 409 288
2 388 42
2 356 477
2 399 110
2 429 208
2 178 125
2 391 124
2 145 160
2 278 51
1 455
1 123
1 234
2 266 162
1 250
1 388
2 418 164
2 39 37
2 89 312
2 439 293
0
2 482 247
2...

output:

200

result:

ok single line: '200'

Test #82:

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

input:

2828 2662 3131
2 1431 916
2 1806 763
2 1260 336
2 1478 118
2 976 1035
2 1932 2651
1 1350
2 343 1447
2 2170 1502
2 401 2633
2 2494 1256
2 516 2160
1 985
2 417 2104
2 1033 2159
2 608 1231
2 2236 1372
2 1386 2045
2 1920 890
2 1023 2200
2 743 1443
2 508 942
1 1850
2 1441 2239
2 743 1873
2 1533 1663
2 20...

output:

2725

result:

ok single line: '2725'

Test #83:

score: 0
Accepted
time: 173ms
memory: 61800kb

input:

50000 50000 50000
2 1 2
2 1 2
2 3 4
2 3 4
2 5 6
2 5 6
2 7 8
2 7 8
2 9 10
2 9 10
2 11 12
2 11 12
2 13 14
2 13 14
2 15 16
2 15 16
2 17 18
2 17 18
2 19 20
2 19 20
2 21 22
2 21 22
2 23 24
2 23 24
2 25 26
2 25 26
2 27 28
2 27 28
2 29 30
2 29 30
2 31 32
2 31 32
2 33 34
2 33 34
2 35 36
2 35 36
2 37 38
2 37...

output:

100000

result:

ok single line: '100000'