QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#376736#2784. Alienshos_lyric41 966ms19776kbC++142.9kb2024-04-04 16:02:192024-04-04 16:02:19

Judging History

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

  • [2024-04-04 16:02:19]
  • 评测
  • 测评结果：41
  • 用时：966ms
  • 内存：19776kb
查看
  • [2024-04-04 16:02:19]
  • 提交

answer

#include "aliens.h"

#include <cassert>
#include <cmath>
#include <cstdint>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <sstream>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>

using namespace std;

using Int = long long;

template <class T1, class T2> ostream &operator<<(ostream &os, const pair<T1, T2> &a) { return os << "(" << a.first << ", " << a.second << ")"; };
template <class T> ostream &operator<<(ostream &os, const vector<T> &as) { const int sz = as.size(); os << "["; for (int i = 0; i < sz; ++i) { if (i >= 256) { os << ", ..."; break; } if (i > 0) { os << ", "; } os << as[i]; } return os << "]"; }
template <class T> void pv(T a, T b) { for (T i = a; i != b; ++i) cerr << *i << " "; cerr << endl; }
template <class T> bool chmin(T &t, const T &f) { if (t > f) { t = f; return true; } return false; }
template <class T> bool chmax(T &t, const T &f) { if (t < f) { t = f; return true; } return false; }
#define COLOR(s) ("\x1b[" s "m")


constexpr Int INF = 1001001001001001001LL;

// needed area below diagonal at x + 1/2
vector<Int> F, FSum;

int xsLen;
vector<Int> xs;

Int calc(Int pena) {
  vector<Int> dp(xsLen + 1, INF);
  dp[0] = 0;
  for (int i = 0; i < xsLen; ++i) for (int j = i + 1; j <= xsLen; ++j) {
    Int cost = 0;
    cost += (FSum[xs[j - 1] + 1] - FSum[xs[i] + 1]);
    cost -= (xs[j - 1] - xs[i]) * F[xs[i]];
    cost += pena;
    chmin(dp[j], dp[i] + cost);
  }
  return dp[xsLen];
}

long long take_photos(int N, int M, int K, std::vector<int> R, std::vector<int> C) {
  F.resize(M);
  for (int x = 0; x < M; ++x) F[x] = 2 * x + 1;
  for (int i = 0; i < N; ++i) {
    Int x = R[i], y = C[i];
    if (x < y) swap(x, y);
    chmin(F[x], 2 * y);
  }
  for (int x = M; --x >= 1; ) chmin(F[x - 1], F[x]);
  FSum.assign(M + 1, 0);
  for (int x = 0; x < M; ++x) FSum[x + 1] = FSum[x] + F[x];
  Int base = 0;
  for (int x = 0; x < M; ++x) base += ((2 * x + 1) - F[x]);
// cerr<<"F = "<<F<<endl;
// cerr<<"base = "<<base<<endl;
  
  xs.clear();
  for (int x = 0; x < M; ++x) if (F[x] < 2 * x + 1 && (x + 1 == M || F[x] < F[x + 1])) xs.push_back(x);
  xsLen = xs.size();
// cerr<<"xs = "<<xs<<endl;
// for(Int pena=0;pena<=20;++pena)cerr<<calc(pena)<<" ";cerr<<endl;
  
  Int lo = -1, hi = (Int)M * M + 1;
  for (; lo + 1 < hi; ) {
    const Int mid = (lo + hi) / 2;
    const auto res0 = calc(mid);
    const auto res1 = calc(mid + 1);
    ((res1 - res0 <= K) ? hi : lo) = mid;
  }
  Int ans = calc(hi) - hi * K;
cerr<<"ans = "<<ans<<endl;
  ans += base;
  return ans;
}

/*
int main() {
  cerr << take_photos(4, 10, 2, {2, 5, 6, 7}, {1, 2, 5, 6}) << endl;
  // 33
  return 0;
}
//*/
Source code, Language: C++14

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 4
Accepted

Test #1:

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

input:

2 6 2
1 4
4 1

output:

098d134608c94f7413faac591054ee35
16

result:

ok Correct answer: answer = 16

Test #2:

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

input:

1 2 1
0 1

output:

098d134608c94f7413faac591054ee35
4

result:

ok Correct answer: answer = 4

Test #3:

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

input:

2 2 2
0 0
1 0

output:

098d134608c94f7413faac591054ee35
4

result:

ok Correct answer: answer = 4

Test #4:

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

input:

2 3 2
0 1
1 1

output:

098d134608c94f7413faac591054ee35
4

result:

ok Correct answer: answer = 4

Test #5:

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

input:

4 4 4
1 3
0 1
2 1
2 2

output:

098d134608c94f7413faac591054ee35
12

result:

ok Correct answer: answer = 12

Test #6:

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

input:

5 8 5
0 5
2 6
7 4
4 5
2 6

output:

098d134608c94f7413faac591054ee35
52

result:

ok Correct answer: answer = 52

Test #7:

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

input:

8 20 8
6 14
5 13
1 8
17 15
6 9
1 9
2 0
17 8

output:

098d134608c94f7413faac591054ee35
210

result:

ok Correct answer: answer = 210

Test #8:

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

input:

10 10 10
2 2
3 6
8 6
8 3
6 9
4 0
8 4
8 1
0 8
8 9

output:

098d134608c94f7413faac591054ee35
88

result:

ok Correct answer: answer = 88

Test #9:

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

input:

10 100 10
98 25
55 31
36 25
38 77
9 82
11 69
88 42
47 49
19 91
61 13

output:

098d134608c94f7413faac591054ee35
7696

result:

ok Correct answer: answer = 7696

Test #10:

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

input:

50 1 50
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:

098d134608c94f7413faac591054ee35
1

result:

ok Correct answer: answer = 1

Test #11:

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

input:

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

output:

098d134608c94f7413faac591054ee35
2374

result:

ok Correct answer: answer = 2374

Test #12:

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

input:

50 100 50
0 20
49 26
21 27
10 67
79 9
38 75
39 27
36 51
75 81
70 37
57 74
57 64
13 76
53 95
25 11
62 37
78 38
39 19
46 7
92 71
40 27
73 11
30 55
60 67
79 48
3 69
1 27
41 54
80 40
50 50
9 49
75 11
90 62
2 71
14 40
30 48
3 53
68 24
99 25
8 49
35 80
31 24
21 11
92 9
4 97
45 61
56 83
68 75
35 84
77 20

output:

098d134608c94f7413faac591054ee35
9502

result:

ok Correct answer: answer = 9502

Test #13:

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

input:

49 7 49
5 3
0 6
6 2
3 3
4 2
3 4
0 3
1 3
2 4
5 1
1 0
2 1
3 0
4 4
1 6
0 5
1 4
6 3
6 6
6 5
4 0
3 5
5 5
2 0
4 5
3 2
0 2
1 5
2 5
6 4
1 1
5 0
0 4
6 0
5 4
2 6
0 1
5 2
4 6
5 6
3 1
3 6
0 0
4 3
1 2
2 2
4 1
2 3
6 1

