P15905 [HackerEarth] Sumeet has an N*N table, where a non-negative integer is written at each position (i,j) of the table.He wants to place J tiles on top of the table that will cover the fields that are too
提高
题目描述

Sumeet has an N*N table, where a non-negative integer is written at each position (i,j) of the table.He wants to place J tiles on top of the table that will cover the fields that are too large.
But, there are certain conditions:
Each tile covers two positions of the table that are next to each
other (adjacent) either in a row or in a column.
The tiles can touch but not overlap.
The sum of all uncovered positions is to be minimized.

It will always be possible to place the J tiles without violating any of the above conditions.

Sumeet wants to determine the minimal sum of visible positions. As you are a great programmer, he asks you to help him out.

Input format
The first line of input contains two integers N dimension of the table and J, the number of tiles.
Each of the following N lines contains N integers describing the table.

Output format
Output the minimal sum of visible fields after covering the table with tiles.

Constraints

1 ≤ N ≤ 2000
1 ≤ J ≤ 8
1 ≤ integer value at each cell ≤ 1000

Note : There is no partial score for this problem

SAMPLE INPUT
3 1
2 7 6
9 5 1
4 3 8

SAMPLE OUTPUT
31

Explanation

Cover the cell (2,1) and (2,2) [ 1 - based indexing ]

输入格式

见题面

输出格式

见题面

