QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#500110#8708. PortalQwerty1232#100 ✓67ms4752kbC++232.5kb2024-07-31 22:31:562024-07-31 22:31:58

Judging History

This is the latest submission verdict.

  • [2024-07-31 22:31:58]
  • Judged
  • Verdict: 100
  • Time: 67ms
  • Memory: 4752kb
  • [2024-07-31 22:31:56]
  • Submitted

answer

#include <bits/stdc++.h>

struct Vector {
    int64_t x, y;

    Vector() : x(0), y(0) { ; }
    Vector(int64_t x, int64_t y) : x(x), y(y) { ; }

    Vector operator-(const Vector& other) const {
        return Vector(x - other.x, y - other.y);
    }
    Vector operator+(const Vector& other) const {
        return Vector(x + other.x, y + other.y);
    }
    Vector operator*(const int64_t& f) const {
        return Vector(x * f, y * f);
    }
    int64_t operator%(const Vector& other) const {
        return int64_t(x) * other.y - int64_t(y) * other.x;
    }
    int64_t operator*(const Vector& other) const {
        return int64_t(x) * other.x + int64_t(y) * other.y;
    }
    int64_t sq_len() const {
        return *this * *this;
    }
};

std::array<Vector, 2> fuck(std::array<Vector, 3> ar) {
    while (ar[0].sq_len() && ar[1].sq_len() && ar[2].sq_len()) {
        for (int f = (1 << 20); f >= 1; f >>= 1) {
            for (int i = 0; i < ar.size(); i++) {
                Vector dt = ar[i] * f;
                if (llabs(dt.x) > int(2e6) || llabs(dt.y) > int(2e6)) {
                    continue;
                }
                for (int j = 0; j < ar.size(); j++) {
                    if (i == j) {
                        continue;
                    }
                    if ((ar[j] + dt).sq_len() < ar[j].sq_len()) {
                        ar[j] = ar[j] + dt;
                    } else if ((ar[j] - dt).sq_len() < ar[j].sq_len()) {
                        ar[j] = ar[j] - dt;
                    }
                }
            }
        }
    }
    std::sort(ar.begin(), ar.end(), [&](const auto& a, const auto& b) { return a.sq_len() > b.sq_len(); });
    return {ar[0], ar[1]};
}

int32_t main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int n;
    std::cin >> n;
    std::vector<Vector> input(n);
    for (auto& [x, y] : input) {
        std::cin >> x >> y;
    }
    for (int i = 1; i < n; i++) {
        input[i] = input[i] - input[0];
    }
    input.erase(input.begin());
    n = input.size();
    if (n <= 1) {
        std::cout << "-1\n";
        return 0;
    }

    std::array<Vector, 2> ar{{{0, 0}, {0, 0}}};
    for (auto p : input) {
        std::array<Vector, 3> ar2 = {ar[0], ar[1], p};
        ar = fuck(ar2);
    }
    if (ar[0] % ar[1]) {
        std::cout << llabs(ar[0] % ar[1]) << std::endl;
    } else {
        std::cout << "-1\n";
    }

    return 0;
}

详细

Subtask #1:

score: 1
Accepted

Test #1:

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

input:

1
1 -1

output:

-1

result:

ok single line: '-1'

Test #2:

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

input:

2
-455833 -283524
427847 159281

output:

-1

result:

ok single line: '-1'

Test #3:

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

input:

2
52420 -46322
-192914 87067

output:

-1

result:

ok single line: '-1'

Test #4:

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

input:

2
52446 -20773
179773 174566

output:

-1

result:

ok single line: '-1'

Test #5:

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

input:

2
-229012 -260770
-174790 -69382

output:

-1

result:

ok single line: '-1'

Test #6:

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

input:

2
-127294 418312
211124 37002

output:

-1

result:

ok single line: '-1'

Test #7:

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

input:

2
-129173 516840
46821 -187136

output:

-1

result:

ok single line: '-1'

Test #8:

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

input:

2
-90088 -7423
234488 19625

output:

-1

result:

ok single line: '-1'

Test #9:

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

input:

2
-48105 256695
15135 -80585

output:

-1

result:

ok single line: '-1'

Test #10:

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

input:

2
-251318 79061
182792 -129183

output:

-1

result:

ok single line: '-1'

Test #11:

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

input:

2
784850 417677
-217245 -460999

output:

-1

result:

ok single line: '-1'

Test #12:

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

input:

2
31270 410692
713271 917276

output:

-1

result:

ok single line: '-1'

Test #13:

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

input:

1
230862 -785444

output:

-1

result:

ok single line: '-1'

Test #14:

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

input:

2
222814 -279784
-73657 59849

output:

-1

result:

ok single line: '-1'

Test #15:

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

input:

2
72171 -104186
201480 105502

output:

-1

result:

ok single line: '-1'

Test #16:

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

input:

2
-17727 -27151
69235 15029

output:

-1

result:

ok single line: '-1'

Test #17:

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

input:

2
-44049 96618
173806 -21489

output:

-1

result:

ok single line: '-1'

Test #18:

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

input:

2
-81268 -53452
329866 -163275

output:

-1

result:

ok single line: '-1'

Subtask #2:

score: 10
Accepted

Dependency #1:

100%
Accepted

Test #19:

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

input:

3
1 1
1 3
3 2

output:

4

result:

ok single line: '4'

Test #20:

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

input:

3
123741 -122828
207774 110184
-33847 97305

output:

55218331445

result:

ok single line: '55218331445'

Test #21:

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

input:

3
-66381 27989
200580 40286
300930 -238824

output:

75745488660

result:

ok single line: '75745488660'

Test #22:

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

input:

3
-212612 305891
-228367 216399
56731 149417

output:

26569291626

result:

ok single line: '26569291626'

Test #23:

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

input:

3
58252 388020
34720 -409605
79321 85296

output:

23928862293

result:

ok single line: '23928862293'

Test #24:

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

input:

3
19556 -29968
-52219 72940
153159 -166846

output:

3924399074

result:

ok single line: '3924399074'

Test #25:

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

input:

3
201002 729262
-242878 -881858
183722 666542

output:

-1

result:

ok single line: '-1'

Test #26:

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

input:

3
-425251 245407
695099 -401393
18815 -10961

output:

-1

result:

ok single line: '-1'

Test #27:

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

input:

3
-74800 392658
-48320 253638
-13280 69678

output:

-1

result:

ok single line: '-1'

Test #28:

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

input:

3
376570 -515419
-67488 -129024
-72636 -138852

output:

6353363484

result:

ok single line: '6353363484'

Test #29:

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

input:

3
-365409 -46168
130463 -388367
-745599 -94238

output:

153937204850

result:

ok single line: '153937204850'

Test #30:

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

input:

3
4925 198059
583262 -155627
573812 -153107

output:

1884923460

result:

ok single line: '1884923460'

Test #31:

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

input:

1
-785465 814199

output:

-1

result:

ok single line: '-1'

Test #32:

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

input:

3
107518 -84340
137659 -15241
359437 347683

output:

4385745738

result:

ok single line: '4385745738'

Test #33:

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

input:

3
-203959 7059
-34097 -218222
96949 -293501

output:

16735132428

result:

ok single line: '16735132428'

Test #34:

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

input:

3
18005 283441
106422 -61165
137635 -175433

output:

652953322

result:

ok single line: '652953322'

Test #35:

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

input:

3
-233201 -63834
105532 -12105
337350 41702

output:

6234493209

result:

ok single line: '6234493209'

Test #36:

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

input:

3
36748 -26399
119775 -223323
224245 -89339

output:

31696939848

result:

ok single line: '31696939848'

Test #37:

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

input:

3
1000000 -110976
-1000000 -1000000
715820 1000000

output:

2474594840320

result:

ok single line: '2474594840320'

Test #38:

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

input:

3
48920 1000000
1000000 -680401
-1000000 -1000000

output:

3664766216920

result:

ok single line: '3664766216920'

Test #39:

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

input:

3
196198 1000000
1000000 -520790
-1000000 -1000000

output:

3426769956420

result:

ok single line: '3426769956420'

Subtask #3:

score: 10
Accepted

Test #40:

score: 10
Accepted
time: 48ms
memory: 4752kb

input:

99840
-359536 735499
-710626 400619
-468266 -282389
-192706 43659
204034 -543669
-100576 -749013
-118006 -283125
-341276 405771
560934 835595
-923936 506603
239724 956299
-680746 -737237
286204 982795
-847576 -282389
-949666 986475
996684 -429589
672984 -133717
140954 696491
-879116 -442837
985064 7...

output:

610880

result:

ok single line: '610880'

Test #41:

score: 10
Accepted
time: 50ms
memory: 4728kb

input:

99680
231534 501002
-604126 79487
-337934 -601948
-869810 434312
-819518 524087
598310 79487
161938 -480538
463182 827612
233566 807092
-51422 666872
155334 -561763
-819518 -419833
290970 947312
-679818 -16273
804558 435167
-387210 223982
161938 223982
35954 373607
-854570 -459163
831482 771182
5251...

output:

434340

result:

ok single line: '434340'

Test #42:

score: 10
Accepted
time: 48ms
memory: 4688kb

input:

99940
-366859 734803
-722883 -352755
266497 350263
892977 -547983
229061 -550941
-253023 -216687
187041 219125
907493 920171
445273 133343
965557 991163
102237 -66815
434577 732831
239757 -263029
-746567 -527277
-350051 879745
-943679 -528263
-928399 -528263
-867279 66295
-696907 -722505
-247675 465...

output:

753304

result:

ok single line: '753304'

Test #43:

score: 10
Accepted
time: 44ms
memory: 4688kb

input:

99940
629940 252040
422661 -727640
847455 297570
-129230 -330430
-539523 962465
267415 639045
-230737 382350
626528 -730
-940433 -799860
-667473 962465
-941286 675155
-880723 467915
727182 -864230
-936168 -94145
608615 697135
-668326 -963925
-947257 201800
-84021 -386950
-882429 735600
-606057 83922...

output:

669605

result:

ok single line: '669605'

Test #44:

score: 10
Accepted
time: 49ms
memory: 4676kb

input:

99831
758237 -429818
616877 504517
482027 -525398
-877633 -183173
773117 659227
89567 -748958
-14593 -305483
-586543 960547
41207 979582
-300103 -4568
493187 778297
-778123 229522
-338233 -273488
96077 -235823
462497 218992
752657 -429818
41207 188617
419717 389902
-245233 478597
878207 229522
-6655...

output:

376650

result:

ok single line: '376650'

Test #45:

score: 10
Accepted
time: 34ms
memory: 4620kb

input:

100000
-185103 330730
640566 330730
-197028 330730
-296469 330730
950535 330730
-436833 330730
-331893 330730
-130545 330730
236349 330730
-462267 330730
-796788 330730
782343 330730
977130 330730
210285 330730
-99909 330730
979830 330730
206793 330730
346842 330730
591111 330730
444690 330730
96783...

output:

-1

result:

ok single line: '-1'

Test #46:

score: 10
Accepted
time: 31ms
memory: 4672kb

input:

100000
897386 -498167
294216 -498167
-416934 -498167
407176 -498167
423246 -498167
-806934 -498167
-106964 -498167
185376 -498167
-17724 -498167
83516 -498167
481156 -498167
795446 -498167
134076 -498167
-338814 -498167
279526 -498167
970276 -498167
844856 -498167
-37134 -498167
-430634 -498167
-954...

output:

-1

result:

ok single line: '-1'

Test #47:

score: 10
Accepted
time: 35ms
memory: 4564kb

input:

100000
302722 467192
-710129 467192
735336 467192
-255381 467192
-822213 467192
-158389 467192
-193270 467192
358540 467192
-219100 467192
558733 467192
-507675 467192
-695590 467192
-409213 467192
-714518 467192
336567 467192
-533925 467192
-773689 467192
-968688 467192
62384 467192
876526 467192
6...

output:

-1

result:

ok single line: '-1'

Test #48:

score: 10
Accepted
time: 42ms
memory: 4592kb

input:

100000
672106 221171
672106 883430
672106 288290
672106 -658799
141374 -131948
141374 158602
141374 309649
141374 650353
141374 642956
141374 -768194
141374 -718417
672106 249667
672106 784734
141374 470511
141374 98035
672106 998389
672106 352965
141374 898640
672106 -536287
672106 -578615
141374 -...

output:

6899516

result:

ok single line: '6899516'

Test #49:

score: 10
Accepted
time: 48ms
memory: 4600kb

input:

100000
-816116 922009
315232 922009
-249356 922009
610000 949351
490680 949351
582100 949351
292220 922009
-987840 949351
595672 922009
-937660 922009
254856 922009
-13192 949351
583064 922009
-350928 922009
-646536 949351
-965832 922009
-193972 949351
-725520 922009
-820104 922009
315472 949351
670...

output:

109368

result:

ok single line: '109368'

Test #50:

score: 10
Accepted
time: 43ms
memory: 4588kb

input:

100000
-400087 361704
168413 -522429
259093 -522429
-133567 361704
-63837 -522429
507753 -522429
327713 361704
-564507 361704
-367307 361704
-783337 361704
-9157 -522429
-827827 -522429
725203 361704
414713 -522429
-125927 361704
877363 361704
812293 361704
-537707 -522429
910523 361704
634733 -5224...

output:

8841330

result:

ok single line: '8841330'

Test #51:

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

input:

1
393683 -129821

output:

-1

result:

ok single line: '-1'

Test #52:

score: 10
Accepted
time: 67ms
memory: 4596kb

input:

99540
40621 884068
577951 239764
-786692 884068
-889682 -915438
820492 -309724
-618176 881224
-464684 -8446
-336083 -615316
-278327 918718
773440 -147292
100609 -406310
594181 -347808
71233 39452
374938 -406310
498904 -276194
877597 797536
259045 305700
853963 605276
-670709 615112
-336083 784766
11...

output:

6

result:

ok single line: '6'

Test #53:

score: 10
Accepted
time: 67ms
memory: 4572kb

input:

99802
605960 -462294
118320 -783465
993870 91908
-864144 -429162
324342 290253
123132 695739
-723136 -925983
-762138 -997044
-580284 -224673
-955872 150849
552280 -842922
993870 -496248
882382 -536550
748448 -118500
936372 -155847
486570 -92055
-545100 -168126
865686 -500748
-362208 740640
-133172 -...

output:

6

result:

ok single line: '6'

Test #54:

score: 10
Accepted
time: 50ms
memory: 4748kb

input:

99969
-999614 -981865
648284 413937
-434763 -919276
739858 -950234
320831 -321652
98406 637373
579061 -919276
-744205 -203204
863982 385671
-35049 -919276
-998529 913303
-742903 413937
620942 -244930
-97328 59939
-256172 769281
710997 -713338
-254653 202615
508970 -919276
289800 -197147
745066 -1971...

output:

146041

result:

ok single line: '146041'

Test #55:

score: 10
Accepted
time: 50ms
memory: 4624kb

input:

99944
-998018 -997121
573972 520015
-31738 362215
409752 82831
-583898 -594737
-470848 738151
967267 -565553
140217 -256889
906577 -296009
-564858 -340937
562667 -389249
156877 82831
-226898 352183
822087 631591
955367 -429545
975597 951175
488887 152239
-188818 502783
-813568 -943457
236012 240223
...

output:

14280

result:

ok single line: '14280'

Test #56:

score: 10
Accepted
time: 47ms
memory: 4692kb

input:

99960
-997576 -997846
-800914 304194
-415036 522634
14204 507584
-409780 -266416
-351088 449964
-613012 694204
-408904 -225996
656750 247434
879254 -651266
-186838 949194
-788212 928984
616454 -118496
76400 752684
-226258 683884
-351088 -997846
-630532 16524
60194 -904106
-925306 973274
-398830 -615...

output:

188340

result:

ok single line: '188340'

Test #57:

score: 10
Accepted
time: 52ms
memory: 4600kb

input:

99544
-995276 -991700
-297341 -757684
333499 596428
334024 13092
-506186 893492
527434 -872988
-69176 536220
-191606 -596940
-36836 998004
816394 416372
133159 -684980
550009 -991700
281734 249380
-114851 -523100
-607931 787276
595999 248812
-872741 -527644
-739811 -831524
-309731 -680436
-401711 19...

output:

59640

result:

ok single line: '59640'

Test #58:

score: 10
Accepted
time: 48ms
memory: 4608kb

input:

99864
-990863 -998600
754487 300100
-154703 630880
377277 73660
-254533 -566255
-555363 -202175
467727 -607880
425517 -842645
-816663 -465800
-555363 331735
-475633 -4595
67737 436630
-255873 -455810
688827 -939770
-795893 -924785
665377 212410
-282003 73660
-818003 431635
67067 891730
-826043 -3353...

output:

371850

result:

ok single line: '371850'

Subtask #4:

score: 29
Accepted

Test #59:

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

input:

5
0 0
1 0
-1 0
0 1
0 -1

output:

1

result:

ok single line: '1'

Test #60:

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

input:

100
-30 -13
-22 -19
32 9
-18 -11
50 19
16 5
-50 -17
-46 -21
10 -1
-56 -19
2 -11
-24 -15
-4 -11
-8 -11
4 7
-8 -5
34 9
18 7
20 1
-12 -11
-30 -23
-42 -13
-24 -3
16 11
-16 -7
-24 -21
2 -9
28 11
6 -9
-22 -11
4 -7
28 7
-36 -15
-20 -21
4 11
-8 5
20 5
30 21
58 19
4 -1
-46 -19
-6 3
2 11
46 15
18 -1
-24 -7
-2...