output:

098d134608c94f7413faac591054ee35
49

result:

ok Correct answer: answer = 49

Test #14:

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

input:

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

output:

098d134608c94f7413faac591054ee35
151

result:

ok Correct answer: answer = 151

Test #15:

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

input:

50 100 50
38 88
6 56
44 94
24 74
30 80
25 75
49 99
10 60
18 68
36 86
7 57
15 65
21 71
32 82
13 63
5 55
11 61
45 95
48 98
47 97
28 78
26 76
40 90
14 64
33 83
23 73
2 52
12 62
19 69
46 96
8 58
35 85
4 54
42 92
39 89
20 70
1 51
37 87
34 84
41 91
22 72
27 77
0 50
31 81
9 59
16 66
29 79
17 67
43 93
3 53

output:

098d134608c94f7413faac591054ee35
7550

result:

ok Correct answer: answer = 7550

Test #16:

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

input:

50 100 50
37 79
7 50
40 90
24 69
27 75
25 70
46 99
9 54
19 62
35 78
8 51
11 60
21 67
30 75
11 57
4 50
10 55
40 92
45 97
41 95
27 73
25 71
38 80
11 57
30 75
24 68
2 49
11 56
20 64
40 92
9 53
35 77
3 49
39 83
37 80
20 67
1 48
36 79
31 76
38 81
21 68
26 71
0 48
27 75
9 53
13 61
27 74
14 62
39 84
3 49

output:

098d134608c94f7413faac591054ee35
7220

result:

ok Correct answer: answer = 7220

Test #17:

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

input:

50 100 50
49 99
48 98
47 97
46 96
45 95
44 94
43 93
42 92
41 91
40 90
39 89
38 88
37 87
36 86
35 85
34 84
33 83
32 82
31 81
30 80
29 79
28 78
27 77
26 76
25 75
24 74
23 73
22 72
21 71
20 70
19 69
18 68
17 67
16 66
15 65
14 64
13 63
12 62
11 61
10 60
9 59
8 58
7 57
6 56
5 55
4 54
3 53
2 52
1 51
0 50

output:

098d134608c94f7413faac591054ee35
7550

result:

ok Correct answer: answer = 7550

Test #18:

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

input:

50 100 50
0 99
0 99
0 99
0 99
0 99
0 99
0 99
0 99
0 99
0 99
0 99
0 99
0 99
0 99
0 99
0 99
0 99
0 99
0 99
0 99
0 99
0 99
0 99
0 99
0 99
0 99
0 99
0 99
0 99
0 99
0 99
0 99
0 99
0 99
0 99
0 99
0 99
0 99
0 99
0 99
0 99
0 99
0 99
0 99
0 99
0 99
0 99
0 99
0 99
0 99

output:

098d134608c94f7413faac591054ee35
10000

result:

ok Correct answer: answer = 10000

Test #19:

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

input:

50 100 50
0 99
1 98
3 98
3 96
3 96
4 93
4 92
5 92
6 91
8 91
9 91
10 90
11 90
12 85
12 82
17 82
19 82
19 81
20 80
21 76
21 76
22 75
22 75
23 73
23 72
24 72
24 71
25 71
25 70
28 68
28 66
29 66
30 64
31 63
31 63
33 62
34 61
36 60
37 60
39 60
40 59
43 59
44 59
45 58
45 57
46 56
47 55
50 53
50 52
51 52

output:

098d134608c94f7413faac591054ee35
10000

result:

ok Correct answer: answer = 10000

Test #20:

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

input:

50 100 50
61 62
12 15
81 81
49 50
78 85
62 69
55 61
57 57
22 25
77 78
2 5
8 12
62 67
49 50
19 25
60 62
71 77
74 74
90 95
33 34
24 26
47 54
45 51
72 75
89 89
18 19
36 38
6 8
1 3
25 26
73 77
35 38
1 4
55 57
85 91
82 86
66 66
18 18
3 5
61 64
32 32
21 22
61 63
79 83
74 80
68 74
72 75
75 81
66 69
51 55

output:

098d134608c94f7413faac591054ee35
624

result:

ok Correct answer: answer = 624

Test #21:

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

input:

50 100 50
0 99
0 99
0 99
0 99
0 99
0 99
0 99
0 99
0 99
0 99
0 99
0 99
0 99
0 99
0 99
0 99
0 99
0 99
0 99
0 99
0 99
0 99
0 99
0 99
0 99
0 99
0 99
0 99
0 99
0 99
0 99
0 99
0 99
0 99
0 99
0 99
0 99
0 99
0 99
0 99
0 99
0 99
0 99
0 99
0 99
0 99
0 99
0 99
0 99
0 99

output:

098d134608c94f7413faac591054ee35
10000

result:

ok Correct answer: answer = 10000

Test #22:

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

input:

1 1 1
0 0

output:

098d134608c94f7413faac591054ee35
1

result:

ok Correct answer: answer = 1

Subtask #2:

score: 12
Accepted

Test #23:

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

input:

2 2 1
0 0
1 1

output:

098d134608c94f7413faac591054ee35
4

result:

ok Correct answer: answer = 4

Test #24:

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

input:

4 3 2
0 0
0 0
0 0
0 0

output:

098d134608c94f7413faac591054ee35
1

result:

ok Correct answer: answer = 1

Test #25:

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

input:

5 5 2
2 2
3 3
4 4
3 3
3 3

output:

098d134608c94f7413faac591054ee35
5

result:

ok Correct answer: answer = 5

Test #26:

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

input:

10 20 3
3 3
15 15
10 10
18 18
4 4
7 7
15 15
2 2
10 10
7 7

output:

098d134608c94f7413faac591054ee35
41

result:

ok Correct answer: answer = 41

Test #27:

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

input:

20 1000 5
737 737
714 714
662 662
163 163
683 683
615 615
23 23
246 246
724 724
90 90
802 802
557 557
146 146
429 429
816 816
164 164
638 638
568 568
957 957
904 904

output:

098d134608c94f7413faac591054ee35
71923

result:

ok Correct answer: answer = 71923

Test #28:

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

input:

200 1000 10
69 69
277 277
350 350
753 753
741 741
849 849
993 993
95 95
928 928
789 789
333 333
795 795
493 493
253 253
661 661
780 780
17 17
394 394
487 487
719 719
426 426
297 297
885 885
323 323
981 981
916 916
0 0
997 997
757 757
374 374
467 467
787 787
297 297
216 216
599 599
62 62
936 936
777 ...

output:

098d134608c94f7413faac591054ee35
77137

result:

ok Correct answer: answer = 77137

Test #29:

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

input:

