Deadlines
Statement
You are at work, and your boss gives you [[N]] tasks which you must complete, labelled from 1 to [[N]]. Furthermore, each of the tasks has a deadline; the [[ith]] task takes [[ti]] minutes to complete, and has a deadline of [[di]] minutes after work begins. Unfortunately, your multitasking skills aren't quite up to scratch, so you can only work on a single task at a time.
Your boss wishes to reward you when you finish a task before its deadline, and punish you when you finish a task after its deadline. He has therefore devised the following scheme:
For each task, if it was completed [[si]] minutes after work begins, then you will earn [[ti]] - [[si]] dollars. Note that all tasks must be completed, even if they earn you negative money (i.e., cost you money). Your total profit is the sum of the money earnt from each task.
Given that you can choose the order in which you complete tasks, what is the maximum amount of money you can earn?
Example:
Let [[N]] = 3, [[t]] = [4, 2, 3], [[d]] = [5, 7, 9].
The optimal order is to complete the second task first, then the third task, then the first task.
Then the completion time (the sequence [[s]]) is [2+3+4, 2, 2+3] = [9, 2, 5]
and the total profit is (5-9) + (7-2) + (9-5) = 5.
Input description
<<Line 1:>> [[N]], the number of tasks you must complete.
<<Line 2:>> [[N]] space-separated integers, corresponding to the sequence [[t]], the amount of time each tasks takes.
<<Line 3:>> [[N]] space-separated integers, corresponding to the sequence [[d]], the deadlines of each task.
Output description
A single line containing the maximum profit you can earn.
Constraints
1 ≤ [[N]] ≤ 1000
1 ≤ [[ti]] ≤ 1000
1 ≤ [[di]] ≤ 1000000
The answer is guaranteed to fit into a 32-bit integer.
Game modes
Test cases
Small Case Test
Input
3
4 2 3
5 7 9
Output
5
Small Case Validator
Input
4
1 2 4 5
5 9 2 10
Output
3
Negative Profit Test
Input
10
835 492 574 116 422 596 149 667 220 546
435 763 929 173 544 397 628 654 732 152
Output
-13743
Negative Profit Validator
Input
10
2 70 269 125 455 381 242 910 485 410
778 886 392 715 655 932 181 360 627 553
Output
-5669
Many Tasks Test
Input
1000
5 9 2 9 5 8 6 7 5 1 8 7 9 2 8 8 10 2 7 3 6 6 1 7 4 10 2 3 4 3 5 6 2 7 2 6 6 4 3 10 7 10 10 9 8 7 1 2 10 8 5 5 6 9 10 4 8 4 3 7 9 5 8 8 6 10 3 2 1 6 8 10 9 9 10 7 5 8 9 7 4 8 5 6 10 10 10 3 2 4 4 8 10 10 7 7 10 5 10 4 9 9 7 7 3 4 7 3 9 5 9 2 1 8 5 4 10 3 7 6 6 2 9 6 5 6 1 7 8 8 4 5 9 4 10 5 4 5 8 7 1 2 8 7 10 6 9 6 9 3 5 3 10 1 5 7 8 9 1 3 5 5 3 5 1 6 8 6 9 1 3 6 5 7 9 3 2 6 6 4 9 9 1 1 1 6 7 2 2 6 7 1 5 8 9 4 10 3 8 1 10 1 10 10 3 4 1 7 10 3 6 7 6 10 6 1 1 1 8 4 6 5 6 3 3 4 1 7 10 3 8 2 7 1 8 10 7 2 10 5 4 1 6 8 2 7 7 10 2 2 5 3 4 2 6 8 4 6 3 3 8 4 2 10 9 6 2 4 7 3 10 5 8 10 2 3 2 3 8 6 8 3 6 1 5 8 3 3 5 7 9 8 3 2 2 3 3 5 10 7 7 2 5 3 7 10 8 2 9 1 1 6 10 2 9 9 7 5 10 6 6 8 5 10 5 4 5 7 7 10 9 1 4 4 2 3 2 10 3 5 9 9 4 5 8 2 2 10 1 1 1 9 10 5 6 9 8 9 10 7 5 7 5 10 5 2 7 6 8 7 2 8 1 7 6 8 8 5 7 2 7 10 9 7 1 8 10 6 7 4 6 9 7 5 2 1 5 7 1 1 9 6 5 8 10 3 8 7 2 5 8 7 5 1 7 7 5 6 4 8 10 8 8 2 6 9 3 8 2 7 2 7 2 8 5 4 3 9 7 1 2 4 1 7 7 9 6 10 1 2 2 1 3 6 3 8 8 2 1 10 6 2 3 4 3 5 9 5 3 7 4 1 2 2 8 8 3 8 9 1 2 5 9 9 10 8 8 5 4 8 2 8 10 6 1 9 1 7 3 7 1 3 6 3 6 2 7 6 10 8 3 1 5 7 5 4 3 1 8 10 10 3 2 8 9 1 9 3 9 9 4 6 3 2 7 6 10 8 8 6 8 6 2 2 7 7 9 8 1 10 1 10 8 4 3 9 6 5 10 9 10 5 9 2 9 2 7 1 3 4 7 1 9 6 5 5 9 7 8 10 4 4 3 6 2 10 6 6 4 4 10 4 2 7 9 5 7 5 7 2 6 1 5 3 3 7 1 7 4 10 1 6 5 6 8 3 5 5 7 9 1 10 7 1 3 7 8 2 3 3 3 10 4 6 2 5 9 5 1 2 5 7 2 3 2 5 8 8 1 8 9 9 2 9 7 3 4 9 9 7 3 3 3 9 4 6 4 10 3 7 8 1 8 3 9 3 2 7 2 8 8 5 4 1 9 7 2 4 6 4 9 10 1 10 7 5 4 4 9 9 3 9 1 3 7 2 9 8 6 2 7 2 6 8 1 7 1 10 8 8 9 8 7 6 8 6 1 5 5 4 4 5 7 9 7 2 7 5 10 5 3 1 9 7 1 5 7 7 8 1 1 4 8 5 6 10 1 1 6 3 2 3 5 4 6 7 8 3 5 8 1 10 2 2 4 9 2 10 4 2 4 8 3 1 10 3 1 3 7 3 6 4 2 6 5 7 9 3 8 10 3 10 9 1 1 10 5 1 5 10 4 2 6 5 1 4 7 5 10 4 8 4 8 2 3 7 10 10 3 2 5 10 2 6 2 3 6 10 10 2 9 10 10 10 9 5 4 8 3 4 7 9 3 5 5 8 10 7 6 6 5 3 3 6 5 4 5 2 9 1 8 6 5 4 2 3 5 6 10 10 3 1 7 7 4 7 10 1 2 6 10 1 7 5 3 10 7 6 2 7 2 5 9 7 2 3 7 5 8 3 3 8 8 3 1 3 6 6 4 8 7 9 9 2 10 10 8 5 1 8 3 8 6 6 5 7 8 1 8 6 3 8 7 1 2 1 6 4 5 3 1 1 9 3 2 9 2 9 3 2 3 7 7 3 10 7 10 5 10 7 5 9 10 1 10 6 10 4 7 8 4 1 8 2 6 2 5 1 5 10 1 5 6 8 7 2 10 9 9 1
471 786 785 787 394 25 709 791 514 657 462 790 605 590 791 49 899 214 572 781 873 791 255 290 643 330 612 607 941 272 904 464 107 552 480 860 38 575 449 775 252 474 93 384 472 251 720 962 354 195 884 409 675 109 199 402 752 503 863 485 72 749 276 106 482 42 667 224 581 811 99 196 569 239 566 929 819 352 600 920 441 75 107 322 828 332 368 703 53 162 934 207 749 554 173 34 309 581 800 450 25 498 849 730 135 811 418 910 894 808 672 459 401 173 424 308 559 859 54 557 38 215 798 502 959 887 829 770 682 143 24 158 401 1000 376 314 497 468 517 605 402 143 34 747 643 680 660 329 124 336 290 52 782 817 419 697 573 150 346 210 748 968 761 567 458 989 930 771 658 354 594 16 797 362 35 139 215 401 53 779 470 902 755 353 637 9 654 783 936 350 151 21 674 311 200 485 205 704 689 860 508 91 482 491 404 774 890 612 193 639 160 44 163 844 108 567 189 980 145 672 429 706 295 46 287 838 379 564 535 37 88 660 657 637 167 184 897 762 982 527 892 487 860 268 20 651 205 111 645 691 971 2 889 1 522 779 640 78 501 71 333 52 646 264 664 86 522 965 866 172 336 511 862 306 503 171 548 294 159 170 134 829 186 262 409 6 18 236 597 365 215 280 35 779 765 71 345 134 763 314 49 226 1000 637 102 446 3 171 894 458 774 683 896 889 416 218 440 369 662 402 728 332 531 319 745 880 560 284 492 177 201 507 80 283 309 867 781 801 205 319 429 121 569 150 224 972 597 253 896 878 774 115 377 11 436 492 296 207 906 430 623 244 60 350 195 614 948 56 984 712 310 450 553 921 256 650 445 245 756 5 583 600 736 873 487 510 213 147 387 257 820 639 720 521 1000 762 318 488 130 646 152 884 397 791 753 908 745 327 103 534 230 120 508 922 421 570 215 364 499 338 266 369 191 199 2 602 6 113 661 264 330 907 715 637 203 144 271 460 269 136 268 290 126 86 145 25 598 313 599 467 297 170 227 443 50 216 514 261 94 6 113 635 180 608 921 908 4 4 706 774 918 332 197 369 774 861 263 497 828 810 405 875 859 87 341 560 448 281 684 375 456 830 843 788 488 431 642 714 696 600 712 212 550 447 615 611 473 578 45 617 771 830 160 111 102 181 123 776 869 354 49 210 157 308 207 526 118 526 738 644 659 66 767 172 333 941 174 82 87 541 973 175 183 985 940 604 887 595 230 964 432 723 291 343 680 254 845 961 255 510 191 888 561 601 299 419 906 14 911 116 328 847 217 15 657 629 995 63 523 117 288 551 133 706 311 163 298 697 129 172 858 278 686 103 665 854 820 667 840 245 995 856 975 489 561 823 818 656 696 741 770 480 943 821 804 391 218 58 20 465 412 289 824 432 822 393 777 46 981 701 442 402 461 986 80 487 34 174 60 140 848 78 129 662 758 391 826 373 713 42 367 681 276 681 337 212 772 644 473 486 977 869 686 471 748 340 633 50 55 664 568 320 546 235 969 678 873 436 426 509 754 441 396 676 903 654 444 713 582 185 416 424 660 10 727 998 569 320 602 411 703 820 439 170 497 971 571 876 515 438 211 785 455 228 885 683 496 604 719 857 933 30 600 914 351 391 266 793 175 587 541 415 357 414 70 770 11 519 309 96 701 580 814 62 623 522 894 381 357 166 475 901 576 513 848 697 701 896 811 335 993 786 302 421 633 842 230 323 247 97 73 818 380 549 517 163 803 111 268 68 944 743 116 577 58 835 740 813 819 554 812 779 706 980 924 655 321 710 775 798 282 158 445 51 824 2 185 216 858 776 453 91 93 842 570 153 558 656 719 292 742 589 183 917 793 70 371 998 618 472 662 41 564 174 782 224 394 182 273 481 514 489 59 644 378 970 837 10 408 179 914 197 910 580 971 512 308 636 287 205 229 269 396 584 557 338 782 387 890 13 351 984 439 799 987 415 869 672 656 2 162 735 934 475 692 616 574 671 466 33 437 18 495 568 923 70 949 376 833 704 21 623 381 332 549 62 454 179 446 169 942 231 765 815 771 844 186 955 726 484 940 854 290 333 819 438 470 1000 109 905 159 859 754 849 728 331 873 985 419 535 357 56 874 52 548 756 128 258 379 826 87 438 87 27 91 264 469 409 382 345 266 631 891 803 180 86 950 553 706 61 255 994 207 91 636 892 54 463 205 409 345 578 5 530 609 634 193 483 745 83 1000 209 173 916 232 156 957 540 436 256
Output
-1472990
Many Tasks Validator
Input
1000
4 3 8 2 1 1 4 4 7 8 9 10 3 5 4 5 6 10 3 1 2 6 7 9 5 3 3 4 1 4 4 7 7 1 3 7 2 1 3 9 3 6 4 5 5 2 2 5 1 10 10 3 8 5 6 8 7 9 10 9 7 7 3 5 4 7 9 6 2 5 3 3 8 8 6 10 8 1 10 2 10 8 2 8 4 8 7 2 5 10 9 5 4 1 8 7 5 1 1 9 2 3 9 6 4 5 7 10 5 3 6 10 9 8 5 1 5 3 10 3 3 1 3 3 1 8 5 4 3 3 6 2 4 5 9 7 7 9 2 2 4 3 8 6 3 6 5 2 10 10 9 9 8 3 4 9 1 10 3 10 8 10 1 5 5 4 4 2 9 10 2 9 7 3 10 2 10 4 6 2 5 5 3 8 2 4 9 6 7 9 1 7 10 9 9 6 8 8 3 4 3 6 2 5 5 5 8 9 3 5 8 4 7 1 7 6 7 1 8 4 4 4 6 5 5 5 1 7 2 7 9 6 8 9 7 5 7 7 9 1 4 10 2 5 5 7 5 1 8 8 9 2 5 7 2 5 10 2 10 4 1 5 3 2 3 8 9 4 9 6 3 4 6 2 6 8 1 6 6 5 7 8 8 4 8 9 7 3 4 10 3 2 5 9 8 2 3 8 4 8 8 10 3 5 3 6 10 9 7 2 4 6 5 9 3 5 9 1 10 9 10 3 6 3 4 4 9 10 1 10 2 10 4 10 8 2 3 5 4 3 3 2 7 10 9 10 10 10 10 1 9 1 4 4 4 2 10 9 6 2 1 7 4 2 4 2 8 6 9 10 1 2 5 7 1 8 5 8 10 3 6 7 7 10 6 6 8 3 2 1 5 3 2 8 2 7 6 4 3 7 6 3 10 5 1 1 10 6 2 5 4 2 3 5 10 7 10 8 2 6 2 5 1 10 9 5 10 7 2 9 7 5 8 3 5 1 7 3 3 7 8 9 6 3 6 10 8 8 3 1 5 4 2 4 5 6 1 7 4 8 1 3 6 2 4 7 7 3 2 1 10 8 9 10 4 5 3 5 10 10 10 10 6 7 3 9 2 10 2 4 5 2 9 10 10 6 4 4 3 3 5 10 7 10 2 9 1 8 6 6 8 3 10 3 1 8 2 8 1 8 8 10 5 6 8 4 8 5 8 10 9 7 1 3 8 3 3 9 9 7 10 10 9 3 6 3 6 1 5 1 5 6 2 7 5 5 4 4 2 5 7 1 7 4 2 10 9 4 1 2 7 7 4 4 5 9 7 7 10 4 2 5 8 5 5 10 4 8 9 10 6 9 2 2 9 2 9 6 10 9 8 4 5 8 10 2 5 6 8 3 6 1 6 8 2 8 4 6 7 7 3 3 4 8 5 7 2 4 6 7 1 3 8 5 6 1 9 9 5 9 1 9 9 5 7 3 4 2 4 7 5 9 2 2 9 8 4 1 7 5 4 8 7 9 7 6 10 2 9 10 1 8 5 4 7 7 3 3 5 8 2 4 3 3 6 7 8 6 7 1 3 1 6 1 10 6 8 2 6 3 3 10 3 9 7 8 1 4 8 7 4 8 9 4 6 3 10 3 2 8 1 1 4 7 8 1 9 10 5 4 8 3 6 7 2 7 5 1 7 1 3 8 9 8 1 5 5 4 8 10 4 2 6 6 3 6 7 8 1 3 5 3 1 2 4 1 10 8 5 7 6 7 2 3 5 4 4 7 3 5 1 9 1 3 5 2 3 8 9 6 8 8 1 4 9 5 7 10 9 2 6 1 4 3 8 3 8 6 4 8 1 2 6 3 6 3 4 1 5 9 6 3 7 3 9 9 3 5 4 10 10 8 6 10 6 5 6 3 8 2 4 8 8 2 1 5 7 2 10 2 9 5 5 10 1 1 10 1 10 2 2 8 6 3 2 8 2 3 7 3 10 1 5 7 1 1 10 4 7 9 10 2 3 3 1 2 6 10 3 2 5 3 9 8 2 1 2 6 2 9 1 4 10 4 5 3 1 6 6 9 1 5 4 1 4 9 5 6 8 9 9 1 4 1 8 6 10 9 6 8 1 2 9 5 2 10 5 10 5 5 7 8 3 1 4 5 10 3 5 8 7 3 10 3 9 10 6 6 6 10 6 10 10 8 8 2 5 9 2 6 5 2 2 9 9 10 9 2 2 9 2 2 3 8 3 5 9 7 3 8 7 5 5 8 10 10 4 7 5 8
52 513 328 194 64 416 435 814 354 402 122 853 84 431 53 862 470 1000 952 879 563 378 515 400 712 193 208 532 643 612 606 519 419 590 499 90 846 228 876 609 189 258 650 759 133 979 274 828 649 162 220 212 606 558 251 66 354 366 590 271 484 179 172 609 796 928 613 322 669 186 674 639 698 278 28 726 987 708 57 715 507 151 838 668 772 470 784 779 292 503 833 546 994 779 275 277 763 680 863 435 907 800 159 380 828 344 420 666 467 827 82 332 672 134 417 125 301 268 953 315 109 221 813 47 846 394 179 335 413 270 529 879 944 852 996 599 156 322 402 604 419 44 954 410 615 941 476 464 927 846 805 687 684 271 972 186 535 39 402 304 714 419 596 263 869 220 604 562 91 51 222 514 605 398 681 451 502 829 172 53 707 175 173 723 808 398 493 537 728 674 14 40 318 667 780 497 147 449 348 745 267 354 720 481 406 696 584 10 172 642 169 116 396 4 106 582 607 899 885 325 1 559 135 349 821 854 308 144 674 151 97 453 879 777 815 667 578 28 488 941 234 731 256 413 488 51 462 941 661 308 416 383 435 793 696 883 251 612 670 822 776 574 611 799 209 463 869 642 390 572 495 900 174 560 391 560 197 597 144 756 951 916 507 965 230 168 368 209 218 899 777 475 338 142 791 20 45 308 426 733 47 208 838 910 174 677 708 599 147 431 488 319 498 929 743 320 954 928 252 200 753 90 277 555 316 868 212 875 911 256 531 205 668 298 197 289 615 461 856 730 707 367 982 314 155 639 489 344 347 881 12 234 366 271 461 713 995 300 940 682 67 661 654 432 832 362 413 812 523 887 973 935 621 9 156 617 97 766 751 699 403 28 101 915 670 543 140 476 907 435 238 135 918 457 662 421 51 850 728 990 243 543 145 459 199 474 610 260 530 272 752 196 921 570 607 448 110 823 985 477 271 364 617 226 117 304 143 190 239 549 922 569 775 44 613 513 214 723 100 406 473 852 180 15 840 928 580 818 295 974 14 298 734 63 140 716 203 191 530 597 643 552 958 662 426 88 236 690 144 258 314 654 913 335 46 250 196 903 672 905 516 7 434 441 98 62 502 451 731 308 678 875 39 898 274 607 509 347 808 611 941 478 851 379 917 654 276 485 661 296 433 783 276 962 472 586 483 921 854 174 281 854 778 247 979 284 945 342 14 690 330 371 204 679 314 378 888 433 180 964 27 217 375 17 487 591 967 693 378 14 592 685 161 50 615 966 793 375 154 739 327 751 210 215 96 265 244 117 501 934 585 594 92 26 560 907 167 654 748 114 310 771 893 105 634 935 442 224 810 661 663 950 130 325 307 731 981 331 663 438 210 980 381 708 600 652 479 561 963 494 649 310 478 366 109 425 590 91 64 629 633 520 711 961 407 380 30 243 146 397 929 588 893 485 366 465 361 415 459 568 53 44 491 66 980 37 993 531 999 535 452 419 774 150 876 892 48 434 815 19 671 396 307 76 967 72 244 894 990 213 990 61 527 283 324 592 626 810 291 20 93 215 914 364 624 46 483 470 432 729 853 200 45 971 979 810 842 467 191 85 77 478 899 780 96 921 186 664 299 153 374 495 727 258 463 62 781 675 188 779 216 42 946 322 864 488 682 627 836 282 182 98 992 579 324 327 504 299 782 641 447 204 394 850 632 204 279 52 945 246 770 122 391 583 463 997 326 588 212 57 84 974 923 192 949 756 191 147 421 437 410 876 25 908 55 434 726 453 721 882 884 523 494 200 308 771 774 557 327 634 436 326 849 416 157 240 299 663 41 806 740 928 896 562 513 270 112 203 904 913 312 711 729 181 734 166 33 635 529 68 497 909 239 31 540 821 706 47 637 575 392 578 114 184 241 847 791 13 908 790 335 292 776 970 107 991 12 937 272 167 822 523 924 348 42 296 882 457 284 78 19 649 333 801 168 697 380 352 273 65 375 151 580 75 923 361 413 189 326 596 613 88 674 5 167 83 122 848 670 821 46 298 821 204 648 247 289 311 136 601 89 960 632 548 846 141 977 630 620 316 907 109 517 295 470 765 712 22 265 385 6 18 641 976 615 203 965 229 275 436 69 869 264 205 705 352 818 72 902 603 916 177 889 805 957 979 98 130 333 579 232 191 613 338 370 700 76 205 99 841 646 767 126 672 521 925 621 939 398 812 349 223 22 200 380 667 136 679 818 996 101 830 395 67 356 879 692 118 152 672 558 972 463 916 306 771 389 316 765 458
Output
-1438948
Large deadlines Test
Input
1000
1 5 2 4 7 8 7 3 2 4 6 5 10 1 2 3 5 1 7 3 7 4 2 2 8 2 4 10 4 10 9 8 4 9 3 6 10 5 6 8 8 3 10 1 7 4 4 1 2 6 7 4 10 6 7 7 6 9 5 1 9 7 3 4 8 9 4 10 6 1 1 5 8 8 3 3 2 2 5 9 5 10 3 3 8 7 5 3 3 6 6 7 9 3 10 8 6 7 10 4 4 4 3 7 1 6 4 4 5 9 9 6 2 9 10 9 10 6 9 3 9 5 8 7 6 2 5 3 7 6 8 2 2 2 9 1 9 10 6 8 10 4 1 4 1 6 10 9 4 5 2 10 8 10 2 1 9 7 5 1 10 3 3 10 8 4 3 7 4 9 9 5 5 9 8 6 9 2 2 4 8 10 9 7 5 7 7 10 6 2 10 3 5 1 2 9 9 2 10 10 6 7 5 8 2 3 4 2 8 2 2 2 4 7 4 2 2 1 5 6 9 4 7 1 8 8 4 8 2 5 8 9 10 4 4 6 4 8 9 9 6 4 5 6 4 8 5 4 6 1 3 1 2 8 3 7 1 7 7 2 1 6 7 2 7 4 2 9 5 1 10 9 3 2 4 1 6 9 5 5 1 4 10 9 9 2 1 10 5 7 7 6 8 1 1 1 6 6 10 6 8 9 8 7 2 9 10 3 1 8 10 7 9 4 3 6 2 6 7 7 7 1 8 2 1 5 7 9 7 1 6 1 5 8 6 3 4 6 1 2 10 10 4 5 6 1 9 10 8 6 4 4 2 3 7 7 8 4 10 1 10 2 6 6 4 7 1 6 9 9 5 4 10 2 4 2 3 10 4 6 7 8 6 9 4 6 4 7 10 10 8 6 2 2 3 10 3 6 6 10 4 1 8 2 10 3 10 4 7 9 8 6 10 10 10 9 5 7 10 9 7 1 6 1 4 7 6 6 5 10 5 3 7 1 8 8 6 1 9 7 7 9 2 2 3 7 1 5 6 1 7 7 9 10 1 1 2 4 2 5 7 1 3 3 7 9 3 2 7 7 9 4 7 6 6 7 9 8 2 8 4 2 6 1 2 8 3 6 2 7 2 1 5 6 10 8 9 9 9 6 5 9 1 8 4 6 8 2 8 2 1 6 9 4 5 7 10 5 10 6 8 6 8 4 7 6 1 4 7 10 5 5 7 3 5 10 5 4 2 6 4 4 4 9 1 2 8 3 3 6 7 5 6 10 4 6 10 7 8 3 3 3 4 1 4 9 4 6 3 5 3 1 3 10 7 5 4 9 4 9 7 10 6 6 9 7 10 5 2 2 1 7 5 4 9 8 6 3 10 3 1 5 9 1 1 10 4 3 2 5 7 8 7 9 2 10 4 1 6 5 7 10 1 5 6 2 6 6 6 3 7 2 8 2 8 3 10 6 10 8 3 1 4 3 8 4 2 5 3 10 1 4 4 9 8 9 2 5 5 9 4 4 1 5 6 10 2 3 10 4 2 3 7 4 1 1 2 6 3 3 2 8 3 5 6 7 5 8 4 10 8 7 4 6 5 3 6 4 1 9 10 4 10 10 2 1 6 7 2 5 8 9 5 9 1 5 6 3 5 8 4 1 9 10 6 9 5 9 3 7 3 1 1 10 4 5 3 4 4 2 9 6 3 6 2 9 1 10 9 10 4 7 3 9 1 10 4 4 8 7 6 8 1 10 3 3 8 3 9 4 2 6 8 9 3 8 9 1 10 6 9 2 9 9 8 10 5 2 3 6 2 5 7 3 8 6 10 5 2 8 6 5 10 10 10 5 7 2 5 5 5 10 2 7 7 8 5 9 2 9 2 6 7 2 7 8 2 3 4 8 2 1 5 7 7 5 9 4 3 1 9 4 1 10 2 5 5 3 10 10 5 5 5 10 6 5 10 4 2 9 3 10 5 4 9 8 7 2 10 10 6 5 7 5 9 9 5 1 4 7 9 6 4 8 8 5 6 9 9 10 5 1 6 5 9 8 5 5 3 7 10 5 2 4 8 7 4 7 3 3 4 3 7 4 3 6 4 6 1 2 10 5 4 3 9 9 3 2 1 7 6 8 1 1 2 5 8 6 10 3 7 1 10 10 4 9 7 7 3 10 2 3 3 8 7 6 7 7 7 7 1 1 3 7 9 10 6 1 8 5 1 3 6 4 9 4 4 3 3 7 5 8 8 6 6 10 5 4 5 7 3 9 9 5 5 4 4 2 5 9
442919 896366 765577 974285 465295 523347 724654 199832 603322 543581 276036 638791 272485 413211 932370 97876 144886 451644 626772 134703 609255 98954 729273 430585 585088 601934 487879 535746 26003 228341 779600 51652 435321 703601 776887 551008 356119 105583 211069 738232 364076 737178 575648 809222 358011 876678 954587 33095 76788 230095 51782 648583 2401 607021 610970 946556 857583 399669 857934 285047 127411 581445 624847 635991 549116 535150 803062 275161 30149 784900 771893 608169 447398 124552 103032 241515 623777 75253 938322 400570 955220 542353 168119 213316 37812 914917 130535 168800 230195 806684 653167 426045 785883 55477 949687 190388 428838 186313 300272 637443 379386 661906 293138 66442 493364 325501 751716 929836 513320 700839 982882 669470 798089 695401 486844 801046 18996 636247 913961 349896 679029 765674 864541 893869 103013 462477 378047 892828 490731 642107 778148 627927 133583 369820 45076 890183 62612 686037 308488 503396 165971 366799 762950 862310 588672 50652 149636 316002 122381 226005 937663 418506 385541 870115 842673 747900 880204 435144 148532 58919 875069 555451 588721 711177 522449 403847 766131 56718 675274 359757 408423 588077 275868 837277 618399 932796 279976 782716 820763 518322 772004 405029 486065 353941 412962 834082 843984 902243 310543 529738 933695 437178 884892 318310 808678 464590 443581 718602 480974 596395 240549 198073 69871 274174 577421 1657 18642 501079 870397 843732 82358 760015 909854 418989 164451 763640 708271 422157 627155 946061 459483 354898 393064 369081 122116 287506 566882 46778 705108 831240 843036 237151 53684 333873 924972 410820 277636 271054 792630 585949 414265 786256 179498 952632 507262 835774 742898 781888 736362 80197 398820 852419 100023 696166 290776 317810 347078 553859 809256 994182 178245 60207 379582 363094 309690 958134 115469 745439 941152 286318 338870 682204 768076 178158 653608 670593 211188 564960 105464 1329 700585 540000 183528 984740 646287 667866 420672 952792 914718 538261 885146 68260 747894 22738 459719 218681 562449 297632 985959 768349 313377 678414 309500 150474 224977 509252 407191 584388 898028 361591 264300 188695 970934 989495 30017 458266 732407 494908 303605 135132 898848 812640 516219 421970 60280 334376 712827 69384 78964 889767 921751 564869 460179 774818 836963 151476 279205 832730 513854 608469 299358 614434 926840 837181 128331 107039 786405 61208 699134 902165 414090 239412 344021 155610 891698 682416 390219 68886 383447 848723 50624 331882 200555 812251 939312 280326 243426 180011 174635 9127 684778 5083 970295 220142 891565 309115 869056 123978 334734 956001 784578 478265 400893 578173 260147 737416 241379 342206 964053 973448 284053 453148 663400 199379 465219 461618 605022 863952 78059 42858 770383 186282 235662 509434 582526 671836 224294 822845 363951 949683 639881 458220 265183 880216 97709 568968 705391 852143 437249 367198 572807 94906 993567 364755 437947 16820 99410 578512 1493 988191 662946 839071 549900 457425 229724 167193 7399 491139 321053 169731 444328 947948 621956 858193 606761 288181 550110 992106 453772 526164 40760 31670 49162 514565 233337 643794 829201 209365 386778 663858 426408 932572 876943 805048 553359 261205 254419 605285 296486 736013 138397 46683 207840 43492 745033 116041 592280 709447 159621 240475 942117 888592 365010 599346 194400 360099 505343 875286 700134 300790 967097 908174 745607 874113 495991 400987 196027 853899 257465 957702 619486 930521 256105 510611 342478 8921 921845 509803 808036 723600 83454 456816 932707 471681 462587 207505 192868 510706 38258 771417 91906 610192 945399 516410 451934 651470 202909 490717 521932 816607 960902 424041 718041 216340 453213 240906 263872 554290 429055 791178 544452 228816 429815 304507 226106 96944 494000 897135 481879 12361 366060 888132 768275 256059 473892 367554 47334 965891 390111 179056 504655 484463 569723 329029 426549 570736 135842 466057 997372 524525 903077 972454 466097 332912 504633 49095 446802 86911 597028 351943 20249 829500 223802 493218 188156 367438 85760 341362 499643 346267 848957 411273 551499 911377 358287 927007 162626 248406 232184 64172 916145 688376 136445 190962 584300 485765 724338 522076 79886 174722 874734 661575 500856 771993 20007 863637 363971 970278 782229 517639 469708 450979 578032 359302 14590 682364 776682 672938 570820 307301 41476 642595 975327 37216 762790 197873 373660 64391 785781 182646 493985 579528 215333 291116 566662 662412 934759 721046 783259 645968 912367 597721 116912 297801 853258 534377 800758 533519 75371 355686 627179 975246 414108 482945 191494 126613 536331 619021 159416 138179 90494 424871 335579 169449 839254 131348 997378 727596 114023 324967 66989 139329 870642 352310 511253 810431 749648 64144 889553 236859 625588 102211 328881 747954 200037 705020 467 968468 958428 230290 123542 975703 11795 532496 584704 444487 698886 407651 821612 332192 180935 604506 802017 250007 208859 137253 65291 884971 152605 415250 616397 796750 295136 408489 597828 706002 445700 637147 135396 338352 560721 931823 192253 126933 293811 909957 44181 321749 334309 818521 799695 135509 850754 263897 114672 554288 559843 6730 324032 237080 401292 961591 381474 538489 952592 480214 458225 451614 640699 762868 894612 521292 642167 236834 939730 489087 484305 100493 417284 992767 67964 275572 815029 237470 742657 585568 767439 57023 1727 854062 362134 374244 347747 327575 524815 112903 549354 399172 303855 189355 860871 960080 468522 129784 950885 454899 29363 514986 106526 399368 39210 371845 405895 90911 261418 558102 792733 903335 142988 291495 47778 98318 350703 997235 162392 508023 326988 676124 754139 655496 516872 12883 255783 525032 648525 369673 139331 27702 905274 990528 728273 178173 702434 734048 553304 35936 516051 31364 62508 858396 577229 405490 388250 509567 696637 255448 294383 219975 375265 651540 485396 113947 653833 769570 446847 868483 370957 632317 776245 942870 176292 888314 5459 534084 682400 833019 417206 485525 96021 314814 727495 886484 88437 934137 894157 319965 598001 72077 505126 499062 908494 716161 713194 169867 441064 822622 644968 900947 142030 468870 419571 329448 75939 414997 76217 485344 300995 110836 25252 494799 78414 120360 103236 363435 571689 956410 363625 575284 792302 988503 650270 428848 178966 471121 463312 261111 334099 199691 484075 801928 442065 710478 109695 770637 915661 243728 113096 368763 107405 734221 259333 259737 403570 56151 801905 948361 455489 177613 775244 994997 226054 563681 158992 256952 223321 741505 504732 519675 913500 957768 298576 691283 898130 348761 569308 48438 843544 119053 620992 826519 319889 125320 787448 106523 33097 875417 83972 441375 906752 997003 272732 883935 611218 991163 922515 924542 663377 199184 179071 404232 580617 962560 959024 679453 348109 782967 828776 821986 736456 119355 605220 671580 49893 837352 310007 949258 745098 1378 34718 293981
Output
486915940
Large deadlines Validator
Input
1000
33 12 20 95 33 55 39 23 25 94 98 83 78 38 48 6 71 63 58 41 35 6 68 78 30 27 65 25 97 67 5 45 48 41 95 55 64 13 34 13 72 66 87 95 75 67 15 62 3 49 33 77 85 51 3 77 36 64 55 11 56 60 59 90 62 20 85 23 53 53 4 78 74 15 61 32 17 25 91 15 21 54 81 63 73 77 39 83 71 47 100 51 22 75 69 16 17 37 74 88 59 27 57 50 79 96 49 49 36 40 23 46 84 2 5 86 44 1 7 27 95 8 28 4 63 75 40 33 66 30 89 36 57 10 46 88 60 76 74 24 8 90 5 19 88 46 5 3 82 88 72 31 88 51 23 94 51 13 27 83 41 82 8 4 82 19 2 39 21 69 63 79 22 82 45 97 56 92 43 98 62 83 6 57 96 98 76 31 3 58 70 4 19 33 96 15 21 26 8 93 4 15 29 45 96 88 24 13 13 12 9 21 12 37 34 14 21 50 74 24 58 77 29 56 44 48 90 57 37 56 23 35 100 73 58 73 36 10 31 64 87 15 72 11 32 12 86 21 32 87 74 100 7 19 46 63 69 77 77 36 61 53 22 78 32 17 97 85 3 7 98 99 14 17 12 99 91 77 35 71 41 60 67 24 68 46 98 55 13 37 93 9 60 74 76 67 3 77 6 85 63 10 69 5 49 56 75 22 11 58 49 48 28 34 95 100 68 100 81 66 91 64 92 88 67 26 29 87 95 31 83 67 52 91 43 60 7 84 69 13 47 38 82 9 50 31 2 59 31 70 93 37 84 31 13 67 12 3 39 57 20 49 19 19 49 36 76 53 33 30 42 96 62 57 48 15 8 97 68 97 98 54 26 74 54 41 62 63 89 45 12 2 41 86 94 78 98 45 11 15 22 56 44 19 60 9 95 21 75 20 6 77 76 28 77 24 19 87 56 73 44 27 62 70 33 15 97 11 36 86 11 93 6 21 84 84 41 32 41 37 28 46 89 9 68 86 87 31 91 46 93 64 66 65 29 98 13 24 53 33 75 70 83 42 93 1 4 1 23 76 15 16 100 61 91 80 45 57 28 66 19 70 49 67 50 55 55 67 67 14 81 1 86 77 62 17 24 84 33 80 87 7 80 27 5 92 87 5 30 23 22 45 47 60 57 67 58 82 35 48 62 64 84 74 10 43 86 53 8 55 92 83 19 5 4 26 13 51 79 47 40 79 62 48 34 40 15 29 34 62 70 75 31 24 62 46 26 2 40 40 14 68 21 49 8 38 88 40 97 67 41 32 86 4 51 81 74 55 88 80 78 98 4 1 8 3 4 20 2 71 100 87 75 97 72 58 97 45 72 69 7 9 7 75 29 72 32 88 76 27 82 96 44 90 81 66 99 61 16 9 78 47 39 4 45 92 88 49 85 45 94 30 24 27 6 53 71 18 24 66 88 70 3 23 40 14 29 41 69 61 32 75 97 20 70 25 53 5 22 75 54 87 14 91 14 66 66 20 82 37 31 53 24 7 47 31 75 4 59 94 41 59 58 77 46 56 3 3 97 95 68 62 32 87 62 32 61 94 98 25 20 29 25 69 92 46 25 32 29 80 69 49 90 95 82 63 49 79 74 65 10 11 27 9 27 12 29 43 55 83 91 36 52 32 59 77 39 30 56 61 89 49 90 18 75 39 31 54 42 89 76 43 39 8 5 79 21 99 64 81 58 80 84 37 94 34 92 99 32 31 86 61 29 88 42 79 67 63 1 69 8 24 58 36 77 18 96 32 49 42 7 71 41 78 100 39 30 68 89 15 66 99 97 74 38 10 88 29 85 39 29 74 31 92 9 18 58 32 65 36 7 1 41 13 2 35 76 29 46 33 29 48 49 23 64 81 30 79 29 49 28 8 16 91 38 22 8 12 66 9 34 63 46 77 15 24 71 68 90 60 32 64 51 26 81 99 42 59 47 34 6 27 24 55 70 100 1 71 67 9 71 14 56 8 56 80 66 37 60 52 59 34 62 38 70 67 97 3 18 2 100 11 93 11 96 74 46 11 66 56 87 14 72 12 63 32 13 69 88 60 45 69 74 12 3 41 16 22 91 50 44 6 27 86 92 75 98 20 98 88 72 53 84 90 98 89 70 8 76 10 55 25 47 34 86 70 6 30 76 6 4 15 16 93 11 36 8 42 30 87 37 16 28 40 100 16 39 59 28 78 42 62 11 99 81 32 98 85 38 24 83 30 4 8 40 41 61 21 66 73
198110 421568 439993 248450 835608 128376 725608 5615 851683 87761 501145 587514 490922 647705 709431 180300 178818 435995 771472 308736 423274 589785 617617 61900 893627 292578 179549 858520 442669 813004 499116 803662 285867 931186 749340 642019 196170 552019 503165 206514 886896 334392 566174 119645 490301 901846 226267 289160 294981 480935 949919 394001 625956 921552 236004 692995 14830 559419 370025 683112 488938 140159 506219 343007 583711 992649 880220 708106 382202 726479 558189 796562 364152 200237 161653 18820 244963 944614 668450 318570 232563 908765 852486 909745 182903 619244 654913 794176 881210 768208 140556 821070 513650 484762 625701 291204 866105 552396 198517 607640 159888 86197 478099 957428 782342 478507 30864 223129 303062 549180 832830 972539 164234 1013 888621 3550 294687 542779 328915 519398 439891 809084 194352 864044 384819 480921 767530 407018 658471 808274 652019 68427 263965 682339 885101 111417 898663 269726 984876 664017 862336 442919 934921 508293 159429 798591 124676 917427 849436 894267 18728 266960 837956 590462 393614 680857 79539 3553 460436 159040 331912 267487 380199 527855 223703 71077 143459 333339 455094 279747 374343 328187 27099 432518 982296 911303 202804 452515 873717 710183 679716 612290 734043 456706 748978 624538 94010 491614 114198 449219 846709 351217 72821 333176 784924 581090 154380 537964 410210 606810 396639 302228 243634 993678 793374 776607 561090 21521 644963 802393 806911 479856 569345 490184 283002 789761 255858 792898 539232 178727 460283 897793 97336 335014 666953 354910 683832 268139 506802 849526 886590 846292 25779 510382 133797 4211 718752 879620 83732 168725 797735 929108 503073 813870 306576 275447 589424 581515 701040 194341 889634 998109 197519 918588 903458 984643 799917 397966 768260 543281 795772 567718 181470 122509 304326 415882 724923 499284 966839 756113 447236 499555 509261 358592 268299 823139 862663 423634 89736 399194 487987 320221 485558 8563 958964 115073 382055 532390 34126 832522 915565 390577 474488 243724 792945 203020 726497 131696 307008 156175 939362 239765 666974 319059 379537 490349 90256 990017 43986 742942 943545 323064 603564 489301 379499 617704 306013 380538 708599 341576 284988 183156 135588 933610 339569 230632 6104 230310 836187 943603 435189 309593 153246 276427 488843 442830 465326 128254 321907 397053 771427 959585 12497 51748 742016 802844 860072 301882 854142 686904 78093 434159 91014 706989 747131 838389 436908 258258 48983 901437 425271 411611 244136 8329 898995 538143 496783 847762 811893 876844 502776 127688 779625 517401 153948 209270 168320 429262 436933 596207 122651 912830 368773 526650 263505 974620 674371 59710 755015 833691 112033 922957 419274 263545 792418 921774 731257 950929 325325 527635 505583 689885 440516 497345 663628 984407 376181 168395 580667 492209 927035 146858 55555 996079 30713 431934 804652 949542 883729 997190 283314 364374 918986 859903 846575 850155 711806 676769 483900 254346 68175 45897 637193 853286 211891 60137 149563 607922 736887 752999 388595 407934 816095 280154 634768 847533 536071 456615 491335 523270 25612 181908 854883 784736 619 395296 235250 601694 842831 749599 79672 131650 895374 450129 179683 612534 537047 185563 63133 890989 731489 160175 600613 831687 588739 896121 389808 106166 859927 958301 442158 130496 349418 695128 520606 289952 27452 853789 995991 984885 219961 660550 641774 447023 796694 690967 725499 968974 936019 530105 67850 611229 932783 740482 901475 971558 246095 710263 883167 235977 20084 673594 513899 741361 952499 318224 633627 425400 586642 926271 849239 639921 747977 971048 50757 417621 380870 673972 402178 425376 38940 252075 378348 938544 902839 321667 683298 420026 693444 124499 11201 949664 304187 698598 468778 318513 727720 911084 60522 66989 673969 632822 233906 839270 636 183598 492350 41144 364899 997254 741493 890045 341683 770867 651348 679061 64581 774039 689272 15656 521818 136079 612379 355738 239800 777326 841895 159513 405320 519813 49709 561578 335730 760707 972175 336240 274516 675288 83125 55702 624679 149862 210295 865394 127950 2659 212632 985600 393039 321960 763967 386211 839939 358562 353737 109895 312412 724920 956873 945605 512398 344484 599163 827867 368342 51665 477236 749724 968365 311111 830758 384569 192387 317970 209169 67780 174205 725629 28682 615140 159483 490979 792516 832870 488109 377163 670925 165346 641094 696349 284150 305022 54849 200197 98452 140869 632121 727738 296921 332610 830432 271519 130705 509128 779884 439358 863036 870944 971699 526780 215024 328472 880788 238176 854815 174501 685347 158965 562705 390944 67208 583774 290314 132268 169750 128192 188976 2634 929588 911465 608294 886082 958297 842075 429106 357683 729447 145649 440680 666732 887698 580096 16137 533185 970 200138 847791 150081 647824 294081 918635 878173 240561 334989 240898 532776 870144 912062 845111 427402 601773 356621 930888 926432 957175 981086 745811 464801 755134 577642 159563 723321 741020 371287 619842 933380 403625 310969 468204 759768 786860 829738 975699 911159 343516 463852 324172 561985 313279 828464 974933 256616 920821 433909 185214 351548 990884 562233 123722 482142 382827 7912 618689 634514 509158 702442 151608 802383 726316 155666 135116 856299 43152 910350 496359 973370 392 267381 9440 965370 724454 152474 497530 196349 650705 810477 362183 238340 922291 308976 790214 890398 70189 440604 908275 585378 465747 484527 832267 870834 214655 444361 161181 251271 43673 765351 984898 486775 131855 117942 176298 730302 5157 809443 835132 867011 630395 91123 516476 999730 174614 290867 805370 778794 584105 164915 668377 688272 631320 766988 164110 812699 979799 368516 46950 10011 692875 806045 688265 724409 620009 719335 204726 856360 747899 767550 688469 545147 804910 165650 555614 740673 641306 896666 399631 755697 359691 521391 372473 184702 235964 308252 631259 613297 712313 107154 861374 713853 311958 148439 592652 257084 398892 290373 465439 279619 728571 272069 858000 524588 576740 9658 773702 720106 895988 96861 846997 44803 784173 661157 860395 870846 672692 157025 120277 458286 118699 147590 231458 461310 430366 223845 228119 48027 960497 485325 946266 453697 477888 971273 396015 593238 963729 230561 200086 768826 720318 569936 971710 430781 934596 51183 763440 45959 768541 726648 775408 375239 549444 202849 317029 488420 619085 663596 980411 561484 404726 465862 494410 191168 905229 264251 172249 838480 903513 684369 224487 361617 659738 17695 784666 502227 385946 93998 720762 234983 202551 777135 866922 946208 777710 21063 876577 73278 93349 368618 665804 204764 652360 1108 298911 605418 712079 44972 760735 948475 121291 364116 517431 503073 997549 919661 692473 137122 680742 745560 208712 17110 822398 299281 763617 582003 607590 770350 316362 337091 904094 845535 190089 422081 484686 313993 550330 547569 895420 198412 454944 642903 476750 832752
Output
493062407
Solution language
Solution
Stub generator input