output:

4

result:

ok single line: '4'

Test #61:

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

input:

100
66 27
38 -18
-39 -35
-4 9
-18 -24
24 26
17 6
-4 -26
-46 -6
52 1
17 -15
73 26
31 -10
-46 -27
-4 23
17 -29
-74 -37
-11 -39
-4 2
-11 10
3 -34
3 -41
-39 0
10 -14
31 -3
-18 -10
-25 -30
10 0
-53 -33
-18 -31
38 31
10 -35
24 5
52 22
-60 -32
-11 -32
17 13
-81 -36
3 29
-18 -45
-67 -31
45 23
31 -17
45 30
-...

output:

49

result:

ok single line: '49'

Test #62:

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

input:

100
-36 37
19 49
31 -23
-16 61
-22 -65
40 -23
-48 1
-2 -41
-1 25
15 55
16 -41
-28 -29
30 19
48 19
8 -29
0 37
-8 -59
31 31
11 -47
12 19
15 1
36 -17
-49 -11
-6 73
-5 -23
-31 -11
-46 25
-33 -35
-44 -5
-42 -35
-21 -53
30 -35
1 49
46 -5
35 -29
10 49
-3 55
28 -5
25 -41
12 73
40 31
-54 -17
56 7
27 -17
-17 ...

output:

54

result:

ok single line: '54'

Test #63:

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

input:

100
-13 12
-9 32
15 -40
1 34
5 -18
10 -29
4 1
12 -19
-5 28
-4 33
10 -17
-18 47
3 -28
-13 36
7 -20
3 -4
13 -50
2 27
8 -39
6 -37
8 -15
-7 18
-14 31
-6 -1
-16 45
-12 41
-1 24
-2 -17
-17 40
9 -22
-8 13
6 -1
-5 4
-7 -6
13 -38
15 -52
-3 14
3 20
1 -2
-16 33
2 -9
4 -23
-8 -11
-3 -34
3 8
-3 38
-2 -29
8 9
1 -...

output:

12

result:

ok single line: '12'

Test #64:

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

input:

100
16 -91
-12 21
-19 70
6 -49
-6 0
4 -28
-6 -14
9 -49
-8 -7
8 -49
-6 14
-14 42
-3 0
7 -42
3 -21
-1 0
0 -14
13 -70
9 -63
0 -35
11 -70
-8 14
1 -28
-9 35
1 -14
-3 7
8 -63
7 -35
6 -35
-4 0
-10 21
5 -35
13 -77
4 -49
-13 49
-10 28
1 -35
11 -56
0 -7
-11 14
-5 21
-9 7
0 -28
-6 28
9 -42
-4 14
-3 -7
-7 7
-5 ...

output:

7

result:

ok single line: '7'

Test #65:

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

input:

9
0 -79
0 43
0 -67
0 -61
0 -5
0 93
0 -65
0 45
0 -51

output:

-1

result:

ok single line: '-1'

Test #66:

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

input:

9
-29 1
67 1
-26 1
61 1
-68 1
-77 1
4 1
70 1
-89 1

output:

-1

result:

ok single line: '-1'

Test #67:

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

input:

9
75 -77
-50 48
39 -41
-40 38
-32 30
-73 71
-75 73
92 -94
56 -58

output:

-1

result:

ok single line: '-1'

Test #68:

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

input:

10
1 21
1 -15
1 7
1 -69
1 -67
1 -37
-83 -58
1 23
1 -25
1 -95

output:

168

result:

ok single line: '168'

Test #69:

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

input:

10
11 -10
72 -71
39 -38
84 -83
-26 27
58 79
74 -73
71 -70
-78 79
93 -92

output:

136

result:

ok single line: '136'

Test #70:

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

input:

10
1 0
64 0
4 -7
19 0
-35 0
-44 0
91 0
100 0
37 0
46 0

output:

63

result:

ok single line: '63'

Test #71:

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

input:

1
0 -20

output:

-1

result:

ok single line: '-1'

Test #72:

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

input:

100
-44 -7
52 14
-8 -1
8 1
37 11
22 5
30 6
-2 5
56 16
-2 2
-3 3
-39 -9
35 13
-16 1
-32 -4
33 12
58 17
-32 -10
-19 1
-16 -5
-28 1
21 9
3 6
-12 0
-15 3
-4 4
7 -1
-40 -5
6 3
20 7
19 5
10 5
44 10
32 13
7 2
55 17
34 14
38 13
-36 -6
-22 -5
41 13
-6 6
-4 1
-60 -15
32 10
3 -3
-49 -11
34 11
-20 -1
-5 -1
5 4
...

output:

3

result:

ok single line: '3'

Test #73:

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

input:

100
14 9
-49 -12
12 2
-10 -3
-20 -8
-51 -10
40 13
53 15
-3 5
36 8
24 11
39 8
-1 0
37 10
-10 0
-39 -7
-2 -2
-58 -15
9 -1
-12 -7
47 12
34 7
-14 -2
-22 -6
-27 -1
-50 -11
10 1
-38 -8
-10 -6
-32 -5
19 7
2 6
37 7
27 8
0 5
-21 -1
-23 1
-6 -4
23 3
36 11
-13 3
49 13
-28 0
-23 -2
-24 -4
-5 -5
49 16
2 -3
-37 -...

output:

3

result:

ok single line: '3'

Test #74:

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

input:

100
-88 -27
-4 3
-4 -6
-53 -19
31 17
-39 -2
-39 -11
-11 -13
45 25
-18 10
-18 -5
59 30
52 17
10 11
17 3
-25 -18
-25 -6
-39 -17
-32 -10
-32 -7
-67 -18
-46 -6
-11 5
17 15
-46 -9
45 22
10 5
-25 -12
-4 6
73 29
-4 -12
-4 21
31 23
-18 4
-11 -4
-25 6
-53 -13
-81 -26
3 7
52 29
-67 -24
17 0
-4 18
-46 -3
-60 -...

output:

21

result:

ok single line: '21'

Test #75:

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

input:

100
-65 76
-7 18
-26 44
-18 1
42 -46
-30 22
-27 24
-10 -13
33 -23
5 26
-47 59
12 21
44 -35
-42 43
22 -11
25 -9
21 -2
-17 -8
-30 51
9 -10
49 -51
26 -18
55 -47
-31 31
-18 30
9 19
20 7
-26 15
-50 57
48 -42
15 -6
-36 47
23 -20
0 -16
41 -37
0 13
17 -24
-19 39
-5 0
20 -22
6 -12
28 -7
18 -4
-23 46
-5 29
13...

output:

29

result:

ok single line: '29'

Test #76:

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

input:

100
-50 52
-14 -16
36 -6
6 -6
46 -46
-31 -5
29 5
-13 11
-21 5
9 5
-19 19
-20 12
13 -27
-38 16
-11 25
30 -8
-7 -7
24 10
-3 -19
33 13
17 1
3 -7
26 -26
-42 38
-17 3
-48 56
-19 -11
28 -12
37 -19
-8 16
-31 15
-34 44
6 24
-29 -1
-23 41
42 -24
-25 7
-42 28
-6 -10
42 -44
-27 33
31 9
0 2
6 -16
-34 14
20 12
-...

output:

10

result:

ok single line: '10'

Test #77:

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

input:

100
-68 -8
6 -3
12 -2
-6 3
-2 -5
-22 -5
-22 -3
-12 0
8 0
-10 -3
-6 -1
-50 -7
38 5
36 4
-16 -2
6 -1
-10 1
-16 -4
-66 -7
40 4
-52 -6
-12 2
8 6
-6 1
-54 -5
12 4
-46 -7
-28 -2
28 2
10 3
52 4
42 5
34 3
14 5
-52 -4
-32 -4
0 0
6 1
4 2
-20 0
-48 -6
38 3
-24 -8
4 -4
-20 -2
40 6
-60 -6
16 -2
-4 4
-44 -6
40 2
...

output:

4

result:

ok single line: '4'

Test #78:

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

input:

100
-22 -70
-33 -18
-36 -32
17 2
28 10
-26 -22
-25 -54
-16 -22
-17 -20
-4 -36
3 20
25 16
16 44
-40 -34
-25 -34
27 42
38 20
-8 2
-12 10
15 26
-10 -44
-5 -4
-33 -48
-4 24
-6 -12
28 20
-16 -12
11 34
9 18
14 -22
33 20
3 -30
-15 -4
35 26
-37 -20
-10 -24
15 -14
24 38
-19 -6
22 52
-40 -24
43 20
19 -12
-3 2...

output:

10

result:

ok single line: '10'

Test #79:

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

input:

78
-38 21
-60 55
-9 46
5 36
80 -29
-37 66
-27 -12
29 -4
43 -62
31 -58
63 6
60 -49
59 -14
-5 -30
-53 -46
47 70
-9 -18
17 16
25 -40
-36 -65
71 30
-49 -42
16 51
81 32
-40 -69
-33 -10
0 35
9 -40
75 -46
-17 54
75 -14
49 -16
-21 -30
39 46
41 24
9 24
28 -33
21 -60
-33 70
-60 23
-2 9
-1 -42
-21 66
69 36
-41...

output:

1

result:

ok single line: '1'

Test #80:

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

input:

79
-53 16
29 -22
62 45
21 50
51 -8
-9 60
-35 42
19 72
62 39
67 -40
-8 25
44 15
19 -24
-63 62
-59 50
46 55
17 49
-4 -3
-41 -36
28 61
-57 -52
-45 56
36 -59
65 -2
-15 -34
71 -4
-3 -38
-29 -24
-20 -51
55 -20
23 12
34 -53
43 -16
-19 74
-25 28
3 56
-3 10
-53 32
-8 -23
-28 -27
-5 32
-23 -10
-41 60
-57 28
3...

output:

1

result:

ok single line: '1'

Test #81:

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

input:

79
-35 -6
-19 -54
-9 8
-19 -6
-3 -2
35 4
59 20
-14 -31
51 44
-42 -19
43 36
-24 67
25 46
3 44
57 -34
-3 -6
73 -34
41 -18
78 37
-37 20
29 -38
-30 81
33 38
1 54
-14 1
-51 26
-15 6
67 28
-3 42
24 -61
-51 42
-40 -13
77 -22
-37 -12
75 20
13 42
33 22
10 73
17 54
-47 6
41 -50
-3 10
-19 74
59 68
-51 74
9 -34...

output:

4

result:

ok single line: '4'

Test #82:

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

input:

80
-2 -46
30 -14
-36 -8
30 -30
37 -51
10 -34
2 -58
-54 14
13 21
27 27
32 -36
14 34
19 67
66 -10
72 -44
-34 -62
-4 72
30 66
-2 66
46 -30
60 -28
-30 70
66 6
34 54
0 -62
0 28
74 46
73 -47
12 8
78 50
84 -48
41 -47
46 50
18 22
50 -26
-16 12
64 -68
5 29
-9 -57
58 30
48 -4
75 -53
-34 34
-36 34
46 66
-47 25...

output:

2

result:

ok single line: '2'

Test #83:

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

input:

78
8 10
53 31
81 -53
11 -27
21 79
1 75
5 -1
37 31
-31 59
-37 -59
78 64
85 47
49 75
27 37
33 59
31 49
-44 -58
60 14
-47 11
29 55
40 58
7 -47
-47 59
79 6
45 -25
-41 33
-11 -33
49 -21
-47 -5
17 -53
82 -60
1 27
5 79
-25 -47
29 7
49 11
-15 -5
15 -7
-30 68
74 28
37 15
18 -60
-43 -17
-32 66
50 20
1 11
87 1...

output:

1

result:

ok single line: '1'

Test #84:

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

input:

79
-63 -54
27 -20
-33 0
58 55
-65 52
3 -44
-1 -32
-5 44
-65 0
19 -28
67 20
-54 -25
31 -16
-68 -63
35 52
-71 -46
-15 -6
-47 -70
-33 -64
-31 42
-49 48
8 -67
-47 -6
44 49
61 -26
-1 0
-7 34
-16 69
49 10
45 -10
-35 22
11 -20
47 -48
67 -12
38 51
-22 55
63 -64
59 -52
-21 -68
-31 -6
38 -61
9 50
14 59
-45 36...

output:

4

result:

ok single line: '4'

Test #85:

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

input:

79
-65 68
3 72
47 20
-35 10
-29 -40
49 -66
31 36
-54 -53
3 -56
34 -61
31 52
-65 -12
68 -3
-39 -58
19 -56
13 26
14 -33
27 -64
47 -60
-17 68
69 -14
45 74
-39 38
63 -28
-54 74
-37 -48
27 -32
9 -58
47 4
-70 11
43 64
-58 71
-63 62
-20 21
-33 20
-45 -40
-7 22
47 -44
65 -34
-51 26
-21 -32
42 11
64 75
-1 68...

output:

1

result:

ok single line: '1'

Test #86:

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

input:

79
46 -30
-46 -2
9 -45
57 19
18 -50
66 30
31 -43
6 10
-45 65
50 30
-46 62
2 -50
56 -32
38 -54
-62 30
45 15
-46 -34
-62 -18
16 56
22 26
6 -38
-50 -14
-5 41
-28 36
70 -38
-1 37
43 73
-44 36
-39 -45
54 42
66 62
-30 -50
-26 42
1 -53
18 46
-4 -4
-26 -54
-12 36
-48 -56
-16 72
12 -4
-52 76
-8 -48
22 -38
0 ...

output:

1

result:

ok single line: '1'

Test #87:

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

input:

79
41 -32
-40 -13
11 -22
57 16
17 56
68 -1
-57 70
-10 -55
79 -34
-57 -10
43 -6
33 -8
79 -50
-33 -50
79 62
-58 -39
69 12
70 41
6 25
-55 -48
-35 -28
15 -18
-21 -38
63 62
11 10
-9 -58
58 -3
43 -54
74 -19
77 4
75 42
16 59
-5 58
-30 -27
-57 22
17 40
-37 42
23 -42
-41 22
42 -35
-21 26
-51 -12
5 28
55 -42
...

output:

2

result:

ok single line: '2'

Test #88:

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

input:

79
57 50
-39 2
73 2
51 -28
63 75
9 34
19 36
15 32
39 -8
6 59
33 -38
67 36
-59 -18
-29 48
54 75
-29 -12
-27 78
41 66
71 -40
73 -30
14 67
-33 32
70 -53
7 24
49 74
25 -14
41 -46
-24 5
-61 -28
5 -2
-23 -14
10 79
65 58
-43 -2
-32 -35
38 -37
-11 -34
27 28
7 -24
53 46
-30 71
5 -50
55 -36
-31 26
-31 42
31 1...

output:

1

result:

ok single line: '1'

Test #89:

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

input:

74
-16 48
-44 -28
-42 -2
-62 26
-36 28
-28 68
60 44
-44 4
66 -70
-32 32
60 28
32 0
64 -16
-68 28
0 -16
-18 22
62 38
60 -68
-52 -36
-17 -53
38 62
36 4
32 -32
-4 -52
30 54
60 12
-64 -48
48 16
-64 -16
-16 -48
52 36
-6 -46
-44 52
0 -48
54 14
-30 58
-60 -44
-64 16
-12 -44
-42 -18
-60 52
-16 0
64 -64
32 6...

output:

2

result:

ok single line: '2'

Test #90:

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

input:

75
-69 -42
-33 -22
-53 -10
-63 -60
-55 44
-27 -56
-61 46
-17 42
-13 -10
47 -22
21 72
-69 38
21 -24
-43 -8
-59 40
-5 -26
9 28
67 46
-24 39
-17 10
-23 -20
21 -56
35 14
35 -2
-29 -2
-49 -54
-49 42
27 -58
-35 32
9 12
-5 22
31 -38
-1 -22
19 62
51 -34
27 22
15 26
63 58
-65 -38
-65 -6
27 -26
-5 38
31 -22
-...

output:

8

result:

ok single line: '8'

Test #91:

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

input:

74
57 59
11 69
81 3
-5 69
-53 -43
-49 -23
73 27
39 81
45 -17
73 -53
49 35
-47 51
49 83
55 -31
-55 27
23 1
-35 31
-49 9
-35 79
49 3
43 -27
13 79
-7 43
13 -49
-51 -33
13 47
15 57
-33 -7
-21 21
81 19
77 -49
65 -13
55 49
1 35
23 65
59 5
17 51
-46 56
13 -17
-17 41
-9 -15
77 63
77 -17
61 47
83 -51
-51 -17...

output:

2

result:

ok single line: '2'

Test #92:

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

input:

75
57 28
33 -44
-19 -16
17 20
-55 28
-31 -44
19 38
7 42
1 36
1 -12
9 76
-55 -52
11 78
-19 -48
-31 84
29 48
65 52
-49 82
13 32
-3 -16
71 -38
57 -36
-29 70
13 -16
45 -48
33 -12
23 26
3 -26
61 -48
43 14
-3 -48
35 38
45 80
-25 -38
-35 80
-35 16
-37 -34
74 31
-10 -15
41 44
-31 4
48 17
-51 48
55 58
51 54
...

output:

2

result:

ok single line: '2'

Test #93:

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

input:

75
-48 45
-34 83
54 11
30 3
-4 73
66 7
36 49
32 -19
-48 -35
32 -3
48 -3
44 -23
0 61
-12 49
4 49
-38 31
48 61
-66 -45
-20 9
16 -3
20 -15
-58 75
-68 -7
-16 -3
-20 -23
-4 57
-20 -39
-22 -1
-28 17
12 41
64 -3
-2 51
-20 25
-19 70
68 49
44 -39
42 15
-38 47
-70 47
54 75
18 39
-48 77
68 1
4 -47
16 -19
70 -3...

output:

4

result:

ok single line: '4'

Test #94:

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

input:

3
100 -77
-100 -100
-60 100

output:

39080

result:

ok single line: '39080'

Test #95:

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

input:

3
81 100
100 -70
-100 -100

output:

34570

result:

ok single line: '34570'

Test #96:

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

input:

3
-100 -100
100 -100
-74 100

output:

40000

result:

ok single line: '40000'

Subtask #5:

score: 15
Accepted

Dependency #2:

100%
Accepted

Test #97:

score: 15
Accepted
time: 1ms
memory: 3648kb

input:

2000
-141033 500883
-457875 317099
570107 -451327
-258775 83073
-48988 -181339
184246 148615
322139 -358663
205746 -28713
-246818 493221
315791 -439181
243789 -493721
-152335 -120605
-290252 397465
359491 -136925
321141 -96245
-410156 465995
192919 -87583
464977 -450703
99537 240803
-279989 264903
-...

output:

19966

result:

ok single line: '19966'

Test #98:

score: 15
Accepted
time: 1ms
memory: 3644kb

input:

2000
-135598 -90332
173830 142382
-5414 25496
-82528 -67798
40478 -10214
385764 525926
115398 169908
251308 294282
263590 294314
-531578 -666220
442932 537116
-371396 -521102
-245894 -230144
-429180 -568306
23432 -73138
177504 290528
-331520 -358256
169528 111726
17898 170554
409940 496694
13828 -53...

output:

5972

result:

ok single line: '5972'

Test #99:

score: 15
Accepted
time: 1ms
memory: 3828kb

input:

999
358449 23473
312882 20485
244806 16021
-99966 -6587
-527088 -34595
214611 14041
351312 23005
-383250 -25163
541266 35461
499542 32725
350763 22969
-3342 -251
-505677 -33191
91635 5977
23010 1477
186612 12205
236571 15481
-250392 -16451
-35733 -2375
353508 23149
-474384 -31139
607695 39817
369978...

output:

-1

result:

ok single line: '-1'

Test #100:

score: 15
Accepted
time: 1ms
memory: 3632kb

input:

999
184536 -196295
-436851 464755
102474 -108995
459909 -489245
-275688 293305
34794 -36995
-390744 415705
-133983 142555
445527 -473945
-352251 374755
-385245 409855
-124254 132205
172692 -183695
-133560 142105
126162 -134195
-431775 459355
371079 -394745
313551 -333545
-372132 395905
308898 -32859...

output:

-1

result:

ok single line: '-1'

Test #101:

score: 15
Accepted
time: 1ms
memory: 3636kb

input:

999
319017 -174498
336878 -184271
-69208 37927
522590 -285887
-523895 286718
-24582 13509
502874 -275099
181747 -99388
-91309 50020
-462362 253049
-138002 75569
-283222 155029
126680 -69257
331472 -181313
524922 -287163
-431039 235910
-156393 85632
-264778 144937
434504 -237689
473830 -259207
450881...

output:

-1

result:

ok single line: '-1'

Test #102:

score: 15
Accepted
time: 1ms
memory: 3604kb

input:

1000
-17417 -44014
-67007 -169294
-140537 -355054
244555 617810
-51275 -129550
328345 829490
293461 741362
56797 143474
-304013 -768046
184705 466610
359809 908978
-265025 -669550
264733 668786
-243479 -615118
-203123 -513166
-332057 -838894
-206543 -521806
-60851 -153742
-178841 -451822
256183 6471...

output:

495647892

result:

ok single line: '495647892'

Test #103:

score: 15
Accepted
time: 1ms
memory: 3556kb

input:

1000
56959 91431
-84971 -136404
-331591 -532294
5659 9081
-221771 -356004
-256921 -412429
-188901 -303239
-231461 -371559
316499 508061
-217971 -349904
-257871 -413954
-70721 -113529
242779 389721
203449 326586
-157171 -252304
15349 24636
-35001 -56189
-285231 -457874
67599 108511
367419 589801
-236...

output:

227636110

result:

ok single line: '227636110'

Test #104:

score: 15
Accepted
time: 1ms
memory: 3496kb

input:

1000
26329 -26297
-105751 105783
333129 -333097
387209 -387177
329 -297
-224571 224603
-68311 68343
291009 -290977
-337931 337963
-496011 496043
462089 -462057
429849 -429817
-130711 130743
489909 -489877
119149 -119117
-200131 200163
-506151 506183
457149 -457117
102249 -102217
261629 -261597
-3506...

output:

261614080

result:

ok single line: '261614080'

Test #105:

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

input:

1
107644 26211

output:

-1

result:

ok single line: '-1'

Test #106:

score: 15
Accepted
time: 2ms
memory: 3508kb

input:

2000
-483181 -135362
120902 24064
-412531 -99494
248281 7808
391568 85654
-434900 -137287
186379 -16165
-237918 -5538
-178979 -39463
116383 11996
118455 7143
-119819 2177
39381 -8652
286531 117200
-515476 -155072
433170 139776
-686268 -197130
113483 -803
-625355 -175486
618652 160760
-629133 -179889...

output:

3

result:

ok single line: '3'

Test #107:

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

input:

2000
-153446 -476364
-58849 -109096
-64979 -300504
-59262 -73790
72470 331460
-38560 -93304
75104 258470
69518 140774
18199 -34338
50612 295913
-134053 -452725
-112713 -282410
-32113 -126910
90947 290009
-42412 -148636
94286 466304
145398 440980
-5863 -106726
78568 151356
-14920 -148693
-5070 -22968...

output:

3

result:

ok single line: '3'

Test #108:

score: 15
Accepted
time: 1ms
memory: 3564kb

input:

2000
-561515 -300547
-272987 -170363
56834 217598
-241871 -133432
-62733 120307
17642 304180
-406136 -254349
193074 -155474
364670 -130523
-146248 -368154
275334 344334
-396350 -91744
-272100 -136797
-247541 220142
-98888 155114
452867 229039
252322 311461
-202909 306360
-341041 -275524
-91685 63458...

output:

45821

result:

ok single line: '45821'

Test #109:

score: 15
Accepted
time: 1ms
memory: 3564kb

input:

2000
-678600 -801617
-124824 -23261
504424 541290
-226632 -357875
439222 481887
146300 269633
-138228 87691
-397804 -368314
198456 209830
-245638 -450088
21860 96857
61012 -57876
-619482 -699026
437088 293827
-257724 -167618
48290 -91195
-90622 142142
211138 165957
-302988 -269759
232366 231240
4025...

output:

31542

result:

ok single line: '31542'

Test #110:

score: 15
Accepted
time: 1ms
memory: 3512kb

input:

2000
509283 -512882
48560 115371
-413913 58282
152594 50328
-214124 12026
-354159 326905
186967 -31240
-71851 207825
-232071 73747
-494950 455418
-398975 94559
-425588 103142
14494 -149572
394066 -86788
-474904 127359
110674 -202318
-305542 305850
-445681 215550
-190760 201731
-433298 308843
291511 ...

output:

9753

result:

ok single line: '9753'

Test #111:

score: 15
Accepted
time: 1ms
memory: 3552kb

input:

2000
-699722 159002
665794 -176842
295240 -513421
-265278 -7034
-58878 -97094
-345962 465692
-1168 592131
-165186 118288
139308 369517
497798 32412
96896 -658455
163562 -76494
-301552 167847
-26374 -660870
-224248 594081
194854 -555352
-28764 -375995
-5162 -681508
-100156 -332337
19228 347357
307856...

output:

63420

result:

ok single line: '63420'

Test #112:

score: 15
Accepted
time: 1ms
memory: 3556kb

input:

2000
226750 -584546
128372 -201112
197627 -489887
139449 -155797
-92337 106205
237230 -416794
-66845 43113
146162 -368286
-150867 201519
-122893 161657
119595 -233095
-143384 358972
-44369 96485
192394 -341302
-49095 -50997
-162891 162791
198384 -322028
176172 -230480
5882 -2622
207073 -304789
-2551...

output:

7192

result:

ok single line: '7192'

Test #113:

score: 15
Accepted
time: 1ms
memory: 3624kb

input:

1865
-283242 786441
-427198 177357
-860350 598221
736066 -920371
672322 -509491
-711950 -513315
99778 -435123
-190918 249653
303922 -73827
-225302 -631995
-253118 -578355
420930 317389
719682 -936755
-216254 187597
722754 -812851
-697112 -849761
693058 97485
373570 285901
-58494 -603763
341688 11854...