500 1000 250
599 599
14 14
176 176
963 963
93 93
257 257
403 403
741 741
854 854
862 862
778 778
489 489
711 711
623 623
163 163
750 750
649 649
441 441
245 245
311 311
429 429
756 756
572 572
766 766
837 837
137 137
719 719
244 244
519 519
287 287
251 251
818 818
789 789
305 305
400 400
262 262
359...

output:

098d134608c94f7413faac591054ee35
764

result:

ok Correct answer: answer = 764

Test #30:

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

input:

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

output:

098d134608c94f7413faac591054ee35
250000

result:

ok Correct answer: answer = 250000

Test #31:

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

input:

500 500 500
236 236
200 200
154 154
128 128
344 344
453 453
112 112
10 10
491 491
356 356
299 299
294 294
197 197
441 441
13 13
78 78
287 287
430 430
342 342
63 63
284 284
100 100
315 315
14 14
33 33
292 292
2 2
392 392
383 383
46 46
295 295
401 401
487 487
327 327
127 127
408 408
109 109
71 71
248 ...

output:

098d134608c94f7413faac591054ee35
500

result:

ok Correct answer: answer = 500

Test #32:

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

input:

4 9 2
0 0
3 3
5 5
8 8

output:

098d134608c94f7413faac591054ee35
32

result:

ok Correct answer: answer = 32

Test #33:

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

input:

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

output:

098d134608c94f7413faac591054ee35
130050

result:

ok Correct answer: answer = 130050

Test #34:

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

input:

500 510 49
236 236
200 200
154 154
128 128
344 344
453 453
112 112
10 10
501 501
356 356
299 299
294 294
197 197
441 441
13 13
78 78
287 287
430 430
342 342
63 63
284 284
100 100
315 315
14 14
33 33
292 292
2 2
392 392
383 383
46 46
295 295
401 401
487 487
327 327
127 127
408 408
109 109
71 71
248 2...

output:

098d134608c94f7413faac591054ee35
5110

result:

ok Correct answer: answer = 5110

Test #35:

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

input:

256 256 25
236 236
200 200
154 154
128 128
146 146
177 177
112 112
10 10
185 185
147 147
134 134
138 138
197 197
108 108
13 13
78 78
111 111
99 99
119 119
63 63
59 59
100 100
40 40
14 14
33 33
131 131
2 2
60 60
167 167
46 46
249 249
64 64
98 98
42 42
127 127
195 195
109 109
71 71
248 248
114 114
148...

output:

098d134608c94f7413faac591054ee35
2626

result:

ok Correct answer: answer = 2626

Test #36:

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

input:

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

output:

098d134608c94f7413faac591054ee35
796

result:

ok Correct answer: answer = 796

Test #37:

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

input:

500 500 33
236 236
200 200
154 154
128 128
344 344
453 453
112 112
10 10
491 491
356 356
299 299
294 294
197 197
441 441
13 13
78 78
287 287
430 430
342 342
63 63
284 284
100 100
315 315
14 14
33 33
292 292
2 2
392 392
383 383
46 46
295 295
401 401
487 487
327 327
127 127
408 408
109 109
71 71
248 2...

output:

098d134608c94f7413faac591054ee35
7580

result:

ok Correct answer: answer = 7580

Test #38:

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

input:

500 500 133
236 236
200 200
154 154
128 128
344 344
453 453
112 112
10 10
491 491
356 356
299 299
294 294
197 197
441 441
13 13
78 78
287 287
430 430
342 342
63 63
284 284
100 100
315 315
14 14
33 33
292 292
2 2
392 392
383 383
46 46
295 295
401 401
487 487
327 327
127 127
408 408
109 109
71 71
248 ...

output:

098d134608c94f7413faac591054ee35
1904

result:

ok Correct answer: answer = 1904

Test #39:

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

input:

500 1000 1
390 390
487 487
26 26
108 108
607 607
524 524
626 626
382 382
979 979
365 365
326 326
246 246
433 433
44 44
273 273
608 608
128 128
710 710
891 891
450 450
632 632
643 643
377 377
686 686
341 341
126 126
346 346
413 413
128 128
776 776
389 389
989 989
537 537
37 37
742 742
871 871
647 647...

output:

098d134608c94f7413faac591054ee35
996004

result:

ok Correct answer: answer = 996004

Test #40:

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

input:

500 1000 20
96 96
499 499
640 640
749 749
773 773
160 160
750 750
543 543
150 150
810 810
193 193
227 227
433 433
988 988
632 632
121 121
568 568
445 445
392 392
992 992
863 863
444 444
497 497
618 618
187 187
925 925
767 767
977 977
697 697
172 172
194 194
887 887
217 217
350 350
98 98
420 420
189 ...

output:

098d134608c94f7413faac591054ee35
38817

result:

ok Correct answer: answer = 38817

Test #41:

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

input:

500 1000 100
485 485
28 28
73 73
858 858
838 838
357 357
679 679
550 550
543 543
835 835
618 618
679 679
139 139
347 347
989 989
771 771
611 611
534 534
467 467
162 162
689 689
834 834
963 963
961 961
706 706
198 198
341 341
410 410
914 914
663 663
851 851
564 564
834 834
472 472
251 251
692 692
404...

output:

098d134608c94f7413faac591054ee35
4096

result:

ok Correct answer: answer = 4096

Test #42:

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

input:

500 1 1
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
0 0
...

output:

098d134608c94f7413faac591054ee35
1

result:

ok Correct answer: answer = 1

Test #43:

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

input:

500 1000 500
999 999
999 999
999 999
999 999
999 999
999 999
999 999
999 999
999 999
999 999
999 999
999 999
999 999
999 999
999 999
999 999
999 999
999 999
999 999
999 999
999 999
999 999
999 999
999 999
999 999
999 999
999 999
999 999
999 999
999 999
999 999
999 999
999 999
999 999
999 999
999 999...

output:

098d134608c94f7413faac591054ee35
1

result:

ok Correct answer: answer = 1

Test #44:

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

input:

500 500 123
499 499
498 498
497 497
496 496
495 495
494 494
493 493
492 492
491 491
490 490
489 489
488 488
487 487
486 486
485 485
484 484
483 483
482 482
481 481
480 480
479 479
478 478
477 477
476 476
475 475
474 474
473 473
472 472
471 471
470 470
469 469
468 468
467 467
466 466
465 465
464 464
...

output:

098d134608c94f7413faac591054ee35
2040

result:

ok Correct answer: answer = 2040

Test #45:

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

input:

500 1000 500
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:

098d134608c94f7413faac591054ee35
2

result:

ok Correct answer: answer = 2

Subtask #3:

score: 9
Accepted

Dependency #1:

100%
Accepted

Dependency #2:

100%
Accepted

Test #46:

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

input:

5 7 2
0 3
4 4
4 6
4 5
4 6

output:

098d134608c94f7413faac591054ee35
25

result:

