Portafolio de Inversiones X54535
Paco es gerente de un banco, y ha observado que muchos de sus clientes buscan alternativas para hacer crecer sus ahorros. Inspirado por la gran variedad de fondos de inversión que ofrece el banco, él ha decido tomar iniciativa y presentarles planes de ahorro personalizado. Paco sabe que la mejor estrategia es diversificar la inversión, seleccionando múltiples fondos de tal manera que se incrementen las ganancias obtenidas para el cliente. Desafortunadamente, el ahorro del cliente es limitado y las posibilidades de inversión muy variadas. Para complicar un poco más las cosas, las ganancias son distintas para cada cliente. Paco conoce a la perfección a cada cliente, por lo que sabe la inversión necesaria y la ganancia específica a que puede aspirar por cada fondo. Lo que no conoce es cuánto está dispuesto a invertir de sus ahorros el cliente. Ayuda a Paco creando un programa que lo apoye en la creación de los Portafolios de Inversiones Personalizados. El programa deberá ofrecer la mejor estrategia de inversión seleccionando los fondos que mejoren la ganancia del cliente a partir del ahorro que éste último quiere utilizar, y de la información de inversión y ganancia asociada a él que posee el gerente. Considere que la suma de las inversiones no debe exceder los ahorros que el cliente desea invertir, y que la inversión en un fondo es fija (no se puede reducir o incrementar).
Para ilustrar la situación, el cliente Enrique está dispuesto a invertir 80 pesos de sus ahorros, y las posibilidades de inversión son las siguientes:
Fondo Inversión Ganancia F1 40 5 F2 20 2 F3 30 3 F4 35 4
Considerando lo anterior, Paco le indicó a Enrique que la mejor estrategia de inversión sería que invirtiera 40 pesos en el fondo F1 y 35 en el fondo F4, lo cual le proveería una ganancia de 9 pesos inmejorable.
Entrada
Una línea de entrada con dos valores enteros n A indicando el número n de fondos de inversión disponibles para cliente y el ahorro A a considerar, seguida por n líneas cada una conteniendo tres valores enteros i Ii Gi indicando el índice i de referencia de la inversión Fi, la inversión del fondo Ii y la ganancia Gi al invertir.
Salida
Una línea de salida conteniendo la ganancia máxima que se puede obtener.
Observación
- Considere que n ≤ 1000
- Considere que A ≤ 2000
- No olvide imprimir un salto de línea al final.
Public test cases
Input
4 80 1 40 50 2 20 20 3 30 30 4 35 40
Output
90
Input
4 20 1 9 6 2 11 5 3 13 9 4 15 7
Output
11
Input
10 60 1 20 30 2 18 25 3 17 20 4 15 18 5 15 17 6 10 11 7 5 5 8 3 2 9 1 1 10 1 1
Output
80
Input
23 10000 1 981 983 2 980 982 3 979 981 4 978 980 5 977 979 6 976 978 7 487 488 8 974 976 9 970 972 10 485 486 11 485 486 12 970 972 13 970 972 14 484 485 15 484 485 16 976 969 17 974 966 18 482 483 19 962 964 20 961 963 21 959 961 22 958 958 23 857 959
Output
9777
Input
1000 5002 1 485 94 2 326 506 3 248 416 4 421 992 5 322 649 6 795 237 7 43 457 8 845 815 9 955 446 10 252 422 11 9 791 12 901 359 13 122 667 14 94 598 15 738 7 16 574 544 17 715 334 18 882 766 19 367 994 20 984 893 21 299 633 22 433 131 23 682 428 24 72 700 25 874 617 26 138 874 27 856 720 28 145 419 29 995 794 30 529 196 31 199 997 32 277 116 33 97 908 34 719 539 35 242 707 36 107 569 37 122 537 38 70 931 39 98 726 40 600 487 41 645 772 42 267 513 43 972 81 44 895 943 45 213 58 46 748 303 47 487 764 48 923 536 49 29 724 50 674 789 51 540 479 52 554 142 53 467 339 54 46 641 55 710 196 56 553 494 57 191 66 58 724 824 59 730 208 60 988 711 61 90 800 62 340 314 63 549 289 64 196 401 65 865 466 66 678 689 67 570 833 68 936 225 69 722 244 70 651 849 71 123 113 72 431 379 73 508 361 74 585 65 75 853 486 76 642 686 77 992 286 78 725 889 79 286 24 80 812 491 81 859 891 82 663 90 83 88 181 84 179 214 85 187 17 86 619 472 87 261 418 88 846 419 89 192 356 90 261 682 91 514 306 92 886 201 93 530 385 94 849 952 95 294 500 96 799 194 97 391 737 98 330 324 99 298 992 100 790 224 101 275 260 102 826 97 103 72 210 104 866 649 105 951 919 106 748 63 107 685 958 108 956 804 109 564 518 110 183 428 111 400 537 112 721 346 113 207 153 114 323 971 115 611 662 116 116 197 117 109 91 118 795 529 119 343 126 120 862 747 121 685 469 122 10 770 123 881 934 124 984 723 125 403 895 126 360 568 127 449 172 128 541 958 129 272 383 130 877 308 131 359 970 132 707 583 133 308 48 134 770 930 135 30 569 136 208 3 137 311 20 138 100 609 139 939 887 140 422 825 141 785 930 142 370 904 143 989 241 144 969 379 145 143 376 146 972 962 147 28 889 148 61 443 149 638 216 150 348 338 151 347 160 152 66 406 153 391 159 154 638 31 155 295 204 156 826 420 157 196 153 158 449 425 159 855 331 160 143 565 161 487 838 162 140 9 163 564 918 164 615 533 165 135 232 166 564 957 167 360 591 168 793 576 169 163 746 170 859 377 171 760 858 172 711 86 173 662 434 174 159 558 175 660 279 176 268 840 177 948 735 178 315 574 179 676 126 180 341 912 181 689 739 182 894 821 183 706 625 184 490 917 185 478 201 186 671 993 187 932 149 188 899 52 189 237 759 190 187 267 191 472 256 192 772 783 193 98 117 194 906 516 195 911 180 196 635 25 197 225 380 198 823 712 199 164 266 200 343 216 201 732 448 202 502 541 203 740 664 204 576 954 205 612 726 206 902 772 207 454 531 208 411 943 209 973 750 210 703 327 211 850 917 212 77 5 213 220 113 214 802 913 215 403 791 216 181 998 217 10 859 218 525 345 219 919 431 220 668 675 221 527 833 222 462 438 223 291 523 224 605 916 225 457 420 226 405 115 227 417 660 228 279 261 229 685 772 230 596 388 231 307 764 232 224 843 233 322 206 234 840 407 235 975 639 236 401 852 237 91 542 238 327 60 239 330 757 240 182 82 241 603 637 242 793 93 243 615 614 244 733 136 245 864 187 246 16 102 247 863 972 248 987 163 249 306 501 250 34 477 251 840 492 252 700 121 253 706 80 254 787 138 255 105 660 256 834 229 257 798 827 258 310 448 259 609 230 260 690 832 261 561 489 262 579 586 263 60 291 264 388 665 265 309 660 266 407 702 267 200 153 268 313 606 269 970 123 270 33 253 271 273 709 272 277 832 273 997 108 274 40 888 275 227 481 276 860 283 277 940 858 278 608 284 279 990 711 280 590 850 281 806 239 282 52 943 283 801 195 284 764 95 285 710 410 286 386 664 287 593 900 288 50 112 289 494 963 290 156 754 291 936 458 292 965 19 293 86 225 294 723 569 295 184 97 296 868 194 297 340 754 298 412 602 299 487 61 300 209 695 301 346 347 302 860 719 303 307 100 304 95 97 305 821 843 306 941 745 307 821 286 308 587 492 309 201 116 310 665 531 311 527 424 312 812 253 313 424 426 314 459 413 315 343 980 316 836 291 317 506 833 318 179 486 319 916 9 320 430 575 321 596 922 322 808 145 323 269 897 324 512 404 325 811 742 326 685 728 327 567 269 328 776 103 329 855 745 330 718 35 331 853 779 332 97 71 333 146 80 334 746 842 335 15 128 336 965 941 337 512 227 338 480 30 339 958 342 340 665 605 341 191 531 342 964 364 343 515 359 344 606 867 345 822 820 346 536 313 347 693 207 348 19 911 349 335 308 350 101 430 351 922 685 352 294 641 353 910 113 354 410 141 355 250 690 356 546 700 357 729 559 358 609 481 359 720 503 360 976 766 361 759 7 362 798 882 363 74 859 364 648 182 365 299 425 366 785 542 367 846 683 368 390 853 369 897 938 370 416 89 371 837 624 372 247 181 373 293 878 374 144 933 375 938 580 376 467 252 377 480 207 378 955 658 379 665 20 380 26 954 381 564 347 382 449 759 383 26 446 384 521 14 385 301 657 386 321 710 387 613 980 388 388 188 389 879 636 390 990 203 391 188 432 392 963 129 393 820 630 394 300 509 395 822 237 396 255 373 397 277 838 398 153 395 399 400 692 400 227 103 401 518 218 402 447 384 403 315 931 404 813 396 405 324 389 406 502 640 407 299 287 408 780 297 409 376 977 410 516 512 411 212 219 412 329 555 413 810 398 414 486 289 415 485 798 416 416 598 417 952 49 418 894 572 419 358 697 420 21 770 421 647 725 422 44 542 423 683 214 424 361 887 425 814 45 426 231 94 427 8 282 428 165 82 429 496 319 430 699 626 431 852 146 432 459 541 433 535 874 434 314 725 435 944 777 436 306 554 437 459 208 438 637 787 439 447 976 440 408 912 441 107 444 442 962 3 443 565 301 444 407 164 445 857 437 446 317 652 447 98 764 448 818 41 449 600 737 450 288 176 451 902 136 452 567 128 453 190 394 454 749 235 455 908 42 456 276 824 457 748 684 458 592 979 459 393 568 460 363 367 461 163 52 462 983 642 463 179 335 464 16 126 465 478 130 466 259 583 467 868 129 468 295 752 469 596 167 470 71 856 471 622 640 472 864 770 473 644 431 474 5 195 475 365 448 476 429 701 477 64 952 478 854 880 479 770 168 480 88 79 481 157 961 482 368 472 483 421 217 484 719 709 485 271 147 486 975 296 487 816 909 488 962 764 489 535 251 490 438 878 491 696 753 492 881 570 493 318 253 494 45 666 495 52 931 496 496 433 497 313 810 498 138 678 499 334 123 500 988 212 501 508 66 502 770 206 503 751 750 504 780 64 505 441 466 506 207 337 507 516 510 508 674 796 509 408 175 510 920 437 511 573 938 512 634 848 513 878 561 514 990 718 515 826 948 516 696 649 517 800 569 518 411 663 519 422 582 520 707 843 521 334 202 522 986 702 523 494 579 524 150 725 525 562 803 526 380 340 527 832 156 528 979 832 529 376 602 530 511 234 531 414 688 532 160 184 533 982 978 534 238 413 535 490 633 536 899 585 537 251 606 538 526 963 539 897 350 540 39 242 541 657 539 542 452 739 543 538 267 544 831 165 545 460 177 546 185 720 547 934 802 548 440 644 549 490 82 550 168 798 551 71 197 552 977 173 553 458 81 554 204 235 555 803 112 556 139 103 557 399 268 558 420 879 559 991 643 560 578 106 561 972 122 562 177 444 563 398 262 564 348 691 565 496 997 566 276 446 567 825 171 568 614 549 569 121 281 570 730 211 571 341 112 572 284 408 573 698 730 574 17 363 575 546 89 576 672 605 577 974 938 578 866 168 579 377 705 580 559 47 581 340 400 582 527 215 583 779 114 584 761 51 585 483 881 586 92 549 587 390 679 588 583 328 589 661 250 590 391 203 591 336 481 592 661 752 593 125 707 594 89 82 595 275 63 596 359 660 597 178 21 598 780 287 599 42 219 600 5 500 601 380 820 602 772 95 603 816 44 604 9 748 605 484 678 606 545 276 607 589 478 608 157 663 609 901 594 610 777 757 611 74 947 612 247 448 613 55 570 614 479 313 615 785 981 616 958 795 617 680 552 618 393 389 619 944 280 620 596 864 621 619 636 622 611 512 623 852 892 624 283 184 625 299 947 626 766 614 627 312 625 628 826 149 629 726 377 630 733 474 631 805 18 632 679 662 633 403 416 634 964 1 635 337 530 636 541 752 637 478 22 638 369 981 639 946 777 640 821 957 641 833 275 642 837 584 643 490 582 644 37 121 645 594 951 646 129 668 647 258 118 648 246 319 649 362 896 650 755 521 651 504 948 652 71 248 653 177 474 654 176 351 655 803 54 656 237 155 657 677 660 658 33 871 659 115 486 660 597 294 661 769 425 662 536 245 663 956 382 664 341 371 665 184 708 666 234 544 667 569 794 668 216 387 669 537 738 670 84 520 671 810 281 672 657 502 673 33 91 674 159 503 675 520 924 676 668 16 677 287 33 678 229 344 679 374 349 680 474 606 681 672 896 682 915 595 683 511 441 684 123 102 685 569 52 686 199 654 687 396 710 688 715 434 689 59 245 690 610 36 691 917 661 692 927 413 693 270 13 694 117 370 695 516 400 696 215 195 697 216 984 698 237 476 699 615 164 700 499 405 701 477 674 702 760 196 703 285 608 704 56 907 705 966 532 706 622 51 707 221 716 708 194 327 709 91 880 710 347 710 711 252 267 712 473 400 713 516 376 714 385 609 715 357 320 716 958 196 717 665 538 718 792 935 719 64 404 720 420 100 721 671 126 722 968 855 723 877 94 724 177 731 725 523 253 726 139 8 727 152 393 728 732 543 729 246 348 730 565 318 731 740 489 732 902 22 733 17 998 734 973 49 735 298 381 736 611 10 737 32 429 738 11 221 739 337 150 740 136 717 741 889 530 742 522 332 743 805 942 744 28 565 745 931 216 746 757 61 747 609 170 748 544 872 749 905 644 750 595 208 751 246 680 752 113 697 753 175 639 754 156 679 755 244 961 756 883 361 757 265 802 758 883 359 759 462 839 760 485 718 761 272 280 762 204 252 763 984 280 764 409 102 765 398 615 766 909 296 767 370 481 768 882 956 769 214 230 770 766 259 771 35 922 772 421 706 773 271 272 774 370 156 775 848 552 776 50 485 777 976 536 778 270 70 779 796 902 780 963 452 781 379 35 782 991 947 783 551 378 784 897 57 785 307 352 786 421 669 787 74 702 788 388 141 789 559 458 790 980 463 791 615 756 792 681 887 793 231 332 794 207 528 795 818 656 796 331 254 797 979 787 798 445 495 799 348 370 800 724 10 801 401 200 802 646 327 803 668 17 804 242 374 805 302 755 806 861 980 807 830 376 808 77 8 809 441 32 810 589 460 811 990 804 812 189 23 813 868 869 814 996 943 815 363 715 816 237 628 817 420 73 818 565 199 819 214 38 820 333 209 821 726 327 822 175 912 823 58 799 824 625 372 825 66 976 826 169 120 827 475 667 828 204 188 829 90 28 830 496 704 831 1 649 832 474 746 833 449 697 834 252 712 835 332 289 836 287 625 837 189 953 838 889 462 839 63 302 840 378 79 841 206 41 842 897 823 843 230 908 844 382 665 845 575 36 846 60 732 847 529 809 848 477 66 849 290 291 850 89 591 851 961 583 852 461 252 853 702 479 854 532 530 855 680 224 856 53 788 857 642 309 858 1000 366 859 891 352 860 822 402 861 152 545 862 324 113 863 633 967 864 267 454 865 381 723 866 272 14 867 506 20 868 419 308 869 461 644 870 526 713 871 978 482 872 468 336 873 729 289 874 795 496 875 581 326 876 383 530 877 226 167 878 421 522 879 386 830 880 273 91 881 484 116 882 676 747 883 107 395 884 229 958 885 902 756 886 962 262 887 105 703 888 84 511 889 991 481 890 701 449 891 689 888 892 655 599 893 600 306 894 538 492 895 499 803 896 881 445 897 981 316 898 473 889 899 383 785 900 679 765 901 573 491 902 589 589 903 480 124 904 145 741 905 624 898 906 923 725 907 915 682 908 232 131 909 974 398 910 735 906 911 678 753 912 640 312 913 644 790 914 212 301 915 123 945 916 253 447 917 943 197 918 18 27 919 916 573 920 327 589 921 640 934 922 615 209 923 470 529 924 655 899 925 288 15 926 401 592 927 840 92 928 633 575 929 707 814 930 424 354 931 682 127 932 194 374 933 855 566 934 190 594 935 728 973 936 178 645 937 275 603 938 88 712 939 367 32 940 544 298 941 738 561 942 963 906 943 460 626 944 266 143 945 727 504 946 33 836 947 442 361 948 628 431 949 384 554 950 244 24 951 482 416 952 765 735 953 446 243 954 247 454 955 913 932 956 560 494 957 528 648 958 594 357 959 935 596 960 462 788 961 621 536 962 660 759 963 564 200 964 302 566 965 936 741 966 592 217 967 724 219 968 118 832 969 299 819 970 251 487 971 129 473 972 96 241 973 167 64 974 169 516 975 381 857 976 976 218 977 767 490 978 837 504 979 407 707 980 203 342 981 387 475 982 735 175 983 706 786 984 335 171 985 40 232 986 821 888 987 131 866 988 159 976 989 978 253 990 53 619 991 849 642 992 478 460 993 19 218 994 230 218 995 453 667 996 336 949 997 931 89 998 588 488 999 449 568 1000 566 526
Output
54503
Information
- Author
- Language
- Spanish
- Official solutions
- Python
- User solutions