output:

128

result:

ok single line: '128'

Test #114:

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

input:

1866
-413422 371588
-114120 -97828
374870 397076
-760254 495172
431186 -130940
-644526 -780156
-504584 566492
-247745 300888
-505518 586884
-271278 532612
-328942 332676
742266 609828
-657054 -807228
308818 51332
783666 536580
-461294 -8316
-33205 -300280
271973 459184
647074 126916
-98482 -815628
-...

output:

8

result:

ok single line: '8'

Test #115:

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

input:

1865
-238889 499619
361919 752907
482015 -68565
-465185 639019
39647 -609237
-387669 31159
638975 -591029
-153937 1275
253247 855179
-693121 -217141
-711745 424715
267807 721771
-169557 -291401
-247073 480299
-406817 -760789
234135 -248989
661727 -126421
-266417 -792677
-655953 347131
-314337 426347...

output:

4

result:

ok single line: '4'

Test #116:

score: 15
Accepted
time: 1ms
memory: 3544kb

input:

1865
564188 721281
-396178 797173
630894 745973
410251 301047
-346962 -506763
595950 -729867
744046 -301579
95342 -218635
-326546 477685
-574338 352405
562876 565825
164974 379381
287814 -767643
-787106 -787115
736366 653813
-691090 240117
-640914 283125
-752530 -472587
183150 -675851
-727698 -36353...

output:

128

result:

ok single line: '128'

Test #117:

score: 15
Accepted
time: 1ms
memory: 3772kb

input:

1865
531480 805379
734468 -579730
-781052 -745618
448100 -741050
-575836 471638
-263324 -283002
-781052 286574
-383940 -613604
101636 433518
427332 533630
-746236 -401042
-83132 -734722
-583420 -331666
772 168686
-326396 -173202
-464124 -594706
-335776 -591563
-201596 -23730
-824060 415086
-438668 1...

output:

16

result:

ok single line: '16'

Test #118:

score: 15
Accepted
time: 1ms
memory: 3508kb

input:

1772
641287 -670370
572680 194224
-396968 510907
260959 814252
633595 499972
-642824 -702041
-475301 -636404
100432 -714434
281971 387409
-492821 -425912
367264 -321179
-317267 525190
241876 -747644
-250280 -184856
916564 520303
183556 92164
793090 943069
338752 792733
908182 262750
-186047 288994
-...

output:

81

result:

ok single line: '81'

Test #119:

score: 15
Accepted
time: 2ms
memory: 3584kb

input:

1848
-506289 16332
-367281 -154164
111695 -70708
-348337 403916
188847 -106612
719655 291772
-232721 913420
370895 -532276
651407 137804
120655 -280116
-609425 7436
509775 104908
-159921 -529972
424015 -175156
-773293 -572620
-78019 -144520
-562353 803276
-188033 298668
-12535 84272
-691937 -389908
...

output:

32

result:

ok single line: '32'

Test #120:

score: 15
Accepted
time: 2ms
memory: 3548kb

input:

1794
-739390 -567358
-191476 584291
315584 -823165
439433 152480
-523621 662672
-348313 570098
946817 -542986
498482 34382
-662815 -733255
-466279 -200527
-478891 -730987
485360 73748
-177976 155234
-589429 -316996
-547309 7166
285128 392321
-434107 -214828
763352 -314080
281246 -663208
530915 13763...

output:

9

result:

ok single line: '9'

Test #121:

score: 15
Accepted
time: 1ms
memory: 3840kb

input:

1771
653319 840369
770688 -717747
-383481 725943
-836001 -602205
112383 876741
-240921 -685833
-333342 932277
-201717 476949
323082 885567
808596 37011
187488 -587742
-573588 -638043
251658 695376
-437355 -663948
-109809 -164337
-663255 410259
649800 892674
-13959 -128796
738774 -254616
-844776 9606...

output:

81

result:

ok single line: '81'

Test #122:

score: 15
Accepted
time: 2ms
memory: 3776kb

input:

1793
-253678 591131
-354739 601418
-814630 882407
135122 779942
689648 665489
-835177 545933
218957 -11752
-332167 -720340
785064 -287698
838688 898283
393539 801407
713219 585299
120542 106346
696452 672779
301307 341732
-45666 -561865
-425455 -226573
36707 602795
-745369 -99133
5063 222095
-465853...

output:

3

result:

ok single line: '3'

Test #123:

score: 15
Accepted
time: 1ms
memory: 3512kb

input:

1778
764495 -682617
-26020 -268572
784583 703698
-775153 -65883
-509581 321378
626714 380265
-815248 509298
-588490 -800625
403937 589893
-536770 334338
246581 743064
277073 351132
651500 -752601
182753 -144615
-800884 391038
-213418 58533
-774739 137454
266879 -200469
102806 -229179
-747451 -192729...

output:

27

result:

ok single line: '27'

Test #124:

score: 15
Accepted
time: 1ms
memory: 3556kb

input:

1771
-49615 -880989
842681 634602
323633 -806631
-462958 418089
471593 -394908
-835153 -393531
50258 505569
-436774 -447675
59735 -47742
-612805 739758
186581 595236
122429 466203
-293101 -314556
245630 122844
456866 -918645
306866 195015
344045 -526695
433550 -483927
-82420 -605427
-830374 162210
4...

output:

243

result:

ok single line: '243'

Test #125:

score: 15
Accepted
time: 1ms
memory: 3808kb

input:

1745
960793 447774
811456 392991
20248 -501978
-132176 917691
223153 -357150
-330401 832821
592594 130713
640627 904992
-345386 -709338
259846 -26427
872935 -88392
-353000 -148413
461266 387429
217078 836466
-388640 -600474
46492 -272343
-546293 209634
766501 726630
155113 111111
-29567 -603066
5334...

output:

81

result:

ok single line: '81'

Test #126:

score: 15
Accepted
time: 1ms
memory: 3556kb

input:

1849
-600539 185762
70597 -279078
-318523 -865830
-13371 378842
-136891 833018
-715835 -262694
-532331 -379786
-310331 -859686
-646203 461274
-563643 -72774
-270619 59442
164421 -739142
71997 -481516
611781 675674
-35899 345562
-164539 -547590
222149 342490
-379963 497114
-202491 635338
811973 37525...

output:

128

result:

ok single line: '128'

Test #127:

score: 15
Accepted
time: 1ms
memory: 3624kb

input:

1745
869905 649804
-716318 -197978
-685052 343624
-227024 -166853
129241 -195431
-50282 -157925
603847 -283166
-564767 -51008
856945 115375
226927 883084
-535688 806494
121951 175225
-150695 631012
693487 -557744
196309 -461435
-468539 -165947
285976 49837
711010 541819
-319283 -484517
476245 522958...

output:

243

result:

ok single line: '243'

Test #128:

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

input:

3
-65500 1000000
1000000 585378
-1000000 -1000000

output:

2518464259000

result:

ok single line: '2518464259000'

Test #129:

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

input:

3
1000000 246017
-153000 1000000
-1000000 -1000000

output:

2944623601000

result:

ok single line: '2944623601000'

Test #130:

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

input:

3
-1000000 -1000000
834381 1000000
1000000 570721

output:

1118699241299

result:

ok single line: '1118699241299'

Test #131:

score: 15
Accepted
time: 1ms
memory: 3512kb

input:

2000
-301976 21673
151074 262495
699032 241939
-519994 -248624
-439396 -174407
-570166 -260090
251052 167482
-83402 61780
402930 228478
798238 257206
568120 258283
400524 295972
-62714 -116120
-864074 -273371
195422 -17258
-181692 76132
705540 263905
335954 302413
397804 91768
520350 182197
-777196 ...

output:

21162

result:

ok single line: '21162'

Test #132:

score: 15
Accepted
time: 1ms
memory: 3584kb

input:

2000
-401242 316210
-313594 -437773
315782 39399
120499 -489558
-71022 -92404
-217267 -152301
-164236 -477770
-329522 -196977
12479 689981
-363391 367433
197070 -119691
-817537 84947
-406544 347682
458551 76417
422856 67095
-289295 74178
314671 140684
305882 -284407
386402 248504
-385633 63911
41352...

output:

40403

result:

ok single line: '40403'

Test #133:

score: 15
Accepted
time: 1ms
memory: 3648kb

input:

2000
-431246 55797
525944 105440
-55672 -84177
48672 -218589
746644 26351
203114 218717
13692 -141634
-328552 170720
-300522 232202
277728 -237223
431172 -202668
-30578 -90530
-406472 -122995
385300 -34520
25212 70373
-400198 134191
63342 -333799
556122 -83846
-97140 -89674
-475880 91137
-379590 226...