ok Correct answer: answer = 25

Test #47:

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

input:

2 2 1
0 1
1 0

output:

098d134608c94f7413faac591054ee35
4

result:

ok Correct answer: answer = 4

Test #48:

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

input:

2 3 1
0 0
2 0

output:

098d134608c94f7413faac591054ee35
9

result:

ok Correct answer: answer = 9

Test #49:

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

input:

4 3 2
0 0
0 2
0 0
0 1

output:

098d134608c94f7413faac591054ee35
9

result:

ok Correct answer: answer = 9

Test #50:

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

input:

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

output:

098d134608c94f7413faac591054ee35
21

result:

ok Correct answer: answer = 21

Test #51:

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

input:

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

output:

098d134608c94f7413faac591054ee35
71

result:

ok Correct answer: answer = 71

Test #52:

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

input:

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

output:

098d134608c94f7413faac591054ee35
77

result:

ok Correct answer: answer = 77

Test #53:

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

input:

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

output:

098d134608c94f7413faac591054ee35
400

result:

ok Correct answer: answer = 400

Test #54:

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

input:

500 1000 1
390 13
487 446
26 316
108 433
607 427
524 800
626 865
382 354
979 681
365 807
326 270
246 86
433 520
44 24
273 606
608 711
128 951
710 205
891 873
450 349
632 48
643 2
377 34
686 806
341 525
126 180
346 266
413 278
128 604
776 605
389 27
989 251
537 894
37 254
742 769
871 544
647 341
658 ...

output:

098d134608c94f7413faac591054ee35
996004

result:

ok Correct answer: answer = 996004

Test #55:

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

input:

500 1000 10
206 933
260 444
129 653
132 459
689 909
642 988
404 437
795 426
615 40
397 262
87 152
450 317
22 311
202 197
384 109
815 294
139 464
567 735
798 289
716 777
520 966
819 146
150 326
621 360
189 565
223 221
739 330
554 931
442 788
125 44
909 732
80 347
331 731
755 191
752 337
336 60
308 76...

output:

098d134608c94f7413faac591054ee35
997310

result:

ok Correct answer: answer = 997310

Test #56:

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

input:

500 1000 125
899 242
163 503
418 415
403 661
755 344
102 7
344 827
286 518
141 591
493 676
426 92
702 753
471 120
108 564
65 997
900 372
462 900
135 293
343 848
948 596
38 23
508 972
84 212
485 633
779 768
370 123
718 306
149 294
929 857
259 30
876 772
540 117
748 490
125 766
375 361
255 192
757 756...

output:

098d134608c94f7413faac591054ee35
990781

result:

ok Correct answer: answer = 990781

Test #57:

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

input:

500 1000 500
227 672
74 362
62 228
170 231
652 828
805 395
46 851
948 214
763 91
180 765
552 321
951 293
747 691
142 160
842 871
788 730
172 500
897 609
90 685
262 104
363 948
161 780
668 399
840 34
594 574
415 639
73 186
931 789
891 378
616 743
370 628
220 745
141 374
264 370
914 72
991 307
201 537...

output:

098d134608c94f7413faac591054ee35
996545

result:

ok Correct answer: answer = 996545

Test #58:

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

input:

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

output:

098d134608c94f7413faac591054ee35
484

result:

ok Correct answer: answer = 484

Test #59:

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

input:

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

output:

098d134608c94f7413faac591054ee35
484

result:

ok Correct answer: answer = 484

Test #60:

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

input:

500 501 4
236 237
200 201
154 155
128 129
344 345
453 454
112 113
10 11
491 492
356 357
299 300
294 295
197 198
441 442
13 14
78 79
287 288
430 431
342 343
63 64
284 285
100 101
315 316
14 15
33 34
292 293
2 3
392 393
383 384
46 47
295 296
401 402
487 488
327 328
127 128
408 409
109 110
71 72
248 24...

output:

098d134608c94f7413faac591054ee35
63501

result:

ok Correct answer: answer = 63501

Test #61:

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

input:

500 749 20
236 485
200 449
154 403
128 377
344 593
453 702
112 361
10 259
491 740
356 605
299 548
294 543
197 446
441 690
13 262
78 327
287 536
430 679
342 591
63 312
284 533
100 349
315 564
14 263
33 282
292 541
2 251
392 641
383 632
46 295
295 544
401 650
487 736
327 576
127 376
408 657
109 358
71...

output:

098d134608c94f7413faac591054ee35
323501

result:

ok Correct answer: answer = 323501

Test #62:

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

input:

500 1000 100
236 736
200 700
154 654
128 628
344 844
453 953
112 612
10 510
491 991
356 856
299 799
294 794
197 697
441 941
13 513
78 578
287 787
430 930
342 842
63 563
284 784
100 600
315 815
14 514
33 533
292 792
2 502
392 892
383 883
46 546
295 795
401 901
487 987
327 827
127 627
408 908
109 609
...

output:

098d134608c94f7413faac591054ee35
752500

result:

ok Correct answer: answer = 752500

Test #63:

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

input:

500 1000 30
258 763
223 734
175 673
140 645
353 863
468 959
123 630
12 521
501 996
368 871
310 821
306 814
221 728
450 949
15 525
82 593
297 805
440 939
351 861
70 584
296 801
113 613
325 838
17 525
37 549
304 813
5 513
402 910
390 899
49 566
306 815
408 917
497 994
332 850
139 645
415 922
121 627
7...

output:

098d134608c94f7413faac591054ee35
761480

result:

ok Correct answer: answer = 761480

Test #64:

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

input:

500 1000 200
216 713
172 681
131 641
104 607
311 830
426 953
93 587
10 483
459 985
324 846
276 779
271 773
170 676
411 944
13 485
71 550
263 766
399 931
308 829
59 531
260 763
84 577
289 803
14 485
29 510
270 771
1 473
358 888
347 874
47 519
272 775
369 898
453 979
298 814
103 605
374 905
89 583
63 ...

output:

098d134608c94f7413faac591054ee35
758932

result:

ok Correct answer: answer = 758932

Test #65:

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

input:

500 1000 1
0 999
1 998
2 997
3 996
4 995
5 994
6 993
7 992
8 991
9 990
10 989
11 988
12 987
13 986
14 985
15 984
16 983
17 982
18 981
19 980
20 979
21 978
22 977
23 976
24 975
25 974
26 973
27 972
28 971
29 970
30 969
31 968
32 967
33 966
34 965
35 964
36 963
37 962
38 961
39 960
40 959
41 958
42 95...

output:

098d134608c94f7413faac591054ee35
1000000

result:

ok Correct answer: answer = 1000000

Test #66:

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

input:

500 1000 500
499 999
498 998
497 997
496 996
495 995
494 994
493 993
492 992
491 991
490 990
489 989
488 988
487 987
486 986
485 985
484 984
483 983
482 982
481 981
480 980
479 979
478 978
477 977
476 976
475 975
474 974
473 973
472 972
471 971
470 970
469 969
468 968
467 967
466 966
465 965
464 964...

