QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#32853#1165. Colorful SquaresWu_RenAC ✓1603ms43936kbC++171.3kb2022-05-25 08:31:062022-05-25 08:31:09

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2022-05-25 08:31:09]
  • 评测
  • 测评结果：AC
  • 用时：1603ms
  • 内存：43936kb
查看
  • [2022-05-25 08:31:06]
  • 提交

answer

#include <bits/stdc++.h>
#define fi first
#define se second
const int N=2.5e5;
using namespace std;
vector<pair<int,int> >v[N+10];
multiset<int>s[N+10];
int n,K,tr[4*N],tg[4*N+10],mid;
void build(int l,int r,int t){
	tr[t]=tg[t]=0;
	if(l==r) return;
	int mid=(l+r)>>1;
	build(l,mid,t<<1),build(mid+1,r,t<<1|1);
}
void pushup(int t){
	tr[t]=max(tr[t<<1],tr[t<<1|1])+tg[t];
}
void upd(int ql,int qr,int l,int r,int t,int c){
	if(ql<=l&&r<=qr) return tr[t]+=c,tg[t]+=c,void();
	int mid=(l+r)>>1;
	if(ql<=mid) upd(ql,qr,l,mid,t<<1,c);
	if(mid<qr) upd(ql,qr,mid+1,r,t<<1|1,c);
	pushup(t);
}
void cg(int y,int k,int c){
	auto it=c>0?s[k].insert(y):s[k].lower_bound(y);
	int l=max({y,*prev(it)+mid+1,1}),r=min({y+mid,*next(it)-1,N});
	if(l<=r) upd(l,r,1,N,1,c);
	if(c<0) s[k].erase(it);
}
bool chk(){
	build(1,N,1);
	for(int i=1;i<=K;i++) s[i].clear(),s[i].insert(-N),s[i].insert(2*N);
	for(int i=1;i<=N;i++){
		for(auto j:v[i]) cg(j.fi,j.se,1);
		if(i-mid-1>0) for(auto j:v[i-mid-1]) cg(j.fi,j.se,-1);
		if(tr[1]>=K) return 1;
	}
	return 0;
}
int main(){
	scanf("%d%d",&n,&K);
	for(int i=1,x,y,c;i<=n;i++) scanf("%d%d%d",&x,&y,&c),v[x].push_back({y,c});
	int l=0,r=N,ans=N;
	while(l<=r){
		mid=(l+r)>>1;
		if(chk()) ans=mid,r=mid-1;
		else l=mid+1;
	}
	printf("%d\n",ans);
}
Source code, Language: C++17

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 18ms
memory: 27296kb

input:

5 2
4 2 1
5 3 1
5 4 2
4 5 2
3 8 2

output:

1

result:

ok "1"

Test #2:

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

input:

5 3
4 2 1
5 3 1
5 4 2
4 5 2
3 8 3

output:

5

result:

ok "5"

Test #3:

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

input:

4 2
1 1 1
1 1 1
1 1 2
1 1 2

output:

0

result:

ok "0"

Test #4:

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

input:

3 2
1 2 1
2 3 1
3 4 2

output:

1

result:

ok "1"

Test #5:

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

input:

2 2
1 1 2
1 1 1

output:

0

result:

ok "0"

Test #6:

score: 0
Accepted
time: 26ms
memory: 27328kb

input:

50 10
47 10 8
13 2 4
19 1 4
47 8 1
22 6 3
26 8 5
18 10 10
24 10 7
40 9 6
34 7 6
26 3 9
9 3 5
32 3 7
24 5 3
29 9 2
14 7 1
49 10 10
32 8 8
17 9 2
29 6 5
39 9 6
17 1 6
28 10 1
24 5 3
49 6 10
50 6 6
41 2 2
12 7 8
8 2 4
43 4 6
2 3 2
41 5 9
45 6 9
23 2 7
36 10 2
1 3 5
45 10 8
29 1 4
16 3 6
17 9 1
31 5 3
3...

output:

14

result:

ok "14"

Test #7:

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

input:

50 10
5 37 5
2 32 5
1 30 1
8 35 9
3 12 9
7 49 8
8 7 4
8 29 4
1 11 10
1 35 8
2 36 3
3 5 1
3 25 9
9 19 1
4 13 1
4 39 7
4 50 5
8 38 3
10 50 2
9 40 7
1 32 8
10 20 6
9 44 9
6 50 2
9 1 3
6 43 7
7 44 10
9 50 5
3 20 7
7 6 9
10 23 2
4 7 4
5 3 10
2 33 1
9 25 10
4 24 6
10 43 5
5 44 9
4 10 10
1 16 8
7 4 2
5 3 6...

output:

15

result:

ok "15"

Test #8:

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

input:

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

output:

5

result:

ok "5"

Test #9:

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

input:

50 50
35 32 9
19 38 42
11 3 15
25 2 45
25 6 36
9 45 24
35 19 34
26 34 40
29 25 29
35 6 44
43 49 4
8 19 47
17 27 35
27 8 41
20 47 21
20 23 20
19 25 7
42 5 25
13 26 50
6 14 11
31 15 3
21 27 18
42 16 12
21 35 28
7 14 16
43 37 43
36 49 13
26 41 1
44 30 23
5 11 32
18 7 38
38 5 48
48 36 31
15 6 22
19 18 1...

output:

48

result:

ok "48"

Test #10:

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

input:

50 40
48 48 23
44 21 18
34 13 16
28 46 10
26 23 14
24 10 30
35 19 37
5 9 32
3 50 36
21 50 11
9 40 3
22 20 9
16 36 28
33 28 33
42 47 29
44 34 34
45 39 1
12 40 25
41 41 32
22 19 39
46 47 18
13 20 30
25 19 20
27 33 19
49 30 30
37 12 27
18 50 31
40 2 35
3 38 4
44 27 22
40 47 6
7 40 38
30 49 8
29 28 13
1...

output:

49

result:

ok "49"

Test #11:

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

input:

50 30
48 14 29
20 24 12
43 37 9
26 41 12
29 48 2
6 4 11
33 7 27
44 17 15
42 30 2
17 31 3
3 8 19
24 5 9
27 13 21
18 44 14
38 28 24
45 16 20
39 46 16
19 44 10
22 39 7
34 42 17
14 22 2
1 42 29
25 22 8
41 9 13
24 41 30
6 8 7
38 29 18
39 5 1
44 22 28
2 33 23
8 19 10
34 10 22
27 12 15
35 28 1
11 23 14
49 ...

output:

44

result:

ok "44"

Test #12:

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

input:

50 20
49 29 14
36 47 10
14 45 3
13 20 8
49 18 5
16 24 1
49 21 17
5 29 8
38 38 2
3 37 5
2 22 7
24 17 12
10 26 8
17 41 14
24 8 13
41 27 12
34 30 11
18 46 4
32 37 15
50 50 10
34 22 13
27 15 20
36 23 20
47 16 3
39 3 8
42 6 11
4 3 12
45 8 11
12 1 6
15 49 16
33 16 6
39 9 14
11 30 9
46 41 16
50 16 12
6 18 ...

output:

44

result:

ok "44"

Test #13:

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

input:

50 10
29 39 6
15 38 1
24 48 10
16 40 5
19 46 8
6 28 4
5 30 8
9 46 9
11 40 1
13 27 10
18 37 3
14 26 9
6 12 2
20 15 8
21 10 9
3 44 2
8 9 10
29 29 3
8 2 3
31 36 1
35 28 4
13 50 3
12 13 5
43 20 5
28 21 2
16 1 1
49 32 9
46 38 6
50 11 7
34 6 6
49 3 8
17 46 2
38 13 5
25 8 9
19 12 4
46 18 4
39 23 2
1 5 6
35...

output:

20

result:

ok "20"

Test #14:

score: 0
Accepted
time: 26ms
memory: 27084kb

input:

50 50
46 45 9
39 46 42
44 41 15
29 31 45
2 39 36
3 35 24
45 37 34
41 39 40
1 43 29
37 44 44
7 8 4
47 44 47
5 9 35
42 1 41
1 43 21
40 4 20
45 13 7
17 27 25
15 45 50
2 10 11
20 38 3
32 2 18
29 39 12
1 9 28
28 50 16
22 48 43
37 38 13
48 35 1
4 29 23
45 16 32
49 49 38
7 9 48
47 31 31
7 44 22
32 42 17
47...

output:

49

result:

ok "49"

Test #15:

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

input:

50 10
7 1 6
1 15 1
36 21 10
16 9 5
47 13 8
39 30 4
45 11 8
47 4 9
40 17 1
14 11 10
12 28 3
13 5 9
39 12 2
50 19 8
44 11 9
43 38 2
11 44 10
1 42 3
9 39 3
33 1 1
2 23 4
10 8 3
5 47 5
43 44 5
48 2 2
44 47 1
50 47 9
1 36 6
3 41 7
35 45 6
45 14 8
48 50 2
27 49 5
4 8 9
44 4 4
49 39 4
36 50 2
40 14 6
3 8 8...