output:

31474

result:

ok single line: '31474'

Subtask #6:

score: 35
Accepted

Dependency #1:

100%
Accepted

Dependency #2:

100%
Accepted

Dependency #3:

100%
Accepted

Dependency #4:

100%
Accepted

Dependency #5:

100%
Accepted

Test #134:

score: 35
Accepted
time: 49ms
memory: 4676kb

input:

100000
-43478 52580
98148 243700
-80622 53188
-8401 -16284
-64308 -380357
-38404 185811
-96747 -442931
-48137 -416770
-107636 58883
23586 16279
-71647 540213
-75859 418137
50172 -277016
73392 -309146
-86038 -342717
21324 -75995
64086 28384
-48718 -33360
-142261 112677
39229 -484192
-35532 -364610
62...

output:

15027

result:

ok single line: '15027'

Test #135:

score: 35
Accepted
time: 50ms
memory: 4604kb

input:

100000
-382174 -157913
-46633 5495
-426652 -153181
-33222 -125937
489758 59598
-36187 -290871
-104059 399812
-25768 56777
-643377 -191247
-269138 -182861
660845 289961
-298993 201110
-316660 103369
-225486 386785
430359 320838
-202271 12376
-639664 -123326
13936 139104
-52317 116690
249575 343518
30...

output:

22757

result:

ok single line: '22757'

Test #136:

score: 35
Accepted
time: 51ms
memory: 4588kb

input:

100000
-131440 211760
-451959 402424
-434499 397708
647092 -581152
-565321 475336
-654294 517784
2859 1888
350334 -298576
-59280 -83628
765054 -642908
176312 -114976
-158117 72244
-341346 222632
-123710 83120
128873 -148732
144123 -89168
-142348 202408
-538952 402508
-394119 362380
-82263 -29636
222...

output:

12148

result:

ok single line: '12148'

Test #137:

score: 35
Accepted
time: 56ms
memory: 4628kb

input:

100000
-310241 707459
-65417 160287
200589 -460301
-317616 722419
103594 -225421
49924 -111581
-97845 222771
85103 -193333
72968 -147413
217188 -492333
-23039 63263
-352178 799255
-285108 651115
-193220 433891
27702 -71065
-196432 437807
-168839 382583
85444 -207221
96417 -231345
-156963 360095
-484...

output:

620

result:

ok single line: '620'

Test #138:

score: 35
Accepted
time: 50ms
memory: 4724kb

input:

100000
186234 135550
-363519 -31821
351393 37325
-74520 21096
280302 -21914
41052 -2812
339618 118920
-166416 -40690
-235803 51183
262293 133235
345390 34560
-163536 70040
-288753 -58267
-412578 -47810
-73827 26033
-435642 -93752
-463650 -81092
-562542 -201038
-172536 -26246
-102213 -103619
-408006 ...

output:

8454

result:

ok single line: '8454'

Test #139:

score: 35
Accepted
time: 4ms
memory: 3592kb

input:

9999
8 282913
8 -40583
8 172321
8 -232571
8 -214913
8 261745
8 166525
8 -297047
8 -26579
8 -102827
8 -125165
8 -159869
8 157291
8 229273
8 166255
8 138427
8 -222833
8 -53093
8 219283
8 -291737
8 101419
8 -279641
8 34981
8 -38495
8 -196319
8 -29909
8 1051
8 271195
8 -282143
8 270475
8 -111359
8 -1409...

output:

-1

result:

ok single line: '-1'

Test #140:

score: 35
Accepted
time: 4ms
memory: 3524kb

input:

9999
0 88507
0 -132989
0 -24977
0 134599
0 31231
0 9271
0 43795
0 58507
0 186727
0 50035
0 -122753
0 -127445
0 102835
0 138835
0 -84917
0 175459
0 53995
0 -176897
0 107239
0 -68405
0 -184001
0 196903
0 -152369
0 107491
0 -195137
0 172879
0 -104261
0 164767
0 127447
0 112459
0 -34061
0 -194381
0 -148...

output:

-1

result:

ok single line: '-1'

Test #141:

score: 35
Accepted
time: 4ms
memory: 3784kb

input:

9999
9 97310
9 -152240
9 -112466
9 -113404
9 -129868
9 -186820
9 -162740
9 -67960
9 -198972
9 -48416
9 -164238
9 -10406
9 49738
9 -103786
9 187022
9 149082
9 -195458
9 -137372
9 87034
9 164958
9 7836
9 -36082
9 73118
9 -102792
9 -17630
9 -110884
9 -7326
9 -138870
9 99648
9 -26086
9 -27682
9 -66126
9...

output:

-1

result:

ok single line: '-1'

Test #142:

score: 35
Accepted
time: 4ms
memory: 3752kb

input:

10000
40080 -280540
-22480 157380
-43540 304800
29710 -207950
-5140 36000
35560 -248900
-27460 192240
77720 -544020
-57750 404270
-69860 489040
73500 -514480
97790 -684510
-23060 161440
-85730 600130
21430 -149990
-22550 157870
10870 -76070
6370 -44570
82050 -574330
-84580 592080
-5790 40550
48790 -...

output:

29466340

result:

ok single line: '29466340'

Test #143:

score: 35
Accepted
time: 4ms
memory: 3460kb

input:

10000
133726 44582
-222818 -74266
-397166 -132382
126814 42278
65056 21692
526252 175424
52096 17372
487138 162386
40144 13388
63976 21332
229288 76436
-470408 -156796
546016 182012
-482972 -160984
285142 95054
-219146 -73042
-286340 -95440
167476 55832
172318 57446
-515534 -171838
-471452 -157144
-...

output:

17620704

result:

ok single line: '17620704'

Test #144:

score: 35
Accepted
time: 4ms
memory: 3612kb

input:

10000
-12583 -1394
37205 4138
-572752 -63635
765881 85102
830249 92254
-411778 -45749
-772309 -85808
211247 23476
564029 62674
-557713 -61964
130031 14452
881981 98002
189458 21055
-471232 -52355
-455545 -50612
834218 92695
589841 65542
559817 62206
-615385 -68372
-26596 -2951
-244972 -27215
461780 ...

output:

3951732

result:

ok single line: '3951732'

Test #145:

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

input:

1
-8931 -940616

output:

-1

result:

ok single line: '-1'

Test #146:

score: 35
Accepted
time: 65ms
memory: 4592kb

input:

100000
-35209 -63672
157633 73636
-422564 -95102
215714 30978
99733 25930
-224156 -80549
-199462 -5367
14209 61747
-619093 -178071
230805 70097
-362539 -51108
42915 392
220666 2758
-13781 -4592
375796 92812
216006 17540
-538099 -122190
386927 102720
-472104 -138757
16391 32286
-30014 38293
-607335 -...

output:

3

result:

ok single line: '3'

Test #147:

score: 35
Accepted
time: 59ms
memory: 4672kb

input:

100000
65752 292312
141396 572924
-87851 -403805
-129675 -507073
-123980 -485609
-58941 -122992
-28217 104230
-35678 -112652
-172862 -569366
102295 415405
103653 423767
-25605 36182
-150799 -539100
-40833 -196543
-155703 -578857
115746 395672
38428 93037
20170 167443
141545 434652
-4269 -4726
124391...

output:

3

result:

ok single line: '3'

Test #148:

score: 35
Accepted
time: 52ms
memory: 4616kb

input:

100000
-579857 95257
-428127 246501
-163209 249161
-95893 18529
-311723 30173
223539 -27311
364483 -75215
127827 -8847
-387439 364965
280137 -68811
444639 -66983
-271199 -71259
479485 -121395
-252579 -18515
-224005 -9087
332201 20053
-446407 204469
-263139 -56755
-166321 293721
-114987 160253
172303...

output:

19904

result:

ok single line: '19904'

Test #149:

score: 35
Accepted
time: 51ms
memory: 4564kb

input:

100000
864934 -527993
65397 -175762
-210063 133578
-65813 103412
400966 -52537
701713 -368822
-736612 396589
8112 141761
208587 -53004
-131638 56747
-172624 185505
-155845 93540
-681695 449146
208627 -262372
-451866 219527
-223021 244764
156412 41101
-103533 10940
-516887 174690
248918 56983
49900 -...

output:

22112

result:

ok single line: '22112'

Test #150:

score: 35
Accepted
time: 52ms
memory: 4612kb

input:

100000
-599959 -558831
63145 -214920
207926 193303
-425770 -414475
-349375 -351808
19615 -217125
113019 -195175
-58950 -264859
203084 -75621
433237 258460
-369602 -229173
-435187 -183594
59835 82320
295193 281834
-254978 -62597
-313255 -339205
395186 56009
-98570 103604
-447554 -402103
-256529 -3352...

output:

16973

result:

ok single line: '16973'