output:

098d134608c94f7413faac591054ee35
750500

result:

ok Correct answer: answer = 750500

Test #67:

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

input:

500 1000 500
0 999
0 999
0 999
0 999
0 999
0 999
0 999
0 999
0 999
0 999
0 999
0 999
0 999
0 999
0 999
0 999
0 999
0 999
0 999
0 999
0 999
0 999
0 999
0 999
0 999
0 999
0 999
0 999
0 999
0 999
0 999
0 999
0 999
0 999
0 999
0 999
0 999
0 999
0 999
0 999
0 999
0 999
0 999
0 999
0 999
0 999
0 999
0 999...

output:

098d134608c94f7413faac591054ee35
1000000

result:

ok Correct answer: answer = 1000000

Test #68:

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

input:

500 1000 1
0 0
0 1
0 2
0 3
0 4
0 5
0 6
0 7
0 8
0 9
0 10
0 11
0 12
0 13
0 14
0 15
0 16
0 17
0 18
0 19
0 20
0 21
0 22
0 23
0 24
0 25
0 26
0 27
0 28
0 29
0 30
0 31
0 32
0 33
0 34
0 35
0 36
0 37
0 38
0 39
0 40
0 41
0 42
0 43
0 44
0 45
0 46
0 47
0 48
0 49
0 50
0 51
0 52
0 53
0 54
0 55
0 56
0 57
0 58
0 59...

output:

098d134608c94f7413faac591054ee35
250000

result:

ok Correct answer: answer = 250000

Test #69:

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

input:

500 1000 1
0 499
0 498
0 497
0 496
0 495
0 494
0 493
0 492
0 491
0 490
0 489
0 488
0 487
0 486
0 485
0 484
0 483
0 482
0 481
0 480
0 479
0 478
0 477
0 476
0 475
0 474
0 473
0 472
0 471
0 470
0 469
0 468
0 467
0 466
0 465
0 464
0 463
0 462
0 461
0 460
0 459
0 458
0 457
0 456
0 455
0 454
0 453
0 452
0...

output:

098d134608c94f7413faac591054ee35
250000

result:

ok Correct answer: answer = 250000

Test #70:

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

input:

500 1000 500
0 999
1 999
1 997
1 997
3 997
3 996
3 995
8 993
9 993
9 991
9 990
14 989
15 988
17 986
17 985
19 982
20 981
20 981
20 980
21 979
23 977
25 977
25 974
27 973
28 972
29 971
30 971
30 967
32 967
33 967
33 965
35 963
35 962
36 962
37 961
37 960
37 958
38 957
39 957
39 957
39 957
42 956
43 9...

output:

098d134608c94f7413faac591054ee35
1000000

result:

ok Correct answer: answer = 1000000

Test #71:

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

input:

500 1000 1
2 998
3 998
3 998
4 997
7 997
9 997
10 996
11 995
17 995
17 994
18 993
18 992
19 984
20 982
22 981
23 980
24 979
24 977
27 975
28 972
28 970
30 969
32 968
34 968
35 967
36 967
37 967
37 967
38 966
41 966
41 964
41 964
42 963
42 963
43 963
44 963
44 962
45 962
46 962
46 961
46 960
47 960
4...

output:

098d134608c94f7413faac591054ee35
994009

result:

ok Correct answer: answer = 994009

Test #72:

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

input:

500 1000 20
740 752
551 563
225 237
83 91
379 398
796 815
285 293
385 399
464 478
718 724
901 917
363 364
39 41
704 722
935 942
177 193
811 828
87 103
901 915
27 35
544 552
555 572
472 485
22 37
579 591
559 566
642 655
835 843
239 251
580 589
742 743
436 442
743 746
807 810
362 371
913 915
197 212
5...

output:

098d134608c94f7413faac591054ee35
59315

result:

ok Correct answer: answer = 59315

Test #73:

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

input:

500 1000 100
359 374
89 96
635 648
65 79
540 541
92 109
896 914
79 81
452 466
92 100
888 891
597 598
597 608
963 967
678 687
812 826
835 841
62 72
757 775
99 111
108 119
976 989
642 652
6 23
420 420
599 601
296 315
142 146
363 369
821 824
674 686
190 207
815 815
856 856
474 477
971 982
768 778
410 4...

output:

098d134608c94f7413faac591054ee35
25454

result:

ok Correct answer: answer = 25454

Test #74:

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

input:

300 442 150
344 345
294 295
231 232
191 192
219 220
265 266
168 169
13 14
276 277
221 222
440 441
434 435
289 290
164 165
18 19
120 121
424 425
152 153
176 177
95 96
420 421
153 154
391 392
20 21
49 50
431 432
2 3
92 93
252 253
71 72
435 436
97 98
151 152
64 65
189 190
287 288
165 166
109 110
365 36...

output:

098d134608c94f7413faac591054ee35
1504

result:

ok Correct answer: answer = 1504

Test #75:

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

input:

100 960 25
366 375
726 735
630 639
230 239
764 773
239 248
468 477
96 105
688 697
903 912
814 823
145 154
854 863
307 316
125 134
744 753
105 114
950 959
639 648
601 610
564 573
248 257
385 394
135 144
317 326
221 230
20 29
574 583
784 793
440 449
535 544
610 619
941 950
404 413
375 384
192 201
893 ...

output:

098d134608c94f7413faac591054ee35
37486

result:

ok Correct answer: answer = 37486

Test #76:

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

input:

250 919 108
841 842
630 630
479 481
435 435
465 466
526 526
397 399
62 63
541 542
467 467
445 445
452 453
612 614
389 390
81 81
331 331
395 396
375 377
413 415
300 301
292 292
378 378
240 240
86 86
196 198
438 439
12 14
293 294
507 508
262 264
913 913
302 304
372 374
250 250
433 434
601 601
391 392
...

output:

098d134608c94f7413faac591054ee35
4284

result:

ok Correct answer: answer = 4284

Test #77:

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

input:

500 1000 408
77 173
102 116
593 615
36 71
3 121
348 389
17 40
514 592
790 847
102 107
820 844
573 677
344 454
358 374
340 399
597 642
761 802
525 638
606 694
861 970
11 52
113 234
856 951
590 649
321 335
73 177
525 635
75 166
799 855
562 668
823 927
357 367
835 855
771 831
754 790
58 139
275 284
806...

output:

098d134608c94f7413faac591054ee35
158008

result:

ok Correct answer: answer = 158008

Test #78:

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

input:

500 1000 171
635 671
29 62
423 459
830 846
414 442
311 337
219 237
10 29
119 124
621 670
919 942
419 442
705 738
125 147
310 329
807 829
737 783
16 24
214 242
319 336
437 483
0 16
528 543
410 429
302 320
219 242
207 220
203 236
333 347
624 670
519 542
132 166
714 760
714 733
730 746
832 866
900 916
...