output:

33

result:

ok "33"

Test #16:

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

input:

50 2
33 47 2
43 15 1
21 48 1
38 49 2
33 1 2
50 41 2
40 50 1
28 32 1
3 9 1
38 13 1
17 41 2
2 36 2
47 47 1
7 14 2
2 10 1
48 3 2
43 49 1
8 6 1
47 30 2
8 23 1
48 10 1
21 1 1
41 18 2
50 26 2
45 46 1
42 31 1
6 11 2
43 4 1
4 1 1
29 35 1
3 4 1
50 38 2
7 36 2
10 5 2
7 10 1
31 43 2
13 49 1
49 33 1
14 48 1
49 ...

output:

1

result:

ok "1"

Test #17:

score: 0
Accepted
time: 93ms
memory: 28408kb

input:

100000 50
2402 7 50
38 3 38
1475 2 46
437 5 50
2077 2 3
107 8 33
95 3 19
1812 7 32
2312 9 44
2452 6 31
648 5 34
986 5 46
556 2 6
596 2 9
267 2 13
2334 7 21
1544 9 44
1975 4 22
2085 1 42
1541 2 25
1427 3 30
1121 10 39
19 5 8
2129 6 11
1211 4 17
1833 4 48
567 4 9
191 3 40
1017 10 20
1902 8 39
1581 3 3...

output:

4

result:

ok "4"

Test #18:

score: 0
Accepted
time: 201ms
memory: 30252kb

input:

100000 50
4 2097 38
3 1478 32
10 43 30
2 179 16
3 828 48
5 2244 3
5 906 39
3 1821 35
10 782 8
8 984 6
10 1116 49
9 656 36
6 891 5
7 899 46
2 1943 50
6 1241 23
1 282 13
6 1734 31
4 790 41
8 76 50
6 651 27
4 287 27
1 2138 7
7 1263 41
8 2366 2
3 1121 49
4 1675 14
9 354 43
7 2378 47
6 1451 28
10 2138 5
...

output:

4

result:

ok "4"

Test #19:

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

input:

100000 50
6 8 5
7 9 34
2 8 29
7 8 34
3 4 28
2 3 38
2 4 41
7 9 25
2 4 5
4 8 45
7 9 34
2 1 2
9 3 18
4 7 1
6 2 1
8 10 1
6 3 35
2 3 12
4 8 22
8 4 45
10 2 21
4 10 44
3 5 1
2 1 4
5 8 47
9 9 32
7 3 25
1 8 29
2 1 38
6 8 43
9 7 35
8 2 32
8 10 3
4 1 13
7 4 17
7 5 35
9 6 28
1 1 25
8 6 46
1 6 29
9 7 6
4 2 44
9 ...

output:

0

result:

ok "0"

Test #20:

score: 0
Accepted
time: 220ms
memory: 27840kb

input:

100000 50
1337 1014 27
660 1789 19
1065 2044 36
108 196 5
2363 858 33
1088 242 6
2153 2022 30
933 407 17
34 2112 50
67 1388 50
1663 285 21
2378 767 30
1238 2316 38
269 2000 32
66 1444 16
1914 1473 47
1857 1567 8
2112 308 8
709 106 41
1676 1540 48
1283 266 8
1581 1631 50
987 1060 23
1684 1843 17
18 1...

output:

67

result:

ok "67"

Test #21:

score: 0
Accepted
time: 289ms
memory: 27732kb

input:

100000 20
1451 2370 8
1802 460 12
836 118 8
53 1518 3
19 1649 14
1271 368 8
612 1466 5
2413 1878 18
1752 1556 14
611 1843 5
646 599 7
866 25 12
1926 647 10
355 597 20
172 1094 16
334 764 15
1665 2098 1
440 2424 12
331 190 5
1014 443 10
1880 1680 9
1572 903 16
839 973 5
1315 57 19
166 257 6
1959 414 ...

output:

29

result:

ok "29"

Test #22:

score: 0
Accepted
time: 177ms
memory: 28472kb

input:

100000 10
1909 2182 3
2176 1695 10
1655 805 5
1324 2407 7
2393 1396 1
461 194 4
2470 2097 7
2466 1824 9
1573 70 8
1730 708 3
476 2165 1
1344 2170 8
997 1448 6
1980 339 6
1857 1566 7
1824 268 5
1707 488 4
1308 1175 4
2151 1948 3
887 1125 6
2040 1213 7
423 283 1
641 1178 3
436 2232 9
593 1711 9
338 17...

output:

13

result:

ok "13"

Test #23:

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

input:

100000 5
1834 1290 5
1876 1599 3
2177 757 3
973 1930 4
787 1452 1
95 873 5
690 717 5
2093 180 4
1351 1579 3
2446 2075 5
551 755 5
2225 1565 2
1335 708 2
1678 285 3
794 44 2
1831 184 5
1186 2128 5
2496 1816 2
1902 644 3
418 1864 5
282 1225 2
252 54 4
957 2297 5
1625 1235 1
58 1142 2
180 103 5
1 1384 ...

output:

4

result:

ok "4"

Test #24:

score: 0
Accepted
time: 82ms
memory: 27760kb

input:

100000 3
426 1106 1
2150 1605 2
1671 1127 3
233 361 2
2353 964 2
709 1814 2
385 207 1
1969 636 2
2174 862 3
2006 41 2
971 90 2
136 1702 1
1360 2229 3
738 2335 1
2488 364 2
2201 2169 1
2113 1333 3
210 1691 3
2424 138 3
417 790 3
2469 57 2
874 419 1
412 2374 1
2208 217 2
2499 1316 2
1349 1192 3
2054 1...

output:

1

result:

ok "1"

Test #25:

score: 0
Accepted
time: 36ms
memory: 27532kb

input:

100000 2
1924 1607 1
388 84 2
1311 798 2
416 835 2
2143 1562 2
1956 541 2
1628 896 2
2166 2356 1
756 2175 2
2178 607 2
1179 697 1
254 168 2
835 1625 2
1683 2020 2
764 748 2
2022 1035 2
1178 1184 1
239 1929 2
1858 559 1
581 2465 1
1405 2485 1
2012 1030 2
1157 1182 2
462 1493 2
1825 534 2
2007 168 1
1...

output:

0

result:

ok "0"

Test #26:

score: 0
Accepted
time: 269ms
memory: 28632kb

input:

100000 50
1527 910 27
59 1218 19
1242 635 36
849 2379 5
585 1014 33
116 40 6
1983 818 30
645 1932 17
1060 260 50
2375 322 50
784 984 21
66 58 30
334 27 38
245 2268 32
1149 394 16
1355 960 47
2225 523 8
1845 2209 8
337 1003 41
2020 2379 48
5 1501 8
105 2252 50
1838 171 23
983 1976 17
718 2090 10
314 ...

output:

40

result:

ok "40"

Test #27:

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

input:

100000 20
70 280 8
2304 564 12
789 117 8
675 2462 3
413 675 14
85 988 8
407 121 5
1604 1820 18
2288 1979 14
1154 1643 5
1863 110 7
462 77 12
1242 911 10
543 51 20
967 2149 16
2248 18 15
161 1181 1
931 718 12
203 2453 5
1395 2363 10
2005 130 9
1268 1540 16
49 398 5
115 446 19
343 2335 6
2309 547 19
3...

output:

19

result:

ok "19"

Test #28:

score: 0
Accepted
time: 123ms
memory: 27992kb

input:

100000 10
2151 2118 3
2368 921 10
1526 461 5
290 749 7
2130 465 1
1015 1969 4
769 2080 7
415 140 9
1984 2483 8
624 1356 3
38 2133 1
1563 1866 8
146 656 6
102 804 6
148 2473 7
575 2400 5
74 174 4
83 2481 4
837 2119 3
1470 1897 6
2485 2430 7
2121 98 1
1419 39 3
1999 337 9
2093 492 9
617 1957 4
741 896...

output:

8

result:

ok "8"

Test #29:

score: 0
Accepted
time: 89ms
memory: 28512kb

input:

100000 5
2443 2270 5
2153 1810 3
517 2089 3
1053 2467 4
777 673 1
178 9 5
1014 1928 5
2432 2221 4
2051 399 3
2135 675 5
1765 2493 5
692 424 2
2070 1676 2
2162 2139 3
2301 867 2
75 2324 5
1853 2434 5
1249 2083 2
2146 49 3
137 1736 5
31 1355 2
2496 99 4
2408 2392 5
1378 1703 1
161 51 2
1836 15 5
781 1...

output:

1

result:

ok "1"

Test #30:

score: 0
Accepted
time: 37ms
memory: 27436kb

input:

100000 3
1051 1952 1
2182 465 2
385 662 3
650 698 2
230 163 2
108 1963 2
2148 2424 1
640 924 2
906 722 3
2302 1614 2
1887 791 2
951 233 1
1672 137 3
1728 1035 1
2426 2451 2
1531 474 1
2429 190 3
580 2400 3
506 588 3
171 1135 3
1986 2279 2
1302 2082 1
2433 2457 1
146 216 2
1028 937 2
65 19 3
1534 623...

output:

0

result:

ok "0"

Test #31:

score: 0
Accepted
time: 29ms
memory: 27704kb

input:

100000 2
1428 228 1
1433 2196 2
487 2303 2
1170 149 2
718 505 2
1944 1577 2
1760 2147 2
40 823 1
2275 407 2
2372 1096 2
2080 83 1
269 633 2
948 2060 2
1654 1874 2
58 2394 2
91 1600 2
138 182 1
2167 269 2
2087 2358 1
831 273 1
807 2210 1
2210 75 2
704 298 2
2153 63 2
72 1626 2
1940 58 1
1800 2437 1
2...

output:

0

result:

ok "0"

Test #32:

score: 0
Accepted
time: 432ms
memory: 32100kb

input:

100000 50
1262 1137 3
1534 1225 18
1302 1200 5
258 2135 46
1644 265 50
1189 1585 4
591 686 1
2089 1317 23
1309 1193 5
1547 2027 34
597 1354 15
1008 2308 43
1249 1849 35
1261 741 40
1984 1784 7
2424 1279 13
2083 1332 23
1554 2046 34
1759 486 22
803 1518 28
2357 1697 10
2345 1490 38
1035 788 41
602 21...

output:

2369

result:

ok "2369"

Test #33:

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

input:

100000 2
1788 1477 2
1784 1471 2
1385 937 1
1780 1479 2
1388 933 1
1789 1479 2
1789 1468 2
1781 1472 2
1773 1462 2
1783 1479 2
1775 1480 2
1378 937 1
1385 934 1
1783 1466 2
1378 945 1
1379 935 1
1782 1476 2
1377 926 1
1782 1464 2
1387 933 1
1777 1461 2
1384 940 1
1389 936 1
1380 936 1
1783 1463 2
17...

output:

514

result:

ok "514"

Test #34:

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

input:

100000 2
36486 67 2
174030 85 1
136529 52 1
5970 23 1
6203 12 2
76224 49 1
19460 11 1
5564 60 1
57857 60 1
15898 35 2
119498 19 2
16662 63 1
240026 26 2
172445 25 1
23395 37 2
144418 24 1
31079 54 1
61178 14 2
204176 70 1
216048 80 2
33352 82 2
133586 99 1
21122 15 2
204337 28 2
68832 26 2
91109 72 ...

output:

0

result:

ok "0"

Test #35:

score: 0
Accepted
time: 33ms
memory: 26340kb

input:

100000 2
74 120032 2
95 120943 2
94 135725 1
33 218968 2
47 13092 2
45 227887 2
31 124133 2
71 207029 2
86 79332 1
41 20737 2
26 134569 1
28 84365 2
52 176305 2
97 238550 2
97 92619 2
44 89007 1
14 6603 2
1 205551 2
81 166554 2
90 10254 1
33 137284 1
90 184588 1
45 239736 1
1 64875 1
2 131420 2
65 2...

output:

0

result:

ok "0"

Test #36:

score: 0
Accepted
time: 30ms
memory: 27420kb

input:

100000 2
59 1 1
96 64 1
91 61 1
28 61 1
58 76 1
18 5 1
24 28 2
37 98 2
79 77 1
18 69 2
70 27 1
34 29 2
88 74 1
65 42 2
87 80 2
25 11 1
70 34 2
29 80 2
51 16 1
46 41 1
58 40 2
66 21 2
96 55 2
8 43 1
37 4 2
73 77 1
11 86 2
94 11 2
12 67 2
19 13 2
99 24 2
9 99 1
48 73 1
5 6 1
20 80 2
44 82 1
26 25 2
93...

output:

0

result:

ok "0"

Test #37:

score: 0
Accepted
time: 159ms
memory: 29260kb

input:

100000 2
217911 141763 2
236124 11544 1
156290 100656 1
114239 30351 2
247916 179714 2
40659 62421 1
127626 134660 2
63120 191748 2
203734 50722 1
67936 184381 1
227868 218433 1
92707 164419 1
20046 162260 2
122348 65201 2
205553 128152 2
191601 54256 2
62654 193305 1
186606 15410 1
59826 70523 2
40...

output:

2

result:

ok "2"

Test #38:

score: 0
Accepted
time: 140ms
memory: 29572kb

input:

100000 2
15413 149140 2
236800 178129 1
29071 17608 1
230087 175593 2
167535 74555 2
88249 5322 1
4403 9805 2
151617 220975 2
57309 21589 1
8611 44583 1
181225 126142 1
114847 209174 1
44986 24397 2
234327 225918 2
202795 14790 2
218309 173982 2
20157 48923 1
208084 235045 1
38574 204675 2
115484 44...

output:

1

result:

ok "1"

Test #39:

score: 0
Accepted
time: 30ms
memory: 27056kb

input:

50 2
52547 181229 2
143425 5985 2
17983 125499 2
227602 249352 2
69546 10367 2
216436 148693 2
112908 151510 1
87734 88673 1
12446 134019 2
121084 12791 2
246076 218077 1
240942 83945 2
168826 174878 1
233255 40987 1
44028 949 1
186998 97350 1
137740 102373 1
107664 37143 2
237367 208404 2
2476 1490...

output:

3905

result:

ok "3905"

Test #40:

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

input:

50 4
19416 170790 1
45908 158405 4
201727 136638 3
187875 17411 4
218329 119863 2
201515 187536 3
12807 212010 3
18469 194478 1
83163 226834 1
44639 105267 4
42526 233217 2
225676 116107 4
57307 36508 4
160496 36788 2
55714 33882 4
191284 136464 3
47286 28856 4
249064 78407 2
162095 22440 3
160556 1...

output:

44324

result:

ok "44324"

Test #41:

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

input:

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

output:

3

result:

ok "3"

Test #42:

score: 0
Accepted
time: 29ms
memory: 26592kb

input:

50 8
10 157992 6
7 86779 8
2 177602 7
1 96442 8
7 245733 1
1 210319 3
9 154803 7
5 68122 7
9 236229 8
5 2860 8
10 65254 2
6 11402 7
2 135893 8
1 180830 3
4 89240 3
3 127926 4
5 215412 8
10 28803 1
4 239829 4
7 25868 3
6 119389 2
10 98856 5
6 47277 2
5 86791 6
3 31101 2
10 109594 3
4 107802 2
4 22175...

output:

41135

result:

ok "41135"

Test #43:

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

input:

50 8
50743 9 4
26844 9 5
68914 10 3
107120 4 3
121264 1 8
218194 4 4
124996 2 8
26240 8 3
246677 7 8
182249 6 2
199421 4 1
88306 5 6
211451 7 2
22948 10 3
191362 8 6
115723 1 8
57016 5 2
149528 1 3
220680 3 7
70752 2 5
195040 3 2
91148 3 7
5172 4 4
87559 7 3
52201 1 2
135075 5 4
84779 6 5
243428 10 ...

output:

55315

result:

ok "55315"

Test #44:

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

input:

50 8
3075 53306 3
158469 16779 5
202552 47792 5
124629 217615 7
146430 217882 6
58755 13683 1
166211 90462 1
132598 19880 4
232761 2743 4
113721 235922 4
146740 234883 2
231933 247931 4
79903 86022 3
84964 194303 3
91159 205989 2
128855 53359 5
112062 191564 7
231873 77982 3
94345 147129 1
240290 17...

output:

89417

result:

ok "89417"

Test #45:

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

input:

50 16
36818 81187 13
245418 81428 1
43491 182339 12
148080 16462 4
76879 22495 3
170445 177381 13
212988 4992 16
18035 14107 13
74453 70608 13
177301 105991 15
96072 181215 1
134972 82769 6
230025 229122 8
16374 4071 16
175917 171022 7
175490 159164 2
207808 184113 11
153605 47459 5
47120 29594 5
20...

output:

139905

result:

ok "139905"

Test #46:

score: 0
Accepted
time: 30ms
memory: 26496kb

input:

50 32
12053 112919 28
74894 77182 15
216570 106256 29
57628 226520 20
128899 5394 13
181399 172725 27
13800 56239 32
80435 237682 10
39335 139550 9
114616 117103 25
195298 9113 23
168305 202017 14
249215 199615 5
215805 128242 3
58839 226979 24
157794 177836 22
247815 24571 6
233669 235426 9
158882 ...

output:

237645

result:

ok "237645"

Test #47:

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

input:

50 2
188879 242305 2
40016 98840 2
35172 244235 2
93 161639 2
61538 239134 2
11158 164951 2
43717 222860 1
175166 133347 1
11694 204769 2
129963 4503 2
70273 5265 1
155603 220889 2
33919 97998 1
238542 219802 1
8579 13580 1
236838 14967 1
189813 249145 1
69913 148764 2
142112 64623 2
121176 111461 1...

output:

3261

result:

ok "3261"

Test #48:

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

input:

50 4
174920 152934 1
193490 9100 4
193404 65984 3
37329 210201 4
14168 42159 2
69 159466 3
183843 199065 3
203033 26270 1
231253 6030 1
210915 50744 4
175515 57690 2
15366 20507 4
122233 34188 4
167739 131927 2
25837 168460 4
221728 45906 3
73062 74388 4
206951 201943 2
23449 249542 3
228447 6992 2
...

output:

22754

result:

ok "22754"

Test #49:

score: 0
Accepted
time: 26ms
memory: 26964kb

input:

50 8
8928 1515 3
174311 244453 5
182143 203611 5
242229 197370 7
249602 232386 6
137943 87187 1
149821 93702 1
236231 5846 4
12043 8077 4
7198 624 4
249807 15838 2
197656 16943 4
14849 56404 3
123882 182813 3
168794 225356 2
246813 78026 5
21515 169463 7
73012 77967 3
171555 237553 1
46316 213275 1
...

output:

91496

result:

ok "91496"

Test #50:

score: 0
Accepted
time: 29ms
memory: 26560kb

input:

50 16
219554 235053 13
186720 220528 1
52113 49212 12
96687 212704 4
237262 18614 3
177726 227872 13
175629 38285 16
230604 208555 13
212246 229553 13
215117 98623 15
216773 235542 1
6799 39263 6
46898 43735 8
248295 56872 16
218968 63152 7
243031 193910 2
95320 20717 11
27452 47607 5
31723 224141 5...

output:

211777

result:

ok "211777"

Test #51:

score: 0
Accepted
time: 26ms
memory: 25880kb

input:

50 32
80529 28498 28
82316 108794 15
245995 15287 29
161468 233299 20
221296 141553 13
175168 138955 27
59519 57437 32
147526 81153 10
31910 2235 9
237034 33489 25
147882 66968 23
53406 115883 14
56552 244209 5
6588 223629 3
90372 230337 24
33964 102877 22
15768 25912 6
168090 202674 9
184250 96602 ...

output:

241210

result:

ok "241210"

Test #52:

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

input:

50 8
201207 229218 6
8758 116941 1
176312 174227 3
136686 116941 2
176935 43193 5
4362 90547 8
137823 124063 4
200463 231157 6
200864 230815 6
7237 116960 1
137783 123958 4
117818 94157 7
138158 116698 2
117036 94259 7
201852 229230 6
137740 116216 2
201682 230909 6
176426 174210 3
138163 124967 4
1...

output:

195095

result:

ok "195095"

Test #53:

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

input:

50 2
31855 42007 1
32484 41185 1
32903 41050 1
31657 41871 1
43395 29831 2
42162 30534 2
33088 41310 1
42593 29836 2
41766 31015 2
32354 42173 1
31619 41007 1
43561 30109 2
43602 31028 2
42410 29634 2
43332 29827 2
42718 29300 2
33439 42078 1
32699 41807 1
33214 41896 1
33451 41640 1
43479 29226 2
4...

output:

9408

result:

ok "9408"

Test #54:

score: 0
Accepted
time: 30ms
memory: 26532kb

input:

50 2
14272 35440 2
219477 39446 2
80539 131496 2
125000 250000 1
60501 200566 2
60234 96288 2
47192 131345 2
164895 228294 2
146589 73416 2
250000 125000 1
246682 162576 2
218151 120595 2
23436 247070 2
173532 97740 2
163383 226583 2
243141 31598 2
236382 51469 2
152041 91412 2
74632 172225 2
36722 ...

output:

13781

result:

ok "13781"

Test #55:

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

input:

50 3
5471 89953 2
1104 85308 3
92885 129934 2
71999 75161 2
56406 17105 2
30624 221356 3
60511 76269 2
176219 242233 3
159708 43597 3
68047 154897 2
106928 26053 3
113540 149397 3
155718 178376 3
160591 96438 3
157428 155105 3
7406 203619 3
32658 137320 3
22860 56373 2
250000 125000 1
241875 203247 ...

output:

39692

result:

ok "39692"

Test #56:

score: 0
Accepted
time: 30ms
memory: 27008kb

input:

50 10
175284 144856 8
167748 145778 6
146691 144062 7
127833 226984 2
66137 88637 4
242497 155966 2
178328 224606 9
185190 167349 2
146796 242430 3
216203 188370 4
165195 230347 2
28299 220176 4
250000 125000 1
71533 144000 6
1 125000 1
220551 96103 8
166592 124048 7
200519 130117 3
90178 198923 7
1...

output:

100558

result:

ok "100558"

Test #57:

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

input:

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

output:

2

result:

ok "2"

Test #58:

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

input:

150 8
5 125361 5
7 36703 6
2 64557 3
5 167217 1
9 238423 6
7 38560 7
6 202678 3
9 45635 2
6 175684 8
3 188025 1
9 72814 6
1 187551 3
5 1304 4
4 95643 5
9 98134 3
1 197269 3
10 102708 1
10 111624 3
6 15727 5
3 74726 1
9 82490 4
10 117649 7
10 98426 8
5 166835 3
3 129578 6
1 227559 1
8 19416 1
9 57469...

output:

12372

result:

ok "12372"

Test #59:

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

input:

150 8
1712 6 4
98828 6 7
105696 10 4
94796 2 6
220394 10 7
232542 2 3
91134 5 7
11844 6 2
225858 2 2
21958 1 2
174991 10 5
228879 9 3
135778 8 8
142446 7 6
194396 6 7
88775 6 5
120851 10 1
55808 10 1
68159 1 4
2212 7 1
240461 9 6
178307 4 4
185552 7 6
74912 3 7
154171 1 5
6706 9 6
59432 4 6
115107 5...

output:

6204

result:

ok "6204"

Test #60:

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

input:

150 2
96837 238277 1
138182 188058 1
23025 138131 1
78591 78554 2
192429 233258 2
238051 6737 1
123113 184022 1
53094 128844 2
204138 133448 2
169341 119408 2
245959 17829 2
177362 159907 2
136574 90359 1
178484 11777 1
115869 25098 1
229523 228648 1
175817 133824 1
186520 144732 2
64586 38926 2
210...

output:

2470

result:

ok "2470"

Test #61:

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

input:

150 5
23106 93151 3
2928 41354 2
148233 243152 4
33445 196744 4
93034 70106 3
208895 220786 2
202542 5680 2
110478 32305 4
142560 39860 3
163993 166854 4
67072 95392 3
37513 77443 4
183170 174001 2
71244 22590 2
68284 88614 2
23907 73057 2
238891 213573 1
85347 154172 5
123534 179431 1
87944 171618 ...

output:

24192

result:

ok "24192"

Test #62:

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

input:

150 16
38954 132967 7
7689 114533 7
146856 239784 12
134288 57409 14
129878 135790 10
176376 5786 6
16089 1683 4
156649 214445 1
151385 153814 1
109997 156186 4
199651 247528 12
144916 4901 7
25961 156064 14
82272 148038 12
184576 105463 7
202202 147658 9
42497 51181 11
170235 115263 9
41544 193154 ...

output:

72940

result:

ok "72940"

Test #63:

score: 0
Accepted
time: 39ms
memory: 26396kb

input:

150 40
239911 22350 6
112320 49961 19
50696 106114 33
88041 97403 35
9272 207274 28
81358 157300 40
70916 126923 9
239523 50997 30
229931 231518 33
53203 53758 28
35697 18062 35
201004 218151 38
45870 223741 6
171614 163979 21
234605 114111 28
69455 28311 13
58221 97100 9
171706 228656 2
113139 2155...

output:

186476

result:

ok "186476"

Test #64:

score: 0
Accepted
time: 30ms
memory: 26788kb

input:

150 150
34837 216110 32
70876 23943 125
229832 160342 65
123474 61800 49
204192 174678 77
77915 46658 69
15185 64177 18
151483 20313 80
28354 93114 52
72478 4386 149
1888 126477 31
43249 108331 101
78186 90309 66
243926 174368 44
154454 168051 98
95285 50247 141
26699 36110 76
140805 239542 43
16899...

output:

247698

result:

ok "247698"

Test #65:

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

input:

150 2
232692 209705 1
213237 233982 1
14018 5888 1
118386 221456 2
238165 61976 2
25262 114100 1
192629 207213 1
78797 14944 2
3493 13226 2
31152 191576 2
146062 15463 2
36050 60758 2
88414 240973 1
1225 8872 1
57043 19380 1
35662 79900 1
180447 36682 1
2829 33689 2
154788 216359 2
71025 214591 2
14...

output:

1142

result:

ok "1142"

Test #66:

score: 0
Accepted
time: 26ms
memory: 26668kb

input:

150 5
198456 105619 3
203203 64684 2
200202 144600 4
178405 249607 4
55800 16139 3
197889 14171 2
44638 69525 2
27055 207620 4
245085 168073 3
186966 239437 4
245056 204337 3
21770 148802 4
59244 221594 2
215166 233211 2
229671 142542 2
123279 65459 2
15691 239866 1
22059 138300 5
115899 135576 1
24...

output:

18518

result:

ok "18518"

Test #67:

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

input:

150 16
39632 4844 7
11656 33765 7
248114 17679 12
21434 204889 14
29951 210331 10
246487 194055 6
25224 6767 4
214524 225933 1
239605 13547 1
163190 2716 4
48930 198407 12
38589 227979 7
138062 226303 14
55378 232336 12
229381 31353 7
3122 233129 9
142560 212061 11
43412 204836 9
12605 40065 10
1039...

output:

74919

result:

ok "74919"

Test #68:

score: 0
Accepted
time: 31ms
memory: 27000kb

input:

150 40
79712 42748 6
12540 21772 19
224365 8910 33
75378 157151 35
232687 241475 28
56722 51874 40
29597 17184 9
6434 48270 30
25246 70401 33
249128 239270 28
201383 145452 35
3849 15209 38
248482 174380 6
196845 213937 21
198806 26143 28
219506 55136 13
228219 210543 9
20562 31493 2
186801 73810 38...

output:

221056

result:

ok "221056"

Test #69:

score: 0
Accepted
time: 33ms
memory: 27288kb

input:

150 150
25054 60699 32
214161 39846 125
14192 25155 65
232382 202954 49
2968 168043 77
171411 6483 69
88483 235964 18
237109 4306 80
11005 204014 52
225733 185902 149
15314 19958 31
63415 16034 101
20440 39654 66
190668 45933 44
41670 190444 98
79777 13790 141
48224 243374 76
175443 152655 43
16339 ...

output:

249253

result:

ok "249253"

Test #70:

score: 0
Accepted
time: 29ms
memory: 27020kb

input:

150 16
128856 164738 11
130115 78643 16
247342 227208 14
233030 190252 9
129788 36056 7
67732 37830 2
5446 164469 13
128140 165218 11
184314 175794 8
131105 111737 4
129237 78270 16
185570 174212 8
131218 112662 4
67622 36925 2
150547 66281 15
83504 172183 5
74903 31231 1
132804 110767 4
132090 1109...

output:

240199

result:

ok "240199"

Test #71:

score: 0
Accepted
time: 29ms
memory: 27132kb

input:

150 2
233182 232649 2
17857 125707 1
17761 124099 1
233574 231543 2
233637 231511 2
234067 232468 2
234193 232410 2
19207 124162 1
233745 231828 2
233832 232949 2
18106 124046 1
233289 232337 2
233558 232174 2
19274 123845 1
19459 124435 1
17988 123817 1
233919 232879 2
234276 233001 2
18941 124786 ...

output:

212859

result:

ok "212859"

Test #72:

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

input:

150 2
222962 59467 2
68050 237253 2
107140 119003 2
97411 194467 2
43470 195734 2
75565 169936 2
113153 137473 2
125000 250000 1
241089 152947 2
36749 29495 2
7037 71805 2
82173 40372 2
40814 81724 2
217297 191747 2
182686 186588 2
24471 63556 2
78130 87549 2
93565 244863 2
129201 227803 2
6471 1216...

output:

5318

result:

ok "5318"

Test #73:

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

input:

150 3
163536 227687 2
45206 228855 3
147279 97615 2
56809 138087 3
110343 187434 2
128473 188533 3
197327 20155 3
122485 78907 2
57215 48452 3
63293 61874 2
218606 190567 2
176349 103996 3
125000 250000 1
127647 239399 2
210362 12392 3
228607 247396 3
50504 226163 3
236160 11773 2
125000 1 1
179740 ...

output:

10601

result:

ok "10601"

Test #74:

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

input:

150 20
169537 204433 9
173032 146843 17
128258 225327 15
187999 77901 2
171536 203304 16
151713 89707 17
218993 125593 20
174938 191981 6
202743 177772 15
70159 85132 9
225089 233072 10
179230 100648 18
19858 198562 15
144145 35272 4
185734 12579 15
119989 148751 6
241151 207315 15
112822 77972 3
22...

output:

103157

result:

ok "103157"

Test #75:

score: 0
Accepted
time: 29ms
memory: 27316kb

input:

600 2
114624 123319 2
126978 64330 1
156076 9802 1
20692 201461 2
154217 122735 1
142299 182278 1
160289 200678 2
92726 41134 2
2595 178962 1
231571 91875 2
104404 1869 1
173050 139728 1
148201 147986 2
1954 229555 1
219934 10946 1
54170 113791 1
208354 165328 1
58098 151624 2
186697 201157 1
242223...

output:

277

result:

ok "277"

Test #76:

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

input:

600 6
34091 148412 5
9612 53187 6
134323 211700 6
110758 198148 5
115479 67854 1
222109 132332 5
248306 142948 5
168895 151237 6
192150 152658 6
167998 120014 1
74933 16346 2
3954 62236 3
235945 72449 1
232690 173380 1
111549 99952 4
186223 190547 3
222017 125780 1
113834 97766 1
184026 187965 4
138...

output:

13288

result:

ok "13288"

Test #77:

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

input:

600 60
143876 217410 44
119065 74861 43
198262 126485 19
120866 196692 16
218536 176981 20
80627 70861 59
131884 231051 26
215415 181086 46
102920 88759 39
77820 177632 5
81878 61484 40
111704 210590 57
110916 207582 46
172561 104762 39
16658 174283 47
170755 11144 31
124246 134575 60
232270 26225 2...

output:

137200

result:

ok "137200"

Test #78:

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

input:

600 600
136558 125559 456
45448 185045 263
21467 134204 581
227455 74555 222
184073 86763 266
173229 190271 469
228228 223814 313
145502 7299 125
213962 97776 557
178964 142462 291
27279 231153 226
7844 111098 459
187018 119157 241
5703 41173 139
39302 63053 380
107082 43536 383
194530 67276 518
909...

output:

249309

result:

ok "249309"

Test #79:

score: 0
Accepted
time: 38ms
memory: 26448kb

input:

600 2
18537 56360 2
200247 9956 1
194049 22780 1
119111 201067 2
2976 94512 1
27472 76578 1
236669 22255 2
35752 206761 2
56574 248766 1
42461 57627 2
29591 224370 1
14975 222233 1
24852 10648 2
45271 197556 1
129119 67443 1
220595 219636 1
5810 220175 1
84530 84744 2
14649 161272 1
34470 74642 1
71...

output:

198

result:

ok "198"

Test #80:

score: 0
Accepted
time: 31ms
memory: 26388kb

input:

600 6
249033 42131 5
216784 84069 6
168905 98809 6
17610 11149 5
202817 407 1
21660 15055 5
241791 175488 5
200943 43401 6
226746 140549 6
223098 41824 1
171303 107956 2
45314 154073 3
81736 201977 1
45481 244052 1
147499 28802 4
228599 204516 3
112266 221412 1
131085 139718 1
18556 36157 4
147694 5...

output:

10548

result:

ok "10548"

Test #81:

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

input:

600 60
39983 117575 44
207330 202500 43
74123 248948 19
5840 28507 16
59362 216150 20
55202 229211 59
232016 9476 26
244645 184693 46
9987 89446 39
15502 206830 5
232366 173984 40
198681 202289 57
83666 57830 46
245831 211520 39
202473 146249 47
154295 239707 31
179877 139233 60
39596 60789 22
2226 ...

output:

155688

result:

ok "155688"

Test #82:

score: 0
Accepted
time: 36ms
memory: 27096kb

input:

600 600
173655 50437 456
216606 204374 263
84390 163815 581
76199 4305 222
14092 236451 266
48540 230539 469
201101 76516 313
41771 244585 125
104010 115455 557
15525 170642 291
40027 234036 226
39362 234752 459
176909 207515 241
240969 172921 139
225514 229154 380
228836 108639 383
126958 155668 51...

output:

249944

result:

ok "249944"

Test #83:

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

input:

600 600
1 1 572
1 1 155
1 1 374
1 1 313
1 1 94
1 1 38
1 1 589
1 1 89
1 1 70
1 1 388
1 1 101
1 1 551
1 1 113
1 1 355
1 1 116
1 1 197
1 1 289
1 1 65
1 1 535
1 1 292
1 1 206
1 1 124
1 1 411
1 1 455
1 1 577
1 1 63
1 1 49
1 1 389
1 1 528
1 1 369
1 1 239
1 1 444
1 1 25
1 1 13
1 1 318
1 1 352
1 1 160
1 1 5...

output:

0

result:

ok "0"

Test #84:

score: 0
Accepted
time: 30ms
memory: 26012kb

input:

600 60
50875 133757 60
92990 234497 22
21910 140745 41
77336 104369 24
78068 105105 24
51550 133284 60
76969 104867 24
5965 240602 25
157843 207381 5
1037 245955 58
92802 234241 22
71003 187556 20
236976 180766 45
66051 172948 39
71486 50500 28
159474 29879 4
67451 173278 39
120369 194986 8
2193 246...

output:

243485

result:

ok "243485"

Test #85:

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

input:

600 6
62031 232016 4
207443 54721 3
208822 55477 3
74004 24244 6
21169 153483 5
74356 23995 6
208906 54163 3
74427 24848 6
73730 24023 6
135878 107422 1
200949 2527 2
61495 233607 4
61446 233866 4
208265 53967 3
74015 24939 6
200052 1680 2
207774 55766 3
208807 55186 3
201128 2593 2
134616 108799 1
...

output:

228758

result:

ok "228758"

Test #86:

score: 0
Accepted
time: 31ms
memory: 26264kb

input:

600 2
19114 245655 2
19729 245649 2
19554 245078 2
19403 245828 2
73626 73858 1
18929 245142 2
20908 245383 2
20422 246985 2
73495 74743 1
72863 73811 1
73514 74546 1
72530 73525 1
72627 74330 1
73042 74070 1
72447 73887 1
19057 245836 2
73665 74841 1
20367 245836 2
73569 74083 1
19769 246485 2
2070...

output:

170042

result:

ok "170042"

Test #87:

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

input:

600 2
211699 224665 2
36705 22432 2
107068 176683 2
36713 36427 2
124878 197369 2
143701 143970 2
64186 33401 2
29508 41732 2
237294 195745 2
53533 78448 2
239053 83550 2
81834 133072 2
159257 163082 2
71874 9978 2
197518 106721 2
163630 155726 2
142520 74930 2
124104 181153 2
171681 150373 2
42587 ...

output:

5743

result:

ok "5743"

Test #88:

score: 0
Accepted
time: 29ms
memory: 26988kb

input:

600 3
204604 106333 2
235622 25582 3
147637 83786 2
126619 164610 2
100106 148843 2
222203 2588 2
81351 214905 2
169869 28848 2
113468 43073 2
66858 61762 2
43145 17915 2
153640 184325 2
185642 88178 2
122085 171014 3
239121 211676 3
213525 232342 2
178013 229986 3
132414 108734 3
96377 86377 3
5745...

output:

3639

result:

ok "3639"

Test #89:

score: 0
Accepted
time: 35ms
memory: 27128kb

input:

600 50
38973 2823 47
9407 8302 29
118537 234791 41
11031 11730 11
240272 154763 10
139517 150093 48
29452 172524 13
198011 184553 34
912 113097 42
22532 38034 37
184443 65054 25
42777 21559 31
152673 96020 10
167987 118749 24
6289 97125 3
128870 220103 45
88777 194284 7
23608 56636 43
67731 237750 2...

output:

114289

result:

ok "114289"

Test #90:

score: 0
Accepted
time: 53ms
memory: 27564kb

input:

2500 2500
27533 147153 2271
186392 182631 851
70342 103530 329
231270 122875 2035
163509 61132 1406
192011 229422 1501
206856 219848 2405
78671 169913 687
155282 45472 1953
184224 101035 1071
140394 58093 122
56300 133349 2276
230347 243563 959
205818 178043 1754
234914 225848 599
116098 93001 1107
...

output:

249838

result:

ok "249838"

Test #91:

score: 0
Accepted
time: 39ms
memory: 27404kb

input:

2500 250
172678 187722 135
249978 189036 44
228144 7096 43
194147 98284 115
231934 174847 176
41550 79288 185
161244 116672 182
206683 57269 113
109389 55520 174
192347 12426 4
76805 139547 96
30471 128372 201
118686 176879 115
51210 67395 181
97108 15676 245
140770 58011 33
158409 209883 33
181971 ...

output:

153115

result:

ok "153115"

Test #92:

score: 0
Accepted
time: 46ms
memory: 27144kb

input:

2500 25
62582 128338 17
236967 242547 5
106324 130622 14
131034 227760 5
228793 211244 3
47647 171270 9
17833 36145 14
202597 138231 19
146396 115864 10
178127 143684 18
169232 182669 17
29955 235831 15
3589 31458 17
93260 199962 24
215984 138877 20
215929 222462 15
230137 121864 24
215531 236694 21...

output:

26095

result:

ok "26095"

Test #93:

score: 0
Accepted
time: 31ms
memory: 26964kb

input:

2500 2
249879 39393 1
222745 39490 1
6497 100173 2
30991 57944 1
85060 211407 1
108938 59908 2
21828 150426 1
171605 1876 1
106934 106424 1
35810 238632 1
230437 13522 2
226678 123750 2
55936 62505 2
195400 123577 1
246282 24017 1
114869 182397 2
13610 150448 2
56239 42901 2
70633 186980 1
115097 14...

output:

60

result:

ok "60"

Test #94:

score: 0
Accepted
time: 48ms
memory: 27504kb

input:

2500 2500
6324 35685 2271
202190 103270 851
2843 70958 329
1705 212063 2035
3866 11421 1406
89336 50245 1501
82283 99190 2405
136421 140484 687
221462 29544 1953
246757 35145 1071
203298 234082 122
225835 183142 2276
81304 82951 959
72328 4322 1754
54626 48943 599
106729 179764 1107
21548 204518 117...

output:

249970

result:

ok "249970"

Test #95:

score: 0
Accepted
time: 43ms
memory: 27092kb

input:

2500 250
57865 45912 135
79783 30746 44
246994 125631 43
128310 24014 115
13473 145567 176
205955 174869 185
162730 184995 182
214064 12141 113
168673 107215 174
246828 239895 4
73159 26491 96
72415 84102 201
61710 29284 115
63082 192573 181
100570 137077 245
230419 215108 33
175182 11682 33
1173 23...

output:

181045

result:

ok "181045"

Test #96:

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

input:

2500 25
26734 26911 17
192419 24059 5
66032 61430 14
189256 132180 5
600 207454 3
209917 77941 9
50616 187603 14
9284 64459 19
125135 49409 10
21322 81431 18
14542 125538 17
213687 225495 15
1849 10456 17
209065 30346 24
26099 226662 20
246925 234609 15
126331 240705 24
10493 24149 21
227302 174246 ...

output:

17878

result:

ok "17878"

Test #97:

score: 0
Accepted
time: 31ms
memory: 26520kb

input:

2500 2
175909 199173 1
34113 42935 1
20583 30134 2
86861 2065 1
99433 210866 1
136879 240557 2
6296 25486 1
28460 38797 1
18171 51846 1
19993 17068 1
181310 77392 2
114657 196580 2
198864 104721 2
238141 247669 1
225193 240175 1
60118 80683 2
57954 218975 2
12822 5693 2
97050 139209 1
216519 196312 ...

output:

52

result:

ok "52"

Test #98:

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

input:

2500 2500
1 1 572
1 1 302
1 1 2251
1 1 1402
1 1 420
1 1 2283
1 1 310
1 1 40
1 1 1075
1 1 2500
1 1 1035
1 1 1985
1 1 2379
1 1 2222
1 1 477
1 1 1749
1 1 406
1 1 1822
1 1 2214
1 1 852
1 1 839
1 1 2124
1 1 1131
1 1 1827
1 1 1457
1 1 1038
1 1 2394
1 1 2101
1 1 906
1 1 564
1 1 1225
1 1 1477
1 1 757
1 1 16...

output:

0

result:

ok "0"

Test #99:

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

input:

2500 60
83449 218104 15
207915 43972 39
32450 244103 5
163360 30462 30
196206 175683 10
173944 91180 48
124902 22629 51
219283 106693 16
31947 244846 5
190656 89071 60
128740 225203 28
96291 133622 45
163807 63235 3
196013 175869 10
124009 22346 51
145185 11454 21
124468 10919 47
50231 185937 18
116...

output:

241065

result:

ok "241065"

Test #100:

score: 0
Accepted
time: 36ms
memory: 25932kb

input:

2500 6
239022 245571 6
172750 87206 1
69767 243933 4
185064 103660 2
104104 87934 3
184669 105200 2
173669 87510 1
70550 242544 4
173723 86831 1
111936 66056 5
70553 242783 4
69488 242406 4
184609 104638 2
102904 87988 3
71080 243616 4
238555 246305 6
103104 87368 3
113171 65637 5
104088 88571 3
172...

