THE QUESTION
Text from the official booklet. Refer to the PDF for original mathematical notation, formatting, and linked input files. Printed samples and inputs are reproduced as published.
The robots are under attack and have tracked down your location! There are n robots in a row with an initial health value of ai ≥ 0. Your goal is to eliminate all robots by reducing their health to 0 using a combination of different laser guns. However, your laser guns only have a limited amount of bullets, so you need to use them optimally in order to survive. There are 3 types of laser guns you can use to eliminate the robots which use x, y, z amount of bullets respectively: • Photon Edge: Choose any consecutive block of exactly k robots and reduce each of them by 1, but only if all of them currently have power ≥ 1. (You can’t reduce below 0.) • NovaStrike: Choose a single robot with ai ≥ 1 and reduce its power by 1. • Lumina-X: Choose any three consecutive pillars i − 1, i, i+ 1, and set ai = max(ai−1 − 1, ai, ai+1) − 1 Your task is to find the minimum bullets required to make all ai = 0. If it’s impossible, print -1. Input format: Each test contains multiple test cases. The first line contains the number of test cases t (1 ≤ t ≤ 104). The description of the test cases follows. • The first line of each test case contains the number of robots n (3 ≤ n ≤ 2 × 105) and k (1 ≤ k ≤ n) • The second line contains the costs of bullets x, y, z(1 ≤ x, y, z≤ 109) for each laser gun • The third line contains the initial health value ai (0 ≤ ai ≤ 109) for each of the n robots Output format: Print a single integer → the minimum total bullets required, or -1 if it’s impossible. Sample Input: 1 7 3 8 2 5 2 3 1 4 2 3 2 Sample Output: 31 Input: 25 83 21 255 91 170 835 562 403 963 585 552 107 707 912 543 765 523 858 381 554 625 14 409 923 466 32 549 702 371 773 982 417 11 152 274 970 168 580 611 860 39 11 251 5 259 605 972 720 36 767 388 832 43 860 318 488 103 577 763 630 674 249 648 981 389 431 38 939 972 347 482 51 544 878 630 198 659 30 637 74 665 239 227 388 43 4 157 57 268 692 992 291 560 529 8 236 511 563 777 837 997 273 365 584 647 514 149 366 698 172 603 718 917 545 243 694 493 634 927 244 378 853 143 169 864 391 442 575 976 874 590 758 25 3 331 299 64 413 142 715 267 950 619 322 315 704 785 97 502 272 718 138 481 433 252 742 799 339 619 36 773 377 70 67 264 436 410 610 869 125 946 655 267 301 815 917 231 370 805 983 788 499 470 617 459 97 654 609 711 830 560 722 954 14 438 179 789 404 614 913 49 698 420 120 945 558 454 826 558 408 77 493 834 137 595 10 570 923 433 109 62 933 798 934 55 841 303 936 987 841 522 534 50 991 254 67 485 40 4 498 332 74 471 970 211 915 96 599 119 448 113 723 916 781 897 137 473 119 382 737 55 65 26 1 720 953 618 138 80 446 126 123 501 48 381 724 543 261 576 217 132 300 43 10 439 123 107 911 357 49 891 391 670 782 382 757 25 505 671 100 760 741 308 6 628 442 862 824 652 432 895 257 795 65 713 555 420 37 104 748 153 362 367 577 949 103 426 117 516 193 25 22 44 356 498 568 431 712 654 982 322 641 830 463 407 498 85 725 278 39 199 861 548 479 96 741 511 888 870 778 16 5 232 360 410 967 37 369 584 627 446 923 86 564 904 407 620 583 862 57 854 23 14 293 5 105 383 188 183 259 850 835 60 944 514 308 191 579 691 345 187 843 405 536 443 339 313 637 586 54 17 163 162 193 368 430 142 835 764 879 899 193 717 327 316 193 952 331 461 56 373 250 325 930 509 682 897 566 391 71 68 454 167 770 571 226 361 386 106 800 448 578 974 874 96 630 568 852 851 654 904 184 831 539 815 801 301 764 28 3 327 286 253 817 875 222 379 927 422 993 233 534 492 13 115 995 12 265 959 37 217 856 226 620 15 641 176 804 178 950 765 36 34 91 462 63 777 98 376 256 704 15 936 934 725 904 191 240 388 368 838 763 129 195 466 687 355 778 218 80 40 395 692 480 890 548 486 760 351 900 409 867 46 8 390 470 9 445 99 938 175 451 576 905 567 867 258 237 15 64 191 69 941 400 605 918 436 345 427 237 29 200 148 938 271 623 30 30 497 166 654 699 28 556 721 55 253 9 477 633 129 626 234 61 14 201 163 6 568 931 455 38 451 517 172 26 453 478 692 93 781 27 866 611 843 388 764 137 234 891 778 898 684 147 230 251 818 691 914 431 773 937 854 287 437 205 578 770 708 985 257 966 744 288 946 815 345 263 232 152 290 912 961 139 185 638 713 969 274 60 46 415 96 177 259 882 509 222 805 302 696 792 102 743 182 567 889 671 638 25 314 602 817 981 143 134 119 423 214 68 70 733 653 942 88 758 356 72 983 381 0 835 537 341 658 806 385 477 149 571 823 800 633 152 325 666 647 877 830 19 470 799 243 552 18 8 396 308 132 595 425 252 287 464 565 712 663 633 783 676 152 783 955 673 684 560 841 55 49 378 96 251 902 761 208 419 821 389 425 361 562 742 662 14 621 906 775 941 35 414 817 672 817 717 840 831 126 759 461 965 953 902 865 80 418 736 924 563 471 376 283 778 253 78 78 661 466 648 92 529 142 952 111 789 128 478 622 5 4 315 86 444 696 93 106 593 454 23 16 422 441 329 908 985 528 724 252 888 495 591 909 3 313 335 163 45 281 193 666 272 601 418 306 385 443 59 33 296 252 283 200 608 592 746 23 638 620 659 440 734 343 11 733 417 797 486 146 751 756 496 669 25 916 621 393 20 234 610 665 504 731 176 270 270 478 386 934 675 563 997 336 918 63 620 97 332 341 255 637 556 464 381 331 973 143 987 855 526 166 29 24 413 45 479 325 142 240 619 825 563 746 262 216 677 245 1000 948 513 142 22 111 952 790 921 862 213 282 619 724 891 793 954 104 60 14 77 437 383 381 727 187 656 767 416 166 347 533 954 230 922 771 345 252 274 318 660 898 740 888 774 44 257 737 118 171 500 302 980 752 67 354 623 956 992 535 967 889 183 634 981 484 811 31 228 946 902 540 554 959 368 545 813 765 976 746 108 928 768 66 65 388 67 461 799 875 553 222 425 270 805 128 643 899 492 768 153 260 111 914 601 553 671 987 758 956 677 327 734 935 914 11 714 277 510 278 563 124 310 583 252 636 450 176 788 981 604 407 19 371 993 878 521 824 928 266 864 689 851 140 556 43 0 25 384 334 871 171 997 293 93 54 311 84 177 25 548 691 561 90 515 219 914 919 584 784 599 327 434 748 624 722 398 936 545 984 204 688 486 83 649 667 108 358 495 194 647 511 831 413 157 181 957 555 382 601 165 243 535 102 448 108 746 456 758 206 416 308 208 801 664 487 37 418 30 821 128 114 856 455 358 24 573 569 928 744 603 162 701 404 356 55 926 126 769 131 235 187 264 7 639 238 9 34 158 676 145 633