output:

098d134608c94f7413faac591054ee35
51860

result:

ok Correct answer: answer = 51860

Test #79:

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

input:

500 1000 45
445 456
5 24
163 171
125 139
768 778
127 129
489 490
409 411
643 650
247 249
967 973
767 773
885 890
647 656
529 531
128 131
487 493
207 216
688 698
525 531
367 373
9 10
600 602
569 571
325 344
687 693
89 91
685 702
325 342
845 864
807 813
46 53
483 490
88 98
85 99
326 333
369 370
845 85...

output:

098d134608c94f7413faac591054ee35
12985

result:

ok Correct answer: answer = 12985

Subtask #4:

score: 16
Accepted

Dependency #1:

100%
Accepted

Dependency #2:

100%
Accepted

Dependency #3:

100%
Accepted

Test #80:

score: 16
Accepted
time: 8ms
memory: 18928kb

input:

4000 1000000 4
316093 839144
203315 754340
298007 372460
239790 788674
758142 993425
607471 123146
372906 65812
81611 948183
469763 922840
634978 45330
868100 412154
267626 64413
465088 168956
449599 896116
354703 330084
226258 508388
288605 246914
989182 625499
606445 215339
60973 44283
183751 9745...

output:

098d134608c94f7413faac591054ee35
997864126212

result:

ok Correct answer: answer = 997864126212

Test #81:

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

input:

4000 1000000 200
802147 894998
702374 643031
467273 752470
246234 7324
89336 833376
424603 149115
435301 228543
849848 655849
771894 51822
953856 489529
458583 430207
201722 428671
192671 511172
709147 646579
975016 838574
696322 51338
512441 993663
369225 135994
280486 211317
601929 668956
428691 9...

output:

098d134608c94f7413faac591054ee35
998608411647

result:

ok Correct answer: answer = 998608411647

Test #82:

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

input:

4000 1000000 3000
101329 69650
774506 60118
145671 192233
835186 103209
433700 475095
235611 399226
189592 909263
199311 190439
15612 238119
66270 25917
379536 96059
867820 851546
719357 753799
470596 48512
981779 117465
211448 54006
853302 464225
271399 757216
959020 520778
222746 347755
739462 851...

output:

098d134608c94f7413faac591054ee35
995265560477

result:

ok Correct answer: answer = 995265560477

Test #83:

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

input:

4000 4500 2
2907 2907
649 649
3387 3387
128 128
4267 4267
1550 1550
4143 4143
4374 4374
4160 4160
1111 1111
3135 3135
2527 2527
1951 1951
441 441
4308 4308
78 78
3473 3473
1820 1820
342 342
4004 4004
3056 3056
2246 2246
1148 1148
3072 3072
2785 2785
4057 4057
2848 2848
3341 3341
383 383
1607 1607
13...

output:

098d134608c94f7413faac591054ee35
10125000

result:

ok Correct answer: answer = 10125000

Test #84:

score: 0
Accepted
time: 493ms
memory: 4000kb

input:

4000 4500 7
2907 2907
649 649
3387 3387
128 128
4267 4267
1550 1550
4143 4143
4374 4374
4160 4160
1111 1111
3135 3135
2527 2527
1951 1951
441 441
4308 4308
78 78
3473 3473
1820 1820
342 342
4004 4004
3056 3056
2246 2246
1148 1148
3072 3072
2785 2785
4057 4057
2848 2848
3341 3341
383 383
1607 1607
13...

output:

098d134608c94f7413faac591054ee35
2291668

result:

ok Correct answer: answer = 2291668

Test #85:

score: 0
Accepted
time: 117ms
memory: 3884kb

input:

2048 2048 99
1297 1297
649 649
966 966
128 128
344 344
1550 1550
1503 1503
1540 1540
962 962
1111 1111
1964 1964
784 784
1951 1951
441 441
13 13
78 78
1113 1113
1820 1820
342 342
1622 1622
547 547
1346 1346
1148 1148
1956 1956
33 33
1382 1382
1633 1633
848 848
383 383
1607 1607
1396 1396
2004 2004
1...

output:

098d134608c94f7413faac591054ee35
42388

result:

ok Correct answer: answer = 42388

Test #86:

score: 0
Accepted
time: 117ms
memory: 3888kb

input:

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

output:

098d134608c94f7413faac591054ee35
10318

result:

ok Correct answer: answer = 10318

Test #87:

score: 0
Accepted
time: 118ms
memory: 4176kb

input:

2048 2048 1364
1297 1297
649 649
966 966
128 128
344 344
1550 1550
1503 1503
1540 1540
962 962
1111 1111
1964 1964
784 784
1951 1951
441 441
13 13
78 78
1113 1113
1820 1820
342 342
1622 1622
547 547
1346 1346
1148 1148
1956 1956
33 33
1382 1382
1633 1633
848 848
383 383
1607 1607
1396 1396
2004 2004...

output:

098d134608c94f7413faac591054ee35
3416

result:

ok Correct answer: answer = 3416

Test #88:

score: 0
Accepted
time: 851ms
memory: 19116kb

input:

4000 1000000 3
738969 738969
430179 430179
95815 95815
285036 285036
904007 904007
492672 492672
206382 206382
24851 24851
49894 49894
541658 541658
18223 18223
248661 248661
556323 556323
37896 37896
598103 598103
10724 10724
455130 455130
588397 588397
760511 760511
891932 891932
582449 582449
751...

output:

098d134608c94f7413faac591054ee35
331708193881

result:

ok Correct answer: answer = 331708193881

Test #89:

score: 0
Accepted
time: 962ms
memory: 19312kb

input:

4000 1000000 233
582059 582059
733162 733162
514791 514791
634616 634616
399364 399364
727903 727903
516759 516759
31994 31994
389207 389207
610813 610813
430229 430229
936059 936059
233301 233301
282787 282787
274817 274817
225858 225858
951238 951238
705438 705438
579986 579986
5311 5311
504394 50...

output:

098d134608c94f7413faac591054ee35
2861193756

result:

ok Correct answer: answer = 2861193756

Test #90:

score: 0
Accepted
time: 966ms
memory: 19052kb

input:

4000 1000000 1333
280165 280165
507866 507866
118395 118395
34055 34055
337178 337178
51482 51482
599033 599033
745453 745453
645698 645698
758762 758762
990762 990762
787254 787254
542783 542783
9919 9919
446078 446078
409640 409640
554787 554787
6320 6320
213456 213456
688362 688362
609839 609839
...

output:

098d134608c94f7413faac591054ee35
114646930

result:

ok Correct answer: answer = 114646930

Test #91:

score: 0
Accepted
time: 513ms
memory: 4288kb

input:

4000 4999 55
2907 3906
649 1648
3387 4386
128 1127
3767 4766
1550 2549
3643 4642
3874 4873
3660 4659
1111 2110
3135 4134
2527 3526
1951 2950
441 1440
3808 4807
78 1077
3473 4472
1820 2819
342 1341
3504 4503
3056 4055
2246 3245
1148 2147
3072 4071
2785 3784
3557 4556
2848 3847
3341 4340
383 1382
1607...

output:

098d134608c94f7413faac591054ee35
9280921

result:

ok Correct answer: answer = 9280921

Test #92:

score: 0
Accepted
time: 803ms
memory: 19048kb

input:

4000 1000000 300
2907 998907
649 996649
3387 999387
128 996128
3767 999767
1550 997550
3643 999643
3874 999874
3660 999660
1111 997111
3135 999135
2527 998527
1951 997951
441 996441
3808 999808
78 996078
3473 999473
1820 997820
342 996342
3504 999504
3056 999056
2246 998246
1148 997148
3072 999072
2...

output:

098d134608c94f7413faac591054ee35
999984053400

result:

ok Correct answer: answer = 999984053400

Test #93:

score: 0
Accepted
time: 950ms
memory: 19124kb

input:

4000 1000000 1000
361605 868226
79234 581021
420642 925330
15317 515171
467517 971657
195656 691941
449776 957515
481288 985424
451797 959532
138776 634647
389236 896376
313825 820076
246680 743979
53353 553166
471917 976746
9661 510283
430332 935308
230004 726811
41847 542235
433821 939076
380806 8...

output:

098d134608c94f7413faac591054ee35
750935949134

result:

ok Correct answer: answer = 750935949134

Test #94:

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

input:

4000 1000000 2
0 999999
1 999998
2 999997
3 999996
4 999995
5 999994
6 999993
7 999992
8 999991
9 999990
10 999989
11 999988
12 999987
13 999986
14 999985
15 999984
16 999983
17 999982
18 999981
19 999980
20 999979
21 999978
22 999977
23 999976
24 999975
25 999974
26 999973
27 999972
28 999971
29 99...

output:

098d134608c94f7413faac591054ee35
1000000000000

result:

ok Correct answer: answer = 1000000000000

Test #95:

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

input:

4000 1000000 4000
364103 638598
76592 919327
422248 582683
14878 982268
472727 532666
192187 810010
455727 549282
487125 520323
458489 547230
131796 863749
390382 612373
314482 684591
242669 760810
53415 943649
477572 527481
8726 989093
433552 571446
225045 776218
42066 955907
438290 566857
380927 6...

output:

098d134608c94f7413faac591054ee35
998762383161

result:

ok Correct answer: answer = 998762383161

Test #96:

score: 0
Accepted
time: 917ms
memory: 19120kb

input:

4000 1000000 40
99061 99068
91682 91706
203834 203857
79257 79268
255765 255770
37900 37910
593717 593731
257795 257799
465836 465858
91834 91851
672662 672662
310685 310699
938756 938764
683584 683592
563176 563197
176365 176381
574717 574738
837026 837044
164033 164053
293377 293382
42761 42788
79...

output:

098d134608c94f7413faac591054ee35
23017412908

result:

ok Correct answer: answer = 23017412908

Test #97:

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

input:

4000 1000000 1000
10261 436434
415588 914546
486845 932316
263525 581636
326343 714449
491557 964937
168494 354046
284536 374324
287496 332741
269739 676914
299970 388535
14508 225140
276362 650050
390473 809104
154792 369793
115019 378501
151336 288482
284800 317316
407122 882120
144520 537557
3561...

output:

098d134608c94f7413faac591054ee35
728143410622

result:

ok Correct answer: answer = 728143410622

Test #98:

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

input:

4000 1000000 2
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:

098d134608c94f7413faac591054ee35
2

result:

ok Correct answer: answer = 2

Test #99:

score: 0
Accepted
time: 794ms
memory: 19124kb

input:

4000 1000000 10
2907 2913
649 655
3387 3393
128 134
3767 3773
1550 1556
3643 3649
3874 3880
3660 3666
1111 1117
3135 3141
2527 2533
1951 1957
441 447
3808 3814
78 84
3473 3479
1820 1826
342 348
3504 3510
3056 3062
2246 2252
1148 1154
3072 3078
2785 2791
3557 3563
2848 2854
3341 3347
383 389
1607 161...

output:

098d134608c94f7413faac591054ee35
1824916

result:

ok Correct answer: answer = 1824916

Test #100:

score: 0
Accepted
time: 757ms
memory: 5032kb

input:

4000 100000 512
73 73
146 146
219 219
292 292
365 365
438 438
511 511
584 584
657 657
730 730
803 803
876 876
949 949
1022 1022
1095 1095
1168 1168
1241 1241
1314 1314
1387 1387
1460 1460
1533 1533
1606 1606
1679 1679
1752 1752
1825 1825
1898 1898
1971 1971
2044 2044
2117 2117
2190 2190
2263 2263
23...

output:

098d134608c94f7413faac591054ee35
10680029

result:

ok Correct answer: answer = 10680029

Test #101:

score: 0
Accepted
time: 728ms
memory: 4960kb

input:

4000 100000 256
93 93
186 186
279 279
372 372
465 465
558 558
651 651
744 744
837 837
930 930
1023 1023
1116 1116
1209 1209
1302 1302
1395 1395
1488 1488
1581 1581
1674 1674
1767 1767
1860 1860
1953 1953
2046 2046
2139 2139
2232 2232
2325 2325
2418 2418
2511 2511
2604 2604
2697 2697
2790 2790
2883 2...

output:

098d134608c94f7413faac591054ee35
18351700

result:

ok Correct answer: answer = 18351700

Test #102:

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

input:

4000 1000000 2
2907 2913
649 655
3387 3393
128 134
3767 3773
1550 1556
3643 3649
3874 3880
3660 3666
1111 1117
3135 3141
2527 2533
1951 1957
441 447
3808 3814
78 84
3473 3479
1820 1826
342 348
3504 3510
3056 3062
2246 2252
1148 1154
3072 3078
2785 2791
3557 3563
2848 2854
3341 3347
383 389
1607 1613...

output:

098d134608c94f7413faac591054ee35
16040026

result:

ok Correct answer: answer = 16040026

Test #103:

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

input:

4000 1000000 2
502907 2989
500649 706
503387 3392
500128 226
503767 3797
501550 1573
503643 3656
503874 3946
503660 3730
501111 1139
503135 3221
502527 2607
501951 2043
500441 536
503808 3812
500078 139
503473 3526
501820 1897
500342 412
503504 3528
503056 3110
502246 2299
501148 1159
503072 3137
50...

output:

098d134608c94f7413faac591054ee35
253968628325

result:

ok Correct answer: answer = 253968628325

Test #104:

score: 0
Accepted
time: 118ms
memory: 3896kb

