#1853. 分道扬镳

    ID: 1853 传统题 1000ms 256MiB 尝试: 0 已通过: 0 难度: NOI/NOI+/CTS 上传者: 标签>CTT赛事:contest1816来源:qoj.ac数据:公开样例动态规划

分道扬镳

分道扬镳

题目描述

标题: 分道扬镳 - Problem - QOJ.ac

#9517. 分道扬镳

Statistics

The problem was used in the following contests:

悲伤的故事

由于现场出现了预料之外的做法。

因此现在是经过修改后的范围和数据,集训队互测现场的情况并没有参考价值。

如果你觉得你的做法空间正确且获得了 MLE,请尝试替换引用的头文件。

题目背景

Mayflower - Plum

五月和七月收拾好自己的东西,分别踏上了属于自己的路……

题目描述

请注意本题不常规的空间限制。

给定 n 个物品,体积依次为 v1,v2,…,vn,价值依次为 w1,w2,…,wn。

你需要从中选择一些物品,保证体积和不超过 m。你将会带走你选择的物品,你的收益是这些物品的价值和。输出你的收益的最大值。

特别地,有一个每次给定的系数 k,数据保证如下性质:

  • 如果你可以先选定一个元素都在 (0,1] 之间的实数序列 p1,p2,…,pn。并对于所有物品,第 i 个物品的体积和价值同时乘以 pi,即体积变为 pivi,价值变为 piwi。然后你再进行选择物品,那么你的收益最多为 r。
  • 在原问题中,假设你的收益最多为 l,则有 r−l≤k。

输入格式

第一行三个正整数 n,m,k。

接下来 n 行,第 i 行两个正整数 vi,wi。

输出格式

一行一个数,表示答案。

样例 0

样例 0 输入

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

样例 0 输出

33

附加样例 1~7

见附件下载中的 ex_mayflower1~7.in 与 ex_mayflower1~7.out。

附加样例依次满足本题的 7 个子任务的限制。

样例解释

在题面中给定的样例中,r 可以通过如下方式计算:

  • 令 p=[1,89,1,1,1,1,1,1],即对于第 2 个物品,将其体积变为 8,价值变为 649,其他物品不变。然后选取第 2,4,5,6,7 这五个物品。此时总体积为 8+2+6+3+1=20,总价值为 r=649+5+8+8+9=3349。可以证明找不出更大的 r。

而 l 可以通过如下方式计算:

  • 选取第 2,5,6,7 这四个物品。此时总体积为 9+6+3+1=19,总价值为 l=8+8+8+9=33。可以证明找不出更大的 l。

最终我们有 r−l=379,又有 k=6,满足 r−l≤k。

数据范围

对于所有数据,保证 1≤n≤104,1≤m≤109,1≤k≤20,1≤vi≤5000,1≤wi≤1012。

子任务编号 n≤ m≤ k≤ vi≤ wi≤ 数据随机 分值 1 1000 105 20 1000 1012 否 5 2 1000 109 20 1000 1012 否 5 3 104 109 20 333 333 否 10 4 104 109 1 2000 1012 否 20 5 104 109 5 2000 2000 是 15 6 104 109 20 2000 2000 是 15 7 104 109 20 5000 1012 否 30

数据随机:对于每组数据,给定 n,m,k 后,在满足 r−l≤k 的所有的数据中等概率随机选一组。

输入格式

(见题面原文)

输出格式

(见题面原文)

数据范围

(见题面原文)

样例

样例 1