Test #151:

score: 35
Accepted
time: 53ms
memory: 4684kb

input:

100000
-280628 -558135
36487 -391845
-301303 257415
-322743 284055
-150393 -256085
-3988 87545
-218968 -132095
-299423 -270785
-387788 249225
-149773 260395
100867 -439965
-429303 183575
19512 351905
311537 -136105
156957 -394225
75352 471505
324177 64295
241862 -207035
-27143 -448265
158797 -225985...

output:

15400

result:

ok single line: '15400'

Test #152:

score: 35
Accepted
time: 52ms
memory: 4620kb

input:

100000
-116853 -747565
12474 205560
84726 -432708
-166200 -110542
-6468 -314190
-42264 318788
300765 9745
89256 30178
-406362 -216726
-173448 -221060
260943 -146285
-166773 -337389
-193119 -7555
289749 63645
-116241 -196823
226626 304026
153819 693813
-192822 -209166
-159852 -372400
-116577 128301
5...

output:

18642

result:

ok single line: '18642'

Test #153:

score: 35
Accepted
time: 50ms
memory: 4604kb

input:

90902
12112 229449
-276736 220289
-760488 833757
380800 -640575
-588032 208001
-745228 806691
560304 -504903
-755264 -352415
-28152 -632427
22272 601217
550144 595841
-562716 346747
317648 612361
-146752 134625
76796 -885705
-755200 -558079
814096 148521
805764 54411
27648 -413439
-603020 -771101
-2...

output:

8

result:

ok single line: '8'

Test #154:

score: 35
Accepted
time: 53ms
memory: 4604kb

input:

90903
885590 293908
262012 119920
-408042 -765036
713150 381092
-681076 166416
224246 336980
-310802 -247420
606150 -236684
-813098 -143084
-253994 -380652
-775722 619796
8662 505108
-794666 -184044
310326 -386348
303574 -727788
728296 655976
-263950 -134420
-599874 726692
198742 802324
-668250 -170...

output:

16

result:

ok single line: '16'

Test #155:

score: 35
Accepted
time: 54ms
memory: 4568kb

input:

91666
-334933 377227
-588373 -579189
643179 -900981
-267447 193507
-777051 -269549
250548 -22209
-691429 558667
-689613 -246741
-232021 -816757
-93013 -338549
179649 -750269
-68437 -715381
-686677 444811
-765013 -663157
389803 -397941
211115 648587
640515 -92053
-879685 733899
-521941 -675957
627243...

output:

4

result:

ok single line: '4'

Test #156:

score: 35
Accepted
time: 50ms
memory: 4328kb

input:

87496
292426 470622
-744811 -784364
305431 -471417
-79454 311232
-538580 78555
-920801 656211
-119468 475824
178590 770420
-336062 166161
-573623 -134967
195674 548395
-213969 261374
-323939 -236193
-222572 267879
-472771 -858131
-372404 -418227
87811 253722
733948 -461184
628405 -645216
-678773 386...

output:

3

result:

ok single line: '3'

Test #157:

score: 35
Accepted
time: 53ms
memory: 4620kb

input:

90903
631735 513309
-569897 -328995
73455 854061
-607417 54013
-433553 350509
-531257 866301
487937 -394839
467527 -146179
520263 358653
559239 568445
285263 876397
-423609 399101
829255 760573
-291963 -302111
294601 476825
-172857 169981
-585753 -21571
-22611 339985
-244773 -551915
616007 -787203
1...

output:

16

result:

ok single line: '16'

Test #158:

score: 35
Accepted
time: 54ms
memory: 4572kb

input:

90904
-192406 123841
397522 -584047
755114 499265
371758 436297
392890 -715679
118378 40897
436554 445825
-545062 -74591
-3290 -598983
414674 -545647
835434 201153
-77974 332225
-132694 -436671
-72214 790209
-24726 369089
295914 457409
-589894 165473
733802 792513
867178 -218687
768618 -718911
28669...

output:

32

result:

ok single line: '32'

Test #159:

score: 35
Accepted
time: 46ms
memory: 4672kb

input:

91666
221605 463103
-607611 -832449
404901 -464641
-769832 -217439
-309787 818815
607093 -371489
293157 816639
-592999 -553225
-392555 272799
-499643 2751
-664795 -396801
40127 894651
335397 697343
636597 363615
192533 -105825
-603 -812801
-249179 -436481
282625 -526873
364597 654687
408129 452455
7...

output:

128

result:

ok single line: '128'

Test #160:

score: 35
Accepted
time: 52ms
memory: 4360kb

input:

87496
-658017 -74395
-415192 638800
804996 189602
-690090 196085
-122964 -201472
29718 -423757
-168327 -655336
-456084 -585424
-801792 668780
451521 -729766
547365 993818
-860841 -665290
-41982 -279763
8046 839528
721266 -16699
-12447 -40942
-129568 527713
-362772 -371827
615330 933029
-267813 71279...

output:

243

result:

ok single line: '243'

Test #161:

score: 35
Accepted
time: 53ms
memory: 4424kb

input:

87495
-345008 -637555
736328 102356
-862432 -297973
579422 -23221
503984 471689
104540 269630
515873 15929
-411181 465290
760286 -43093
73118 137969
725573 317303
-334069 -19252
665452 493862
280503 743429
497018 760616
327053 -86563
-792934 -478765
-10611 -219580
172262 -260065
249212 185840
-81844...

output:

81

result:

ok single line: '81'

Test #162:

score: 35
Accepted
time: 54ms
memory: 4488kb

input:

85712
624564 741663
110646 -561384
100035 -595890
39366 829791
-340749 839781
820800 527175
826686 495180
-810162 100062
304722 -589572
-472842 -265356
-356148 249399
521460 761724
-755886 670473
-65610 337716
-67770 -683208
-725274 559818
509814 -176958
90504 588654
-466839 643356
765288 892971
-47...

output:

27

result:

ok single line: '27'

Test #163:

score: 35
Accepted
time: 45ms
memory: 4360kb

input:

83332
-770502 -484669
-201693 -223579
368979 749663
562083 -440632
-714396 -428968
22866 738404
515274 570959
483837 446318
59856 -89119
-428331 -313408
47976 429389
536811 399419
-944031 -564562
-37641 695393
-877314 -67897
-240645 -201646
-825060 155807
-434352 -414118
-642387 469484
-788853 287
-...

output:

729

result:

ok single line: '729'

Test #164:

score: 35
Accepted
time: 48ms
memory: 4572kb

input:

90903
-469199 -750333
679729 -816893
-230711 -698033
-88363 401557
494769 -661565
608049 -412413
726481 232019
-614607 811267
-175631 -133533
-727759 439299
841033 -428401
-131839 -109845
-305935 90083
181761 -209045
-897103 162115
-709071 -849789
-28051 -917279
95025 -898301
-590735 -703581
236849 ...

output:

64

result:

ok single line: '64'

Test #165:

score: 35
Accepted
time: 53ms
memory: 4420kb

input:

85712
-156906 -659066
77832 485950
-718965 -626990
882045 -453080
765927 547375
219204 915295
655929 790429
175518 321439
87066 -684500
493200 57919
31905 -745331
-778104 624724
353394 -178898
-725148 574897
-603945 767722
159750 28561
-229347 318586
295236 -750569
-27144 855553
917640 -404159
-7277...

output:

27

result:

ok single line: '27'

Test #166:

score: 35
Accepted
time: 40ms
memory: 4312kb

input:

79998
513585 467582
-827046 782510
-444294 -225508
-328194 418793
-910881 869261
-800154 124385
815391 -343795
-138870 -795046
-335160 271616
269856 -680836
-255996 436478
-181719 85991
203031 384476
-219276 138020
618561 -146965
-829017 -611284
644643 70601
-828855 -452686
148086 596912
-390375 513...

output:

729

result:

ok single line: '729'

Test #167:

score: 35
Accepted
time: 51ms
memory: 4364kb

input:

83332
-539375 -347353
-420314 181343
-801104 409448
340429 -645334
-603545 -312991
345532 -263338
-418865 560837
749236 31340
558724 79697
774616 501923
-481154 -348631
-41729 168392
-424454 69977
-22208 -517435
-565151 -145807
833017 -601135
724207 329744
121567 116633
-199922 860213
604894 186617
...

output:

81

result:

ok single line: '81'

Test #168:

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

input:

3
-1000000 -1000000
-517284 1000000
1000000 -938753

output:

3970435093148

result:

ok single line: '3970435093148'

Test #169:

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

input:

3
480563 1000000
-1000000 -1000000
1000000 -591918

output:

3395808889834

result:

ok single line: '3395808889834'

Test #170:

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

input:

3
-1000000 -1000000
-51848 1000000
1000000 197781

output:

2864321549288

result:

ok single line: '2864321549288'