input:

2000 3001 1000
1944 1945
988 989
1445 1446
188 189
520 521
2321 2322
2248 2249
2306 2307
1439 1440
1657 1658
2944 2945
1181 1182
2924 2925
667 668
20 21
116 117
1660 1661
2716 2717
517 518
2427 2428
832 833
2015 2016
1710 1711
2934 2935
51 52
2074 2075
2446 2447
1272 1273
576 577
2406 2407
2096 2097...

output:

098d134608c94f7413faac591054ee35
10267

result:

ok Correct answer: answer = 10267

Test #105:

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

input:

4000 507139 1757
194530 194532
68355 68356
331808 331810
36608 36610
440501 440501
70224 70224
405028 405029
471105 471105
409895 409897
69292 69292
259731 259733
85853 85853
71030 71031
67918 67918
452229 452230
22303 22304
356417 356417
70759 70759
67713 67715
365280 365282
237144 237144
71643 716...

output:

098d134608c94f7413faac591054ee35
2582408

result:

ok Correct answer: answer = 2582408

Test #106:

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

input:

4000 1000000 2
958999 997882
895585 930876
889398 918794
625570 676836
950769 902747
616638 647327
946759 885874
768251 754315
754360 625475
883460 867471
918187 992263
956427 980959
996132 923279
909242 957586
652623 769314
783536 739244
995832 893331
607266 743670
804983 703468
758135 655807
76323...

output:

098d134608c94f7413faac591054ee35
78024964781

result:

ok Correct answer: answer = 78024964781

Test #107:

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

input:

4000 1000000 10
901856 910432
972345 972742
889984 898528
965933 968715
901600 917082
261180 261232
327707 337667
359712 394399
261080 261264
261489 261354
428742 438459
905473 905808
261477 261456
261364 261534
965671 952439
959414 967863
322404 320814
261204 261234
298048 302905
393783 401297
8574...

output:

098d134608c94f7413faac591054ee35
9866346457

result:

ok Correct answer: answer = 9866346457

Test #108:

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

input:

4000 1000000 100
57863 57946
530433 532761
870678 869838
300477 306991
675568 674708
543267 541311
454657 447858
729187 729689
612284 602718
86736 86934
396810 396739
292442 291892
544664 545898
426030 426631
63842 63825
760665 761331
720529 720363
223254 221659
428929 433481
46349 48934
574574 5745...

output:

098d134608c94f7413faac591054ee35
3327720949

result:

ok Correct answer: answer = 3327720949

Test #109:

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

input:

4000 1000000 1822
396762 457310
170153 190277
388554 414992
7779 59170
914207 932481
795872 842367
413548 463092
294555 318983
505803 528981
934712 938583
905737 937147
898082 957394
915261 973612
179647 216230
42467 81940
773732 796188
180328 239174
515815 517656
789995 797759
23857 35158
15109 446...

output:

098d134608c94f7413faac591054ee35
86064128360

result:

ok Correct answer: answer = 86064128360

Test #110:

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

input:

4000 1000000 2920
145237 155084
981743 984022
749316 758479
563952 570669
344545 348642
1129 6314
860481 862577
489971 498826
207792 214636
228190 237217
704971 711301
541909 542844
20332 26740
822405 825845
161964 166798
568301 577699
467571 471028
406860 412364
847152 852933
86382 95646
123518 125...

output:

098d134608c94f7413faac591054ee35
12698259150

result:

ok Correct answer: answer = 12698259150

Test #111:

score: 0
Accepted
time: 555ms
memory: 18820kb

input:

4000 1000000 2484
268065 269245
623436 624494
467675 468262
320013 320175
417948 418716
876089 876191
107948 108716
685448 686216
150448 151216
778563 779622
838065 839245
317981 319089
878445 879694
103436 104494
520448 521216
195013 195175
682675 683262
550945 552194
855013 855175
760175 760762
64...

output:

098d134608c94f7413faac591054ee35
1185259288

result:

ok Correct answer: answer = 1185259288

Subtask #5:

score: 0
Time Limit Exceeded

Dependency #1:

100%
Accepted

Test #112:

score: 19
Accepted
time: 4ms
memory: 19776kb

input:

50000 1000000 3
360946 187012
56354 290116
389944 194589
327798 454716
248464 891509
615396 878303
736802 689759
446833 816714
552228 948958
34870 257015
911026 191884
761150 821028
341778 82756
125288 719663
86132 290045
145161 627383
25381 217026
756213 671192
686079 478553
648300 785174
706912 93...

output:

098d134608c94f7413faac591054ee35
999889968863

result:

ok Correct answer: answer = 999889968863

Test #113:

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

input:

50000 1000000 8
399073 559474
284146 99898
375389 122686
80775 357801
319456 379430
251948 425589
470164 726942
180115 677331
174879 609886
879336 274639
172132 755286
73776 907221
655053 808794
127586 558652
158465 298754
474407 208895
819275 192292
754904 362313
942856 453040
205348 662961
554428 ...

output:

098d134608c94f7413faac591054ee35
999861384931

result:

ok Correct answer: answer = 999861384931

Test #114:

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

input:

50000 1000000 49
395775 225827
107876 226736
693613 305582
901641 53447
504609 994262
5047 608677
484540 120957
36722 397124
825085 736548
553505 750564
978962 460112
450110 15095
336393 250376
517875 417904
995371 271663
905045 858978
240324 844363
468528 106252
331737 99932
78429 675647
897302 755...

output:

098d134608c94f7413faac591054ee35
999811809929

result:

ok Correct answer: answer = 999811809929

Test #115:

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

input:

50000 1000000 99
595092 535757
193430 467573
548323 750849
89122 500291
562841 861078
924882 20121
116634 939464
735914 577485
455078 104026
434181 806496
208311 437995
721445 878386
306688 927173
567734 38513
58134 237797
539935 425782
797486 99058
692233 731520
455780 628428
543934 291599
230276 6...

output:

098d134608c94f7413faac591054ee35
999869756441

result:

ok Correct answer: answer = 999869756441

Test #116:

score: -19
Time Limit Exceeded

input:

50000 60000 2
8597 8597
9329 9329
9757 9757
52906 52906
3767 3767
1550 1550
27747 27747
32959 32959
51190 51190
11613 11613
5014 5014
2527 2527
14847 14847
23167 23167
35500 35500
53108 53108
37110 37110
56602 56602
39663 39663
4674 4674
37075 37075
7077 7077
24718 24718
17596 17596
8332 8332
15727 ...

output:

Unauthorized output

result:

Subtask #6:

score: 0
Skipped

Dependency #1:

100%
Accepted

Dependency #2:

100%
Accepted

Dependency #3:

100%
Accepted

Dependency #4:

100%
Accepted

Dependency #5:

0%
English 繁體中文 简体中文

Server Time: 2024-11-30 02:46:48 | OpenSource Project