1000 100000 20
272 662
586 35
723 738
862 854
879 250
573 714
751 547
169 664
879 919
313 100
168 348
425 557
928 213
47 633
736 103
383 534
508 133
496 162
839 653
613 549
940 401
670 394
718 319
716 689
769 434
336 1000
214 630
292 573
795 215
936 118
785 243
7 561
132 627
399 700
503 295
581 758
581 231
591 748
561 106
568 245
591 859
647 95
368 71
728 536
466 856
745 245
694 573
534 486
353 112
423 552
859 958
949 490
379 115
408 560
712 219
491 251
657 706
54 687
135 805
988 940
742 983
347 54
720 389
110 445
529 738
310 62
924 4
941 959
996 533
489 623
60 835
519 476
552 560
478 459
42 522
776 819
286 188
212 210
357 772
359 143
934 187
190 502
673 280
861 319
402 181
235 464
20 880
116 542
99 660
582 16
825 453
124 220
666 696
302 368
759 112
415 514
623 954
734 368
90 146
813 122
588 980
285 131
952 132
304 843
322 486
702 656
644 711
857 480
394 377
688 328
294 531
176 224
316 687
6 981
727 483
110 406
875 112
760 24
928 782
133 282
710 142
350 729
603 318
814 517
718 449
531 530
384 741
353 753
942 899
902 12
65 122
303 925
933 587
914 640
333 422
618 868
765 957
687 406
607 628
203 285
311 455
13 607
183 244
314 579
84 604
767 789
270 399
328 558
516 917
685 457
14 61
408 799
681 90
544 244
151 768
64 639
604 196
240 110
402 746
803 328
126 668
368 761
393 98
362 689
535 740
144 445
851 338
869 885
473 341
569 917
827 139
470 580
45 870
619 567
545 486
981 7
292 379
569 439
959 403
940 943
743 570
571 660
229 701
963 741
294 582
530 359
940 899
140 331
283 79
215 211
853 312
775 136
535 135
627 391
977 867
470 487
546 518
151 340
682 374
121 72
303 598
444 405
392 778
546 619
253 895
907 600
685 368
577 612
894 842
948 673
624 201
176 81
274 24
394 79
668 718
207 940
556 275
469 980
129 599
160 735
427 692
758 424
369 975
163 881
865 723
542 877
59 117
258 77
494 449
30 348
10 564
302 411
293 120
800 566
607 763
871 244
829 216
395 771
657 332
710 393
224 258
793 164
755 680
349 164
671 704
739 675
37 992
549 20
602 274
666 457
824 317
734 28
187 338
439 7
70 527
849 675
196 295
163 797
206 625
424 692
307 733
767 749
795 810
612 399
852 379
508 456
814 260
21 694
758 458
516 694
126 225
404 928
363 475
158 904
366 336
275 503
452 496
756 265
510 539
803 413
818 945
319 800
280 91
772 578
293 936
57 471
667 944
736 935
687 397
857 798
930 37
607 253
313 666
513 551
142 802
563 581
828 799
282 339
30 207
100 968
208 445
270 698
509 814
43 440
40 965
708 774
427 104
331 196
507 569
446 647
249 903
274 719
778 722
446 47
112 978
308 81
112 128
947 375
754 962
855 867
396 620
711 32
543 498
103 798
1000 72
716 642
353 914
714 683
317 324
993 631
247 890
716 468
372 113
913 335
28 261
83 176
837 873
611 492
328 962
627 226
226 844
218 559
917 571
867 442
76 547
805 832
234 122
948 321
292 248
399 49
554 150
304 712
738 996
87 442
229 353
111 720
496 958
768 614
565 715
851 643
559 689
881 748
145 175
821 160
184 222
717 125
324 141
781 10
156 477
379 275
335 925
556 473
227 87
662 343
401 49
828 854
199 446
806 665
181 11
734 90
873 66
675 963
875 370
354 838
865 796
984 334
28 800
857 180
929 686
92 731
922 38
469 523
186 48
754 322
565 669
391 294
949 324
426 948
390 845
303 613
595 802
605 251
278 617
830 105
868 844
547 480
47 584
590 35
698 361
839 988
721 309
448 964
30 133
841 335
629 807
492 269
913 150
961 699
284 32
180 368
107 655
490 960
848 697
504 469
839 600
92 409
377 211
522 284
28 691
376 68
56 655
50 792
699 120
735 245
111 902
554 169
159 793
946 795
445 736
626 297
679 206
793 279
285 680
236 55
293 808
999 36
256 797
608 190
2 313
524 617
437 505
992 581
798 433
361 927
447 686
284 39
700 385
647 785
414 323
798 124
627 371
719 533
75 434
6 565
773 928
42 583
584 771
614 11
706 175
561 190
989 193
742 168
557 899
397 52
683 284
736 507
341 765
575 281
635 636
868 575
908 85
392 215
399 532
580 116
282 332
297 855
711 963
497 890
866 971
179 810
212 643
323 445
355 636
119 816
776 765
699 843
487 272
718 266
842 2
915 998
751 71
337 330
797 155
259 304
35 914
905 753
522 289
589 800
742 450
687 496
32 348
882 65
503 993
84 119
498 127
58 979
439 600
138 224
168 249
655 647
33 870
816 188
331 365
49 990
684 526
608 699
941 210
9 249
434 9
115 534
142 530
505 250
108 311
202 288
911 46
58 881
883 937
855 664
457 127
572 774
695 609
721 480
878 902
761 708
643 703
450 200
286 635
305 963
925 932
195 10
986 929
709 172
497 714
782 791
244 719
696 401
431 290
882 271
475 616
496 25
527 651
345 68
194 771
792 695
595 560
573 734
442 690
161 778
780 298
757 95
866 542
315 173
314 96
283 832
437 400
328 408
879 190
433 98
779 185
720 252
796 474
622 333
701 657
869 163
466 759
621 211
397 451
360 28
746 462
269 924
203 214
304 586
20 902
921 378
160 461
169 549
986 715
360 6
557 735
914 797
13 235
653 560
204 542
524 693
670 25
511 706
101 995
41 846
965 157
201 108
849 855
409 639
877 393
314 905
145 827
6 642
964 301
261 320
719 175
177 633
766 459
49 570
787 918
625 555
339 27
57 721
894 439
722 99
339 614
260 62
642 621
251 945
568 918
293 929
215 631
101 334
611 995
4 269
414 639
2 364
76 246
257 984
480 62
123 682
326 889
167 270
358 405
592 499
488 524
542 502
330 5
291 262
683 481
214 97
956 127
260 558
794 368
322 657
262 555
268 603
460 530
274 559
695 388
869 822
44 41
518 332
762 785
560 641
696 205
729 408
799 828
717 195
436 1000
931 261
64 798
62 742
472 290
13 963
908 600
635 92
436 852
247 421
478 283
614 677
346 792
556 505
335 312
95 194
610 214
740 515
950 160
479 532
159 256
520 578
174 91
481 948
880 990
713 479
47 28
571 460
87 217
640 525
682 874
465 915
357 571
182 867
345 288
17 660
187 956
571 946
532 565
567 863
977 317
546 725
364 579
818 908
865 552
515 378
762 299
403 343
148 653
607 901
296 678
988 678
234 710
391 45
189 660
821 523
686 587
676 748
901 192
752 768
895 765
47 570
14 434
365 356
335 838
433 433
923 714
598 434
607 63
643 58
924 18
812 538
535 663
846 942
42 699
911 13
273 481
675 805
390 414
856 204
230 86
331 72
418 756
625 817
559 533
232 706
142 846
386 259
156 346
913 729
467 173
725 645
896 59
72 753
787 146
155 822
290 75
622 201
878 389
316 361
60 226
916 667
397 273
937 478
958 738
707 120
273 29
260 687
331 475
300 32
452 523
142 515
562 719
641 292
430 804
719 724
716 590
17 943
136 769
233 644
492 97
206 432
771 499
684 699
58 570
697 57
945 483
777 178
262 961
660 778
194 673
763 914
522 751
958 317
967 928
864 140
174 182
297 627
609 991
243 257
829 990
558 324
538 473
749 827
718 953
807 258
34 949
774 593
3 935
291 437
226 437
736 566
829 761
748 959
572 890
795 722
444 449
812 121
40 821
17 902
691 87
226 780
295 951
570 507
457 765
449 560
314 408
608 834
807 67
728 151
50 315
547 789
144 146
529 1
249 839
965 123
627 100
782 848
511 775
399 79
579 785
486 501
814 450
336 401
38 867
772 104
949 26
532 114
560 490
415 811
527 760
410 67
952 519
130 878
749 149
483 245
945 924
60 628
870 954
873 738
882 321
992 212
53 632
980 769
132 32
262 679
490 895
446 309
242 864
86 167
94 170
816 862
67 613
563 61
266 584
778 901
601 941
188 161
776 115
981 795
245 243
100 694
280 884
595 337
551 256
971 274
683 28
253 385
978 60
953 745
555 340
203 362
477 712
993 50
528 293
150 223
874 366
123 934
331 944
817 616
993 454
687 823
269 773
338 870
893 721
584 846
352 383
708 994
749 697
942 228
500 37
680 973
43 438
361 225
42 985
886 80
135 450
332 895
635 549
384 245
740 629
927 14
881 264
454 796
497 952
107 321
524 916
873 869
464 453
633 214
285 129
556 355
682 748
41 433
62 130
413 734
791 214
102 17
871 983
400 304
769 533
936 671
977 520
19 440
257 442
920 758
421 56
138 753
656 964
335 581
156 726
299 802
759 590
406 741
424 556
386 854
254 273
94 273
673 459
349 69
375 629
760 743
361 564
608 400
147 923
397 891
495 32
994 264
931 309
310 300
742 880
596 695
759 651
644 260
902 836
304 292
833 854
536 747
129 295
230 162
778 48
619 835
222 80
960 593
563 497
78 669
400 385
630 930
255543

样例 2

1000 1000000000 20
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000 1000000000000
1000000000000000