output:

178357

result:

ok "178357"

Test #101:

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

input:

2500 2
168306 46140 1
169482 45605 1
169516 46017 1
162004 228762 2
162355 227242 2
161722 229112 2
167879 47085 1
169673 47059 1
168494 46761 1
167878 46630 1
161681 228123 2
167833 47065 1
168090 46911 1
169294 46524 1
169488 46539 1
162409 227927 2
168037 45566 1
168941 45988 1
167804 46895 1
168...

output:

180088

result:

ok "180088"

Test #102:

score: 0
Accepted
time: 43ms
memory: 26192kb

input:

2500 2
44764 123590 2
192572 80935 2
43394 1549 2
74121 75273 2
171138 33932 2
110615 107148 2
114004 4054 2
109066 56396 2
142041 23182 2
4058 215674 2
164140 84033 2
57395 86536 2
100028 172453 2
101700 163693 2
110849 226922 2
175180 59357 2
247985 151531 2
63016 63105 2
72114 130442 2
237129 166...

output:

1339

result:

ok "1339"

Test #103:

score: 0
Accepted
time: 50ms
memory: 26312kb

input:

2500 3
67301 113107 2
65575 57238 2
96025 233903 2
161686 197933 2
158323 73988 3
169185 145279 3
21443 57812 2
237597 235238 2
131926 227219 3
237926 166138 2
20149 223777 2
174285 127221 2
19680 18722 2
228877 162886 3
72839 87127 2
207617 248034 3
180519 109868 3
46176 134074 3
50942 98718 3
5331...

output:

1511

result:

ok "1511"

Test #104:

score: 0
Accepted
time: 30ms
memory: 25832kb

input:

2500 100
222621 81648 66
114247 27752 88
63853 247624 94
112824 29768 50
142894 114214 72
160321 118539 16
245524 208575 72
192974 124305 39
8830 171341 19
12826 65105 11
247394 157734 73
180321 180029 12
40084 141534 14
49996 238873 84
31667 213643 33
198010 134890 76
136256 242076 98
173452 120912...

output:

93070

result:

ok "93070"

Test #105:

score: 0
Accepted
time: 417ms
memory: 29356kb

input:

100000 1000
245055 75 491
235250 88 172
42553 22 447
140416 68 798
106923 96 80
43722 93 525
111310 47 75
110220 93 279
69200 34 113
42229 94 361
78738 98 477
41479 34 732
219209 70 302
65610 16 875
238541 84 85
50633 9 280
129084 10 413
83443 92 403
91864 98 118
222235 1 730
197829 6 417
21945 58 5...

output:

12066

result:

ok "12066"

Test #106:

score: 0
Accepted
time: 762ms
memory: 31956kb

input:

100000 1000
85 240027 43
76 186707 286
46 212585 313
18 202025 686
44 52 954
83 62179 727
2 37352 440
37 183109 808
29 179121 595
78 234809 25
71 226756 953
85 5339 22
20 103655 215
36 64859 857
84 4900 454
36 8270 31
71 74458 679
58 103310 770
27 80876 232
17 166229 331
6 90464 709
14 172166 702
13...

output:

11978

result:

ok "11978"

Test #107:

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

input:

100000 1000
76 5 733
94 10 908
63 52 422
33 96 575
23 41 456
88 63 57
77 43 464
26 32 675
97 33 529
73 80 610
74 51 545
85 50 153
81 30 36
51 67 220
19 43 44
31 77 66
24 64 450
74 29 319
20 99 68
77 70 671
86 24 636
12 99 83
12 28 54
65 40 120
69 57 295
78 66 534
75 71 338
66 22 96
33 45 329
89 90 1...

output:

21

result:

ok "21"

Test #108:

score: 0
Accepted
time: 802ms
memory: 41352kb

input:

100000 100000
1 1 96060
1 1 34612
1 1 90735
1 1 97985
1 1 34442
1 1 72679
1 1 68136
1 1 3933
1 1 21995
1 1 32448
1 1 1114
1 1 22393
1 1 91375
1 1 56499
1 1 42096
1 1 96553
1 1 63761
1 1 2783
1 1 61991
1 1 19961
1 1 82056
1 1 22383
1 1 98572
1 1 55978
1 1 24063
1 1 95608
1 1 46070
1 1 44551
1 1 85350...

output:

0

result:

ok "0"

Test #109:

score: 0
Accepted
time: 1603ms
memory: 43768kb

input:

100000 100000
106657 186816 41487
137952 90873 87656
19535 23880 93654
37707 235689 78167
31078 69344 22985
51794 65809 10104
74604 22962 57736
159323 99005 11293
228729 95690 28660
2610 114413 41360
28842 52764 32901
204933 64437 6444
30914 107310 98109
40295 84045 42392
38548 36537 14171
67937 238...

output:

249994

result:

ok "249994"

Test #110:

score: 0
Accepted
time: 1084ms
memory: 36888kb

input:

100000 30000
36372 66756 22884
171675 21063 11213
97934 34338 5945
133388 91677 2380
15664 245854 25518
165274 90383 5210
153675 202064 494
400 69646 27754
31138 140885 14373
234268 170051 23874
68637 210190 608
155230 77447 1139
47046 118367 27576
117485 204985 15499
42942 181264 8784
194945 4715 1...

output:

249856

result:

ok "249856"

Test #111:

score: 0
Accepted
time: 854ms
memory: 34012kb

input:

100000 10000
63593 105297 7915
163429 134639 8913
87915 144447 8776
84259 198753 1284
84596 78778 4741
129383 101327 9862
232122 23876 527
20791 187598 1636
184645 84736 3197
237501 245317 8595
127632 52041 4601
81496 161854 1773
195741 96284 7341
25241 196424 1228
97918 231145 1943
54007 41255 1180...

output:

207351

result:

ok "207351"

Test #112:

score: 0
Accepted
time: 766ms
memory: 31696kb

input:

100000 3000
178956 210854 256
34510 102726 2256
142870 194984 981
52191 217488 463
14523 163394 984
21231 96208 1954
167562 6128 1359
211948 231587 2962
25797 134066 942
69133 126633 1629
105843 45113 1832
201623 11434 1903
27404 246654 1038
60553 26220 21
97648 66204 159
194306 39359 1482
106752 60...

output:

106240

result:

ok "106240"

Test #113:

score: 0
Accepted
time: 653ms
memory: 30348kb

input:

100000 1000
223160 99216 605
121506 231079 960
73611 28033 734
6802 140683 690
109594 249437 762
175650 133226 280
10649 6073 283
233472 230051 764
238368 162542 186
170621 109162 906
70347 12138 345
22721 110630 485
123900 113199 756
219623 28164 930
44264 163555 127
117436 232738 900
129110 244271...

output:

54134

result:

ok "54134"

Test #114:

score: 0
Accepted
time: 627ms
memory: 29476kb

input:

100000 300
34039 230042 168
52397 249655 217
174343 165862 45
237079 203625 194
136446 106216 250
237718 122561 248
167406 195532 292
117286 192771 174
172460 8976 172
133494 165143 208
217250 191095 17
131580 201068 128
157054 247863 130
209021 19776 122
57778 220618 230
35094 19337 277
30386 37105...

output:

24968

result:

ok "24968"

Test #115:

score: 0
Accepted
time: 751ms
memory: 29544kb

input:

100000 100
88855 233455 83
167108 47778 24
2580 177827 51
107261 117227 76
26634 160351 27
64678 33061 1
75693 173315 94
60815 156008 49
66279 143216 89
238860 88866 40
118310 30909 41
87763 213940 50
113963 99301 85
237553 176928 46
225020 91863 97
177685 66690 74
130002 156021 94
26852 152276 96
2...

output:

11578

result:

ok "11578"

Test #116:

score: 0
Accepted
time: 751ms
memory: 28252kb

input:

100000 30
225067 158362 5
64268 198153 13
41976 227569 23
214050 248289 11
5027 54080 17
26045 11521 5
36015 116580 3
32379 211598 5
34645 80972 13
163133 249605 24
94607 189727 8
168041 113603 29
192621 146867 6
192344 172971 22
123171 31815 9
186569 205636 2
121369 102490 14
200252 76057 17
170394...

output:

4281

result:

ok "4281"

Test #117:

score: 0
Accepted
time: 849ms
memory: 28960kb

input:

100000 10
176899 244643 1
4709 14116 10
14984 58094 10
157171 51919 10
206592 216025 9
113135 181385 3
171886 223672 8
187367 210369 5
73993 26675 1
36410 68519 7
234891 39685 3
58125 148466 9
131059 154797 7
149177 24363 6
208612 191584 3
66650 13264 3
234404 118069 6
79073 249794 9
47918 599 5
118...