样例输入
50 2 3 678 190 627 694 469 876 789 563 557 54 860 890 7 846 958 171 877 53 787 294 737 783 897 267 134 714 386 602 179 949 974 666 272 598 179 858 367 295 688 124 219 914 510 787 860 341 938 531 863 72 42 880 96 187 58 323 390 354 988 184 928 372 749 319 873 712 403 926 321 781 579 171 715 254 713 646 528 908 496 611 77 520 426 602 26 872 662 544 481 471 607 502 27 208 528 763 428 613 983 503 215 399 883 217 481 680 685 641 879 939 177 347 925 365 653 641 525 251 228 900 331 934 115 765 208 632 867 80 384 643 891 21 306 159 130 302 571 225 395 120 677 223 495 913 225 188 991 847 675 902 853 531 50 908 156 633 445 928 488 44 743 727 986 200 961 88 11 56 712 957 587 198 49 107 463 252 212 259 431 6 364 427 478 133 779 449 745 632 671 592 741 937 696 796 860 963 310 857 999 973 627 391 105 609 919 627 439 874 431 163 980 775 44 914 164 340 56 687 391 218 928 828 567 505 149 574 131 929 764 947 902 15 544 489 571 889 475 999 785 429 611 320 514 329 870 152 46 947 1000 646 245 664 202 285 914 321 889 260 73 676 277 549 15 354 441 381 299 449 587 437 563 182 742 231 748 297 468 608 615 820 336 137 734 488 195 832 934 941 468 152 215 567 17 443 540 196 312 961 1000 819 306 67 629 944 282 52 97 97 813 423 116 594 695 219 205 579 123 93 107 150 317 89 290 850 312 683 393 491 919 604 321 597 608 599 277 804 742 574 235 484 834 140 957 581 612 575 279 839 999 273 411 487 275 926 425 40 514 671 988 472 842 443 286 383 134 282 368 512 336 60 648 797 1 683 426 166 179 985 678 32 311 89 806 342 715 932 334 665 951 472 528 116 196 475 948 986 873 866 734 699 61 487 110 661 153 249 197 106 729 456 381 550 98 965 91 265 539 635 318 766 401 478 439 104 540 495 974 3 213 119 433 714 249 890 523 624 548 816 316 648 752 442 193 980 649 678 598 696 261 681 315 6 430 151 630 848 339 132 180 430 585 326 776 731 664 703 291 437 245 964 516 351 94 321 240 430 614 426 502 816 250 201 805 972 577 966 479 927 852 187 358 488 225 335 581 1000 833 245 946 810 285 188 250 580 952 486 697 515 39 676 345 968 491 616 323 54 943 774 408 354 157 297 398 764 371 680 322 93 131 165 176 163 358 886 647 269 7 866 732 519 31 847 718 200 680 326 586 914 709 654 58 963 770 57 689 748 389 811 291 114 124 833 125 121 916 463 116 688 604 0 465 946 613 86 868 293 572 577 961 205 15 937 543 88 853 271 490 461 819 209 684 604 561 455 251 942 797 695 600 851 980 481 673 772 568 495 250 854 82 980 692 416 510 737 781 370 999 380 831 550 806 184 366 261 493 74 598 882 19 324 125 46 312 930 970 291 565 588 973 547 164 712 90 292 579 99 873 989 936 362 513 855 808 892 866 313 709 40 363 756 833 633 932 469 767 897 401 17 905 367 946 497 697 524 933 639 981 962 424 439 686 867 715 369 150 678 75 598 854 811 255 397 545 938 102 447 135 596 665 238 633 867 182 45 112 41 668 248 255 33 681 197 58 148 257 322 10 64 31 339 209 845 953 303 702 973 274 428 565 32 572 869 441 975 390 709 265 834 808 33 719 584 671 595 223 42 983 322 672 380 480 640 658 855 308 875 217 666 312 707 648 197 814 491 289 551 633 323 501 537 391 374 300 329 23 320 906 432 278 175 297 731 703 298 431 451 19 780 484 230 617 212 963 447 227 237 73 939 822 994 186 142 794 8 796 412 675 403 789 216 838 403 369 168 669 632 743 535 990 500 335 117 926 790 94 1000 61 50 148 211 861 206 818 79 74 543 974 55 846 719 236 204 829 114 554 73 926 789 377 98 475 533 608 999 76 92 64 649 477 116 330 235 252 580 680 271 752 993 717 959 237 232 344 935 389 877 279 707 201 601 529 579 592 83 190 614 718 651 771 817 793 356 191 658 816 520 400 91 513 176 362 567 718 874 805 95 226 682 629 486 157 560 273 71 243 662 612 643 409 682 968 486 814 733 345 296 67 134 621 528 827 7 132 285 124 874 570 11 994 230 803 708 792 537 951 307 600 777 638 670 428 717 165 485 899 269 889 703 195 244 54 930 62 821 898 695 252 441 632 625 839 106 152 796 661 784 482 934 622 587 641 876 799 645 128 700 987 704 126 262 999 1 774 211 124 29 811 63 287 236 710 572 317 395 84 534 897 355 951 508 146 109 93 970 151 697 707 790 761 104 461 997 267 544 171 900 151 433 315 792 605 951 803 45 344 955 809 3 582 20 123 697 559 446 968 443 103 139 563 962 269 817 554 17 793 900 890 114 303 819 354 117 455 911 560 387 617 931 760 642 207 338 467 93 589 790 337 160 87 147 659 828 912 972 596 839 976 377 831 723 219 255 321 674 31 981 355 942 989 596 191 249 6 540 815 778 458 16 228 5 917 467 486 257 657 753 54 268 378 684 935 102 230 818 946 218 891 203 865 714 67 431 773 338 748 373 808 138 216 848 279 744 326 127 412 463 107 880 482 451 450 609 807 328 729 240 899 545 521 384 941 607 422 169 41 12 86 824 550 647 495 569 493 328 737 454 751 855 451 718 592 406 387 770 158 102 76 928 934 343 227 175 528 740 439 863 658 957 725 423 599 642 191 433 711 3 785 123 33 477 336 15 189 226 627 978 197 581 723 849 939 226 23 508 388 216 958 661 305 244 234 134 701 876 832 270 937 176 36 65 984 724 27 177 205 152 88 567 640 95 213 542 584 699 87 309 827 289 466 899 858 578 449 348 582 786 252 614 342 785 246 89 740 656 126 334 496 709 702 155 715 7 510 727 713 876 470 393 130 975 532 51 285 532 67 303 902 585 407 708 843 269 15 219 536 536 10 54 822 507 191 566 175 885 440 469 114 223 36 164 262 16 610 446 376 186 45 21 776 217 307 302 661 25 827 770 890 1 392 30 863 30 384 539 892 459 409 612 40 467 755 861 293 525 769 560 292 55 530 257 784 434 450 870 912 199 437 911 437 960 120 317 823 162 254 215 654 25 90 421 56 37 13 839 484 675 265 781 293 597 951 79 715 741 399 567 849 216 230 542 596 941 218 654 493 364 838 991 492 51 237 345 434 295 339 166 381 259 516 530 537 54 295 362 111 769 129 954 761 111 913 416 482 468 429 193 553 238 320 217 949 52 746 430 418 391 234 393 639 440 803 397 899 228 174 824 637 474 551 548 302 879 579 729 829 415 751 539 188 321 35 122 403 333 121 87 983 731 230 578 316 22 738 389 79 103 630 975 309 185 870 802 708 408 395 164 447 641 57 122 700 65 624 552 189 691 585 225 864 132 514 666 679 661 530 983 48 605 180 967 329 688 131 773 289 450 473 79 525 546 727 782 953 212 26 869 364 941 614 555 306 314 255 337 417 669 398 427 316 573 937 455 274 209 358 918 249 577 908 92 201 308 254 520 210 417 771 146 243 935 493 763 478 260 702 359 590 629 954 2 501 45 417 631 471 840 958 249 772 705 234 456 58 819 411 485 811 166 209 741 438 229 998 168 482 942 980 245 118 179 82 446 393 9 618 911 825 358 440 196 31 857 1 717 487 557 42 571 834 69 385 566 566 155 174 411 469 633 29 808 370 604 952 32 526 126 436 468 95 959 102 54 866 494 313 159 841 366 751 155 621 410 977 283 97 931 589 130 481 404 754 950 212 169 970 886 455 762 373 248 910 49 846 645 795 440 962 289 777 25 558 569 743 955 540 945 97 201 163 495 152 340 165 887 291 198 764 602 46 516 34 857 115 173 816 973 442 796 911 904 470 896 0 844 989 586 2 476 295 177 154 117 892 489 15 761 180 583 198 764 523 424 814 53 928 529 114 180 311 33 276 491 102 77 550 785 18 955 187 338 884 831 419 581 253 934 399 325 732 843 374 905 968 282 954 370 471 579 910 837 820 165 361 297 9 6 846 360 1 195 953 879 966 867 907 883 625 1000 362 495 317 413 512 465 303 8 503 40 137 593 298 836 120 955 262 307 684 700 10 53 957 29 753 241 618 690 256 392 376 461 423 773 17 488 808 45 972 120 794 82 681 137 592 834 12 984 513 787 110 582 322 471 801 229 516 59 146 683 649 954 461 978 845 732 318 932 785 460 805 157 536 61 813 287 249 923 301 681 802 511 520 453 381 563 558 41 413 98 887 41 629 92 715 256 513 610 477 947 155 399 702 723 316 380 920 93 258 127 62 439 374 86 598 485 104 371 721 397 167 353 125 613 642 90 1000 452 201 672 241 49 58 179 884 19 745 642 847 712 367 789 889 792 243 417 657 603 732 967 776 748 512 977 949 652 258 462 600 126 966 170 215 763 759 651 670 506 322 736 209 782 264 360 726 131 937 877 225 843 564 793 43 107 236 588 431 385 976 655 691 24 10 320 867 701 487 179 50 959 33 662 421 168 209 341 249 825 891 522 561 257 364 906 521 575 112 985 739 258 990 433 860 365 904 233 72 42 585 223 350 976 645 161 461 642 585 474 228 937 412 249 498 438 920 919 590 418 626 96 508 944 276 962 713 328 938 427 534 855 639 407 286 30 319 0 716 49 582 558 154 440 517 879 502 165 922 253 91 297 349 231 389 589 14 889 957 670 439 41 9 771 702 583 180 65 205 658 474 167 898 177 356 927 151 684 931 566 257 852 938 336 4 998 349 446 55 977 728 902 565 749 404 830 520 535 470 762 301 92 158 624 63 73 310 734 976 567 534 308 355 193 506 102 115 804 331 651 575 994 556 448 563 422 431 586 403 175 233 671 492 461 375 508 930 627 664 325 501 521 30 316 587 864 543 328 822 120 525 898 871 224 961 263 210 572 869 218 46 733 403 203 175 603 513 457 852 857 481 225 30 282 821 244 105 904 92 806 461 699 620 630 266 958 392 773 112 611 623 472 632 488 258 660 747 700 369 605 458 265 955 318 765 608 8 641 965 739 762 587 43 709 709 576 633 350 971 678 24 32 264 774 692 437 873 956 272 771 289 195 736 720 938 744 143 971 948 785 67 952 75 185 709 240 799 960 117 526 442 138 74 226 582 352 107 886 881 115 546 924 520 244 941 427 367 661 455 413 855 483 173 31 590 540 472 340 388 726 177 642 292 132 101 24 952 253 70 329 85 314 683 32 280 16 580 255 892 185 772 177 767 470 668 723 309 941 659 981 869 467 739 642 953 119 456 909 783 62 147 71 584 602 295 514 811 248 561 942 415 400 891 906 238 546 892 566 434 122 543 717 765 88 178 162 228 32 884 526 922 709 452 211 942 737 484 196 791 227 279 598 863 80 818 350 495 985 629 594 932 895 537 916 257 39 526 212 921 642 278 455 245 259 992 810 183 682 439 846 403 792 487 787 48 542 725 232 690 690 651 545 875 800 435 135 879 270 937 504 565 699 134 578 578 978 999 199 2 641 804 918 434 177 541 515 961 502 361 707 613 958 411 808 939 274 910 884 659 346 308 155 767 452 992 814 186 65 162 707 865 50 147 239 188 50 881 460 497 550 275 448 34 350 725 350 419 204 270 554 942 84 253
样例输出
2418372