input_large.txt

1000
-853
2624
-3406
-3363
2345
-1139
1218
2294
-4420
3272
3342
2351
3033
-3984
2713
3834
-598
-4261
-1010
4287
-1598
1510
-2306
2283
100
-4531
-3822
3288
2216
-3595
2256
-1496
4137
-3829
513
-1085
-666
-2439
-632
4190
2766
-4456
1090
-2159
914
-2720
2617
-3600
877
-4189
-655
2978
-3646
-3932
1984
964
-3991
3701
-1036
2013
1294
-520
-1029
-4813
2494
-1888
172
802
-3994
3859
1375
4612
-2811
-2456
-4501
-4408
1384
-2902
4366
-2786
3692
4955
-3886
3474
-810
-2228
-1681
-3178
-323
2963
-2354
357
2111
-4898
-4172
763
-895
1453
-86
2401
2783
-4790
-2089
-1740
79
-3353
-2774
-4907
1105
4267
2311
258
-883
180
2951
-4056
3098
-4325
-846
1167
2901
-3551
3015
-527
-543
2039
642
-1453
-616
1070
3071
-488
-4252
959
-394
-4955
4091
-2866
2503
-2178
-1858
-4326
4951
723
2761
1324
-4901
4913
-3381
466
-254
3144
-2724
1344
-1574
-1065
4448
4906
-4911
-2259
4695
4372
1413
2100
-3836
3585
1415
2413
-2364
2522
795
-1355
1684
-3147
-974
1519
-3900
-583
-4265
-1876
-661
-4763
361
-2443
3694
14
2150
-4710
-3213
2919
-1315
2228
-612
4780
-25
1674
4275
-3575
1235
-435
-4055
-4340
-3463
4379
-1941
4182
-4983
-1273
-1207
-3277
4640
-2790
2910
2905
154
-1914
3247
-3683
1464
-2026
2026
720
1631
-271
-3249
-2545
3810
-2551
1726
1565
1849
-2873
2813
-3790
-2571
-251
3618
881
-3913
637
-4161
1376
-3946
-4061
2214
-902
-973
-3593
-1804
2610
1187
-1675
-2725
-3468
4411
1432
-4759
-1456
1685
-3470
1739
-1241
-1673
-4171
-339
2162
1722
-4814
-4598
956
1456
-4643
-3560
1635
3397
1306
-1217
4591
1199
565
2597
-4922
1098
-1349
754
-933
4248
-1568
-3571
-2619
-48
-2046
-2678
-3155
-576
-641
3096
1898
4600
-2186
-3051
-1742
-1918
-4198
1748
2004
2757
2618
-1322
-4629
-4209
-4057
-3811
-3063
-958
1567
878
4231
2260
-1461
2119
-4040
441
-4488
3717
425
-3474
-3825
-4390
-1031
-2903
-4243
942
1391
4774
-4083
-2895
-2499
-2731
-206
-3585
3655
-4296
4130
-971
476
-773
3617
2711
3633
2323
-2497
-979
571
1950
-1082
4652
3882
-209
4044
-565
-148
-1332
-4561
226
-508
4456
481
1193
2897
3674
406
862
2117
4047
-3966
2756
-1199
1501
1550
-4446
2570
-444
4733
-1060
785
1066
-2796
-1147
2169
-1623
349
-3627
-1983
-3095
9
2168
-3587
-4719
-3403
-2972
-2299
-2851
2433
-3576
-253
2426
-4649
199
-4640
-1902
4219
-1542
-60
-4767
1091
2785
-738
1696
3818
-3568
-1337
1115
-1948
-4888
-4443
2180
2974
2655
848
-3533
-2566
-2380
3406
-4088
-4605
-4659
4914
-1812
3435
-1474
2075
2515
-769
-136
-4007
4
4864
1492
3374
3609
2497
1452
3644
-4097
-3648
-4087
-119
4915
1443
-2222
-2959
189
-727
-497
-3870
-4892
-309
-3179
-1042
4022
4979
191
2568
283
4587
-3791
-388
1528
4786
-1025
-3286
3784
-2029
-248
-1133
2502
2027
3889
-53
4184
3602
1828
3587
-3728
4455
223
-449
-261
-3644
2784
-1903
2665
-798
4874
-485
-1554
4197
-3420
3448
16
4937
4592
-1509
-581
-4229
2495
-1039
99
-2604
2579
1284
-2710
-3641
-4864
4766
1580
766
179
4439
-3873
842
1013
4307
961
-4657
-4905
4842
2966
449
-3806
-4009
-3777
-920
4552
1557
-2127
-745
-613
3423
2309
1738
-1328
4771
-4718
-2396
-3958
-3535
1023
2623
1897
4112
-790
4070
2259
3497
-301
-70
4500
3893
2138
4055
-3632
1005
810
3337
-1847
2531
-3775
-3833
3006
631
977
2996
-2450
-660
1819
-4197
2450
-1173
-3465
635
3229
436
834
285
-2249
3338
-3665
3595
-4247
1433
-3165
4561
2896
1652
3610
-2708
4444
3998
2612
1768
-4660
-4415
4465
-192
-3014
-2639
3190
-4464
3199
-2021
-1842
-4109
4487
2666
412
4969
166
3872
4572
3504
-2248
2089
3696
4962
-2129
-2747
-4724
1657
2242
-1285
-4462
-2296
3922
-2936
-4638
-2660
-3000
4620
968
1177
-2390
422
4623
-454
3690
4156
-1519
-938
-4687
1595
-2481
-3217
4981
-4764
-827
545
3255
-1392
-1814
1577
1973
-1717
-3915
-2053
4619
-1836
3662
2244
2080
-606
-3132
1064
-3486
2538
370
-3519
1721
-4815
1493
-4968
847
3636
-3462
-3696
-1288
-2151
1887
-3424
-659
-298
1783
4148
-1489
-4164
-176
3306
-172
2955
3786
-2792
1215
-1731
-2201
1296
-3358
3842
1342
4303
-3416
1011
2429
3408
-4278
-1312
1186
4768
-107
-3460
2899
3153
4294
3739
-2374
-3323
-4148
1043
-409
-3196
4536
-3007
-776
-3849
744
3499
-1976
-1478
-4674
-2674
2894
2086
3879
-688
1332
4462
966
-44
3197
-3523
-4817
-843
1357
4228
87
-4062
1459
-4156
424
-4138
-980
1
-2460
1405
1102
-505
588
-2698
-3025
1291
1455
3792
392
-1441
-4695
1088
395
2811
-3395
-4329
3933
-3927
-3681
2414
-719
-2591
4540
3407
1424
485
-219
2096
-4658
-2726
-133
-2403
1881
-4015
-2633
-1126
3362
983
-3303
1123
-3255
2834
-786
1322
-1275
-244
3816
1050
-2659
-1331
3534
3210
2206
-492
-3975
-3269
-3224
2982
4810
4476
4167
1551
-4979
500
3177
-2319
1478
4440
-1953
554
-3186
1876
446
-4471
-3018
-4997
-88
-1163
1083
-4151
-1425
-4258
28
429
2334
-2312
-3752
-2025
1728
-4844
-2576
-504
-1945
-4336
-2958
-285
-3284
1775
-1439
-2157
-4842
604
3166
1625
1620
-4549
775
-340
-2564
1825
997
1972
-4339
3387
3915
3440
3163
4983
-2399
-3139
-2273
2416
-1579
2885
-4232
-1796
-1446
-1093
-3555
90
-555
1436
155
4566
-2601
2504
-3180
1211
-1205
-2242
235
2225
4001
1003
860
-4648
-360
4385
1572
-1989
2843
-2372
2781
-2535
2823
-4782
4072
4902
3468
-3904
3992
-1120
-351
3892
-2473
-1986
-2922
-4768
814
-692
-712
-3934
4014
1516
-3914
2789
2034
-227
-2904
-4760
3901
-1911
2053
3295
2261
-2100
4725
2839
2227
3543
71
-4977
-3167
-2665
4565
-1308
583
-667
-3356
-1824
791
138
1355
2549
3109
-2620
883
4373
3866
-1610
-1289
-2530
697
-511
3528
-4188
-2888
1084
4980
-3054
1818
3758
-272
-1522
1683
-1853