output:

1219

result:

ok "1219"

Test #118:

score: 0
Accepted
time: 394ms
memory: 29644kb

input:

100000 3
128256 41083 2
137790 79671 1
42642 92874 3
60022 247188 1
200656 52987 1
121369 106482 3
48495 130702 1
53900 19573 1
126534 235208 1
150680 172787 2
163202 5042 1
225390 123223 3
205555 1643 3
68030 129377 1
202365 28593 2
211054 236900 1
215897 24876 1
107961 107319 1
139505 122932 3
228...

output:

43

result:

ok "43"

Test #119:

score: 0
Accepted
time: 1461ms
memory: 43936kb

input:

100000 100000
102184 69924 41487
59339 222887 87656
197831 41703 93654
249661 216165 78167
424 55804 22985
158886 236518 10104
46986 8098 57736
244435 225335 11293
229351 46001 28660
85 200220 41360
96880 206011 32901
34907 106001 6444
115470 223315 98109
184172 46065 42392
188580 9603 14171
72797 2...

output:

249996

result:

ok "249996"

Test #120:

score: 0
Accepted
time: 976ms
memory: 37320kb

input:

100000 30000
37063 105149 22884
11290 246215 11213
25337 183895 5945
130763 150879 2380
24017 72402 25518
81927 135757 5210
57506 4013 494
56698 27845 27754
199110 16006 14373
200144 241946 23874
211440 77300 608
210542 86343 1139
249563 18891 27576
6804 215249 15499
241519 47688 8784
23699 14424 16...

output:

249943

result:

ok "249943"

Test #121:

score: 0
Accepted
time: 771ms
memory: 35104kb

input:

100000 10000
234029 193575 7915
165599 177250 8913
191984 20562 8776
24506 5059 1284
63786 154102 4741
237452 205543 9862
18459 30814 527
85258 75691 1636
240488 65216 3197
30951 1270 8595
142735 193817 4601
123293 194404 1773
237721 211286 7341
65972 93952 1228
240021 211779 1943
28681 75197 1180
2...

output:

226745

result:

ok "226745"

Test #122:

score: 0
Accepted
time: 584ms
memory: 34036kb

input:

100000 3000
45094 104884 256
244296 88819 2256
209306 54472 981
222847 125803 463
100365 31259 984
237915 243485 1954
246754 194574 1359
27384 25595 2962
56416 245193 942
50691 190644 1629
204765 25366 1832
232315 146966 1903
245354 1294 1038
234003 8671 21
241206 249147 159
239363 247282 1482
18715...

output:

99936

result:

ok "99936"

Test #123:

score: 0
Accepted
time: 926ms
memory: 31312kb

input:

100000 1000
179184 201755 605
10905 105642 960
92045 90129 734
196727 52588 690
40587 233267 762
63680 244367 280
149320 213426 283
56159 12618 764
198394 38785 186
201001 55843 906
71902 102589 345
93654 231720 485
30159 186254 756
202889 60563 930
135609 85764 127
20470 75098 900
6334 182730 67
21...

output:

36841

result:

ok "36841"

Test #124:

score: 0
Accepted
time: 607ms
memory: 30628kb

input:

100000 300
77781 111103 168
17816 241350 217
97487 48894 45
1869 118285 194
79869 123842 250
8517 246401 248
70311 190181 292
48264 160543 174
188998 235989 172
201154 46969 208
47486 230246 17
19989 33733 128
182656 56132 130
52033 48958 122
189729 247809 230
247497 242769 277
61775 125012 261
3131...

output:

14720

result:

ok "14720"

Test #125:

score: 0
Accepted
time: 919ms
memory: 30112kb

input:

100000 100
42929 95011 83
13059 202120 24
149828 32980 51
235785 123958 76
39934 214048 27
44366 93218 1
226276 207834 94
106032 75072 49
17816 185522 89
21702 21152 40
235834 40188 41
219693 245192 50
20518 37984 85
105494 73201 46
149856 221947 97
64102 247546 74
143556 112647 94
239303 11751 96
1...

output:

7083

result:

ok "7083"

Test #126:

score: 0
Accepted
time: 882ms
memory: 30140kb

input:

100000 30
17964 163212 5
235881 225168 13
225154 11211 23
107931 206464 11
149110 224191 17
139687 234709 5
176148 221212 3
19320 35161 5
238696 100738 13
32532 28591 24
30497 213015 8
33532 19455 29
220227 129431 6
44055 169679 22
63798 59209 9
248595 141963 2
157103 179755 14
115086 50441 17
21027...

output:

2603

result:

ok "2603"

Test #127:

score: 0
Accepted
time: 535ms
memory: 29944kb

input:

100000 10
93809 92848 1
132001 145445 10
217460 142071 10
243229 133145 10
123489 21592 9
199677 1599 3
42119 234631 8
53292 43813 5
73938 199782 1
6543 214880 7
25162 18358 3
189845 45287 9
224798 218527 7
221060 9189 6
79172 28327 3
208770 158169 3
239302 100467 6
162608 96328 9
125230 60515 5
229...

output:

772

result:

ok "772"

Test #128:

score: 0
Accepted
time: 301ms
memory: 30684kb

input:

100000 3
4235 17229 2
201181 167025 1
33465 6958 3
61653 228176 1
143646 243799 1
249106 158240 3
249769 227882 1
24812 63466 1
75289 81477 1
5787 45271 2
157676 8932 1
2827 36044 3
114523 242757 3
32700 38415 1
248575 29025 2
149236 199474 1
57177 82831 1
125419 220398 1
79542 4462 3
72725 213869 1...

output:

42

result:

ok "42"

Test #129:

score: 0
Accepted
time: 423ms
memory: 35728kb

input:

100000 60
128455 114928 29
216927 84322 22
117082 111369 6
220956 12479 52
58101 88074 59
124562 196620 16
163051 21378 9
117345 179143 4
84440 201858 38
241440 68145 17
120775 99411 11
38543 185065 10
199926 248263 8
142251 61869 60
119044 178776 4
156749 166714 35
242651 69173 17
81958 48212 56
36...

output:

244133

result:

ok "244133"

Test #130:

score: 0
Accepted
time: 377ms
memory: 33320kb

input:

100000 6
76585 225459 3
228900 243131 5
13502 121759 1
203148 19945 6
203684 19319 6
123848 18549 4
156986 83555 2
203402 19811 6
203302 19452 6
123103 19598 4
122952 18505 4
76868 224900 3
202265 19721 6
11662 121494 1
12907 121657 1
123376 19139 4
76354 225692 3
227314 241355 5
227579 242609 5
765...

output:

220707

result:

ok "220707"

Test #131:

score: 0
Accepted
time: 384ms
memory: 33304kb

input:

100000 2
183962 41268 2
184006 42020 2
126505 244323 1
183949 40688 2
128453 244423 1
127417 243905 1
127513 245503 1
126632 243663 1
183942 40239 2
182526 40587 2
127214 244389 1
184008 41147 2
183355 41669 2
127628 245002 1
126551 244227 1
183339 41764 2
183380 41587 2
127412 244635 1
182785 41834...

output:

201494

result:

ok "201494"

Test #132:

score: 0
Accepted
time: 449ms
memory: 30784kb

input:

100000 2
196486 8120 2
180825 39956 2
146764 69525 2
48824 95232 2
75290 246220 2
114577 59821 2
159797 39369 2
175414 240753 2
248574 56495 2
90153 138275 2
9300 181130 2
224397 45070 2
156171 201009 2
15397 45784 2
38809 75009 2
35441 138089 2
113072 46973 2
74726 21077 2
33820 104937 2
215864 120...

output:

155

result:

ok "155"

Test #133:

score: 0
Accepted
time: 514ms
memory: 30020kb

input:

100000 3
189391 15107 3
126333 226040 2
11854 110067 2
156705 107272 3
116289 87187 2
206336 154186 2
159994 184184 3
233349 165603 3
25662 179300 3
148474 12626 3
244269 103966 3
224719 81735 3
160818 2615 3
208810 182556 2
165859 196723 2
140130 191960 2
41037 81873 3
109963 229482 3
143449 22101 ...

output:

499

result:

ok "499"

Test #134:

score: 0
Accepted
time: 593ms
memory: 31808kb

input:

100000 100
83422 66816 100
138812 203558 75
176279 113229 69
247947 129188 85
117933 249470 20
108211 111908 47
20894 186275 90
177801 1297 35
78098 168905 14
116304 241566 96
131414 115632 67
215 147853 59
171250 189395 16
244259 137266 8
51585 203718 34
155047 123952 59
231665 110325 87
75186 3747...

output:

14615

result:

ok "14615"
English 繁體中文 简体中文

Server Time: 2024-12-01 20:46:20 | OpenSource Project