Back
Close

Gerrymandering

Statement

 Goal

You're in charge of redefining electoral districts in your county, in order to win the next elections.

The county starts as a single rectangular district. A single district can be split vertically or horizontally in two new districts. This ensures that all districts remain rectangular. Your objective is to find the optimal cuts to maximize the number of voters granted by your districts.

Each district will grant you a certain amount of voters, depending solely on its dimensions. The input is a table of number of voters for each possible shape. The dimensions are not symmetrical, i.e. a 5x3 area may not have the same value as a 3x5 one.

Example: in the first testcase, a 1x1 rectangle is worth 7 voters, a 2x1 is worth 8, a 1x2 is worth 10, a 2x2 is worth 41, etc.
The optimal solution in that case is to split the initial 5x4 district vertically into a 4x4 and a 1x4 district. Then, the resulting 4x4 district is split horizontally in two districts of size 4x2. The resulting score is then 39 + 96 + 96 = 231, which is the highest possible amount of voters in that case.
Input
Line 1: Two integers W and H, the width and height of your county.

Next H lines: W integers representing the amount of voters given by a district of shape hxw
Output
Line 1: A single integer representing the maximum amount of voters you can get by redefining electoral districts.
Constraints
1 ≤ W ≤ 40

1 ≤ H ≤ 40

0 ≤ voters ≤ 10000
Example
Input
5 4
7 8 18 39 40
10 41 60 96 81
24 54 114 87 154
39 56 140 135 162
Output
231

Tags
Dynamic programmingRecursion

Difficulty
Hard

Test cases
Small county Test
Input
5 4 7 8 18 39 40 10 41 60 96 81 24 54 114 87 154 39 56 140 135 162
Output
231

Small county Validator
Input
5 4 0 13 37 30 46 11 54 56 63 75 37 66 62 109 169 40 90 133 153 195
Output
256

Chile Test
Input
1 5 1 11 15 23 20
Output
26

Chile Validator
Input
1 5 0 11 14 23 23
Output
25

Medium Test
Input
10 10 10 16 35 42 60 57 85 82 89 116 17 41 65 112 134 128 144 191 207 226 30 56 93 118 170 191 237 281 333 353 46 82 112 172 229 314 348 388 439 500 49 98 194 251 295 338 410 482 487 552 71 119 235 318 388 461 523 540 643 680 80 155 226 323 430 549 618 713 763 837 90 176 305 381 482 614 719 722 805 992 101 200 308 410 556 640 751 909 954 1044 105 220 355 505 550 754 852 957 1001 1125
Output
1354

Medium Validator
Input
10 10 1 18 39 53 58 68 73 85 93 111 29 63 83 107 128 143 159 182 198 227 42 87 79 125 198 224 272 289 324 336 52 80 114 153 241 303 351 376 436 468 55 98 148 273 257 329 389 514 581 605 59 156 228 304 371 381 523 567 589 661 67 160 240 358 370 474 609 640 691 823 80 177 268 368 441 544 637 712 850 874 105 193 287 460 524 630 762 797 1023 1051 105 210 370 454 551 710 832 973 1104 1216
Output
1575

Large 1 Test
Input
30 20 3 14 8 15 28 27 18 60 54 77 75 35 90 45 40 67 75 126 73 130 136 116 135 173 124 144 188 192 190 98 13 16 15 39 27 64 44 51 62 66 62 85 131 144 150 162 162 114 191 123 173 238 171 156 167 276 226 289 249 170 20 33 33 80 74 108 99 132 184 201 173 330 223 305 347 261 469 339 454 335 587 425 403 419 557 467 625 588 536 686 15 42 111 125 164 115 139 210 235 281 371 394 412 311 403 538 452 594 442 468 491 683 533 642 778 598 812 764 687 756 36 21 73 147 200 167 240 200 297 311 378 348 385 517 508 527 563 504 746 712 686 811 918 714 826 930 960 1047 1155 1135 28 65 115 204 160 221 242 314 287 390 429 488 583 640 612 538 574 791 656 857 888 840 916 1050 1126 1062 1131 1082 996 1087 42 36 146 150 217 293 294 351 330 384 505 618 672 588 655 775 839 877 912 997 935 977 986 1211 991 1271 1251 1250 1409 1339 61 40 152 189 310 232 319 363 362 536 563 650 633 749 821 892 939 807 922 888 932 1163 1043 1334 1438 1384 1218 1436 1664 1674 42 99 239 189 359 276 318 412 499 461 612 600 633 867 770 940 890 1012 1098 1142 1064 1122 1388 1386 1425 1630 1630 1523 1508 1533 52 87 180 281 362 310 471 496 472 691 770 640 839 745 914 895 1102 1133 1308 1374 1314 1453 1297 1605 1518 1810 1667 1662 1746 2069 56 110 182 245 343 365 481 484 521 658 674 744 961 996 932 1092 1277 1289 1419 1310 1379 1478 1743 1685 1822 1787 1789 2107 1945 2242 71 62 238 398 448 429 591 518 667 766 741 874 918 1055 1023 1135 1341 1197 1348 1600 1721 1618 1742 1795 1800 2113 1996 2030 1980 2349 71 90 269 345 392 450 669 748 630 779 857 1006 1096 1109 1265 1339 1290 1357 1664 1505 1792 1631 1768 2006 1823 2137 2084 2415 2420 2284 100 103 249 382 523 595 581 721 731 961 1018 1079 1195 1082 1171 1469 1452 1499 1548 1676 1936 1752 1994 2139 2259 2280 2279 2316 2506 2410 96 135 305 477 441 671 595 744 827 858 968 1200 1318 1253 1294 1320 1411 1501 1856 1661 1914 1978 1951 2111 2209 2291 2543 2652 2794 2792 127 155 312 363 462 579 660 714 926 1050 1111 1280 1246 1256 1577 1523 1602 1792 1666 1949 2224 2196 2190 2355 2270 2636 2531 2715 2768 2905 117 117 285 479 657 730 733 877 1029 1034 1073 1135 1384 1401 1511 1495 1868 1738 1887 2017 2123 2435 2543 2347 2745 2604 2782 2916 2796 3068 61 195 365 566 506 651 908 849 1010 1226 1307 1261 1565 1415 1583 1574 1736 1970 2027 2016 2333 2234 2632 2772 2835 2967 2984 3187 3235 3314 91 194 363 417 688 828 977 918 1163 1102 1324 1378 1408 1733 1650 1881 1950 2086 2061 2296 2262 2444 2713 2868 2785 2953 3291 3444 3129 3367 76 113 372 442 791 789 1028 1084 1270 1253 1370 1614 1650 1574 1825 2103 2119 2066 2149 2373 2704 2517 2680 2698 3178 3234 3183 3422 3625 3861
Output
5567

Large 1 Validator
Input
30 20 5 1 20 28 15 22 47 25 33 49 58 87 41 85 54 45 89 140 95 155 109 155 117 95 84 136 85 85 213 205 4 20 21 26 38 61 34 64 56 89 113 74 89 148 80 120 114 150 135 112 128 163 232 187 197 208 286 181 203 232 4 32 30 38 31 51 73 69 121 114 100 157 134 138 135 139 229 194 237 179 211 237 289 264 305 228 340 320 366 261 16 21 39 49 56 55 93 84 134 156 112 190 191 200 221 176 236 255 261 313 356 359 331 332 331 363 401 328 439 498 16 30 44 52 115 139 237 247 350 350 425 315 432 522 568 523 624 701 606 570 639 628 732 739 973 1034 1000 890 1141 879 18 49 78 85 237 198 215 336 331 339 378 540 477 510 688 582 766 655 825 678 735 787 931 1046 1084 982 1211 1235 1126 1040 46 54 49 88 217 305 338 305 401 433 548 586 670 543 740 617 723 839 787 883 858 935 1021 1178 1172 1085 1342 1134 1473 1278 24 70 101 101 311 307 273 345 492 579 533 677 629 761 645 917 873 1039 848 917 997 1004 1076 1331 1168 1471 1552 1530 1573 1593 63 75 112 138 352 313 320 383 544 463 532 600 655 816 921 840 882 919 1193 1193 1061 1314 1252 1453 1427 1420 1433 1448 1726 1688 73 80 134 157 350 394 443 453 583 626 572 725 822 930 990 974 1092 1253 1151 1397 1226 1423 1306 1470 1555 1754 1858 1614 1689 1765 43 111 110 163 414 403 559 455 527 608 725 728 880 986 1077 1200 1263 1189 1345 1365 1308 1532 1605 1640 1705 1739 1924 1981 2095 2268 76 91 102 144 411 542 517 544 605 747 906 926 1010 1033 1160 1212 1138 1365 1408 1372 1561 1642 1660 1770 1895 1775 1869 1932 2251 2327 66 92 140 190 518 475 476 565 708 753 825 824 1038 1093 1151 1272 1485 1517 1496 1481 1807 1740 1832 2028 1972 1992 2312 2192 2137 2427 42 81 176 173 495 562 667 741 740 831 948 920 1050 1084 1279 1270 1505 1636 1736 1672 1874 1978 1877 1932 2120 2286 2215 2286 2662 2763 99 95 141 209 576 525 735 686 952 947 1058 1088 1049 1265 1379 1527 1630 1648 1609 1853 1861 1956 2245 2050 2116 2381 2454 2786 2741 2616 97 155 188 214 533 660 659 764 802 867 1205 1043 1135 1321 1538 1434 1645 1692 1912 2087 1885 2115 2185 2491 2644 2448 2648 2942 2987 2842 134 128 233 202 576 728 824 744 1086 926 1181 1130 1275 1595 1691 1487 1803 1951 1889 1933 2256 2461 2559 2472 2412 2702 2989 3057 3096 3006 125 144 197 231 690 692 732 855 1050 1140 1093 1444 1580 1666 1563 1893 1742 1934 2176 2140 2257 2519 2434 2607 2753 2726 3097 3298 3163 3297 84 131 211 302 605 761 802 884 1129 1247 1379 1434 1606 1474 1898 1975 1921 2155 2271 2132 2477 2457 2538 2683 2904 3005 3143 3102 3512 3632 88 194 280 240 660 859 927 908 1035 1372 1307 1405 1513 1838 1789 2047 1970 2248 2249 2494 2345 2588 2673 2905 3002 3217 3374 3614 3598 3894
Output
4757

Large 2 Test
Input
40 40 1 4 1 9 27 7 13 55 33 51 74 30 40 28 101 35 114 121 46 70 96 152 73 76 119 170 60 101 190 123 192 62 144 184 182 138 167 202 151 206 2 9 21 14 30 30 30 53 30 75 55 66 52 87 91 67 147 83 122 108 170 133 107 180 148 106 197 190 169 269 235 267 267 275 175 181 305 231 332 324 1 22 21 32 15 25 28 72 98 89 68 73 108 105 157 164 170 155 130 177 116 174 141 166 257 236 205 180 284 243 305 342 350 362 195 251 231 215 294 358 6 36 23 34 57 55 72 103 106 90 69 120 106 174 105 135 187 230 174 160 258 192 264 299 210 308 216 359 337 288 314 356 377 359 400 403 452 352 302 457 27 19 20 25 66 72 86 79 66 142 98 133 123 172 196 138 216 165 173 197 308 303 205 221 375 380 309 321 321 290 308 372 364 456 414 501 419 457 465 379 17 41 53 43 38 48 85 135 134 100 152 178 221 172 154 222 282 227 256 291 258 315 281 273 420 417 446 467 420 389 428 412 516 407 419 461 577 592 614 464 22 35 45 79 50 83 182 210 239 309 241 333 401 388 486 539 415 461 470 559 732 740 807 804 852 974 772 1034 821 1041 1159 888 1111 1152 1177 1095 1187 1383 1184 1331 17 42 58 47 77 87 220 281 234 247 380 360 437 537 580 483 532 557 678 703 678 656 852 1003 746 1001 1128 1172 1062 1062 1212 1320 1034 1015 1161 1510 1163 1152 1257 1231 29 26 89 64 135 140 287 344 256 332 443 379 573 637 654 514 561 766 620 634 892 754 891 1069 963 894 1064 1286 1238 1295 1154 1310 1468 1406 1184 1565 1537 1360 1712 1693 63 67 91 101 81 141 379 276 292 365 533 414 513 692 743 758 809 760 932 897 910 1053 877 979 1003 1243 1059 1213 1300 1142 1257 1256 1586 1679 1539 1629 1687 1680 1727 1717 43 43 56 125 129 148 238 273 495 435 492 600 483 678 580 623 835 864 810 776 911 858 1193 994 1033 1281 1316 1438 1262 1464 1280 1350 1380 1648 1628 1522 1759 1954 1978 1899 44 106 88 99 104 175 373 315 357 385 461 577 540 624 790 694 814 999 877 929 1138 1127 1018 1144 1109 1392 1255 1498 1559 1735 1642 1795 1747 1897 1708 1701 1984 2100 2004 1877 57 89 81 164 113 133 326 411 463 568 464 573 677 706 874 936 978 841 865 1046 1227 1115 1378 1203 1460 1348 1309 1365 1781 1439 1793 1704 1942 1943 1749 1747 1963 2038 2220 2278 68 84 143 159 188 182 335 439 498 527 583 802 810 864 843 811 1104 1174 937 1263 1333 1406 1267 1225 1614 1349 1416 1664 1886 1950 1715 1685 1837 2091 2100 2302 2378 2384 2491 2104 49 80 118 148 185 208 435 477 563 702 666 763 731 865 789 975 1080 1169 1139 1373 1402 1420 1464 1649 1531 1626 1520 1724 1838 1761 1710 2038 2215 2072 2394 2257 2178 2306 2430 2492 89 63 119 180 231 255 500 610 734 568 627 696 971 971 1082 933 1004 1286 1276 1338 1214 1299 1679 1628 1471 1596 1624 1791 1713 2166 2019 2235 2107 2267 2349 2211 2734 2438 2449 2561 47 146 156 197 182 258 549 610 769 809 687 761 964 1005 1142 1093 1280 1228 1196 1313 1624 1496 1470 1780 1630 1774 1849 1971 1844 1948 2256 2484 2236 2221 2491 2611 2819 2741 2971 2735 83 120 125 216 264 248 587 509 728 696 739 753 1016 1048 1007 1170 1167 1433 1248 1590 1669 1761 1678 1576 1817 1778 1881 2233 2036 1990 2177 2252 2571 2743 2732 2767 2697 2962 3024 3111 124 131 148 141 239 213 631 740 768 827 804 1090 1174 1227 1242 1198 1242 1371 1332 1530 1537 1809 1922 1704 1722 2231 2066 1985 2280 2352 2550 2642 2653 2400 2934 2676 2901 3131 2824 3273 94 177 145 179 223 309 685 655 791 856 1018 970 1159 1130 1074 1325 1225 1406 1604 1794 1700 1889 1806 2156 2082 2324 2164 2275 2486 2422 2469 2641 2627 2962 2757 3218 2873 2843 3013 3130 123 114 199 214 258 225 536 661 907 825 900 1078 1128 1309 1117 1266 1524 1505 1799 1656 1883 1758 1910 2055 2023 2147 2309 2356 2521 2577 2483 2507 2780 3086 2990 2831 2929 3458 3416 3407 81 100 191 232 276 329 546 805 926 955 1130 1107 1161 1446 1278 1264 1680 1582 1855 1708 2046 1856 2126 2245 2425 2364 2469 2597 2812 2717 2529 2905 3141 3263 3137 3107 3478 3376 3576 3748 47 89 136 299 322 258 721 686 932 1019 1108 1206 1421 1348 1259 1653 1433 1478 1643 1863 1942 2099 2228 1991 2091 2628 2298 2633 2710 2573 2920 3229 2956 3429 3122 3357 3410 3639 3431 4045 102 145 243 214 281 350 801 818 1041 1037 1131 1324 1287 1500 1646 1693 1656 1668 1717 2070 2144 2105 2353 2273 2493 2591 2592 2891 2844 2894 3147 3262 2936 3564 3248 3463 3372 3632 3897 3812 77 185 244 255 329 416 720 905 1015 1011 1093 1420 1398 1454 1732 1823 1619 1742 1739 2154 2226 2306 2157 2555 2502 2514 2720 2868 2659 3262 2912 3256 3063 3350 3737 3786 3599 3879 4124 4022 56 170 234 271 338 423 697 755 949 1019 1282 1146 1410 1430 1671 1747 1908 2020 2182 1930 2144 2341 2311 2329 2792 2551 2869 2680 3118 3167 3273 3102 3415 3596 3873 4052 4197 3940 4311 4359 106 163 268 224 365 453 693 824 1078 1003 1454 1500 1570 1523 1809 1926 2075 2085 2041 2032 2131 2226 2615 2565 2614 2824 3035 3042 3259 3128 3092 3677 3631 3615 3797 4035 4212 4377 4263 4557 86 180 182 296 351 465 886 887 1085 1099 1125 1608 1632 1625 1550 1719 1857 2194 2294 2040 2492 2596 2507 2496 2826 2847 3267 3389 3521 3488 3595 3472 3427 4146 3843 4132 3946 4043 4569 4472 128 207 311 272 267 395 982 985 1052 1319 1189 1610 1397 1616 1965 1862 2035 1944 2445 2467 2621 2590 2865 3041 2878 2784 3267 3155 3341 3509 3844 3971 4093 3684 4277 3998 4295 4777 4713 4599 78 216 228 228 367 462 1027 1160 1253 1341 1507 1574 1753 1947 1878 1996 1919 2382 2572 2402 2673 2477 2793 2838 3092 3047 3302 3133 3705 3499 3587 3575 4201 3812 4367 4204 4537 4770 4902 5045 158 239 246 333 396 404 1153 1279 1379 1198 1631 1473 1623 2036 1909 2293 2260 2480 2530 2374 2807 2646 2914 3242 3101 3317 3142 3200 3519 3887 3811 4096 4123 4162 4353 4623 4639 4413 4658 4856 214 263 182 348 479 414 1092 1293 1170 1306 1466 1534 1723 1870 2128 1985 2280 2259 2591 2845 3001 2730 3217 3076 3187 3417 3255 3716 3766 4139 3945 4321 4162 4393 4677 4475 4874 4995 5227 5060 140 288 287 273 399 486 987 1137 1409 1310 1550 1747 1845 1820 2144 2391 2115 2614 2772 2870 2650 2699 3135 3376 3543 3573 3713 3847 3674 4216 3925 4214 4034 4447 4867 4528 4804 5018 5175 5337 237 278 247 420 484 548 1218 1322 1153 1369 1835 1734 2057 1912 2325 2509 2435 2719 2447 2763 2674 3249 3379 3540 3356 3390 3413 3609 3806 4199 4381 4329 4622 4361 4820 5101 5402 4917 5114 5478 125 193 199 335 450 425 998 1394 1336 1664 1524 1753 1821 2101 2390 2571 2263 2728 2974 2787 2995 3109 3214 3704 3526 3420 4004 4138 4364 4310 4239 4197 4443 4953 4766 5055 5510 5384 5539 5537 148 243 370 462 435 567 1140 1074 1361 1653 1873 2030 2223 2263 2238 2437 2501 2680 2847 2996 3306 3232 3584 3604 3838 3629 4214 3944 4059 4372 4593 4411 4895 5148 4792 5526 5697 5507 5845 5903 132 332 300 301 540 566 1002 1262 1572 1515 1751 2019 2141 2370 2462 2376 2741 2590 2788 2942 3056 3292 3642 3506 3636 3650 3984 4121 4295 4307 4318 4433 5058 5102 4854 5447 5116 5899 5451 5775 173 189 330 412 510 447 1315 1175 1496 1537 1619 2109 2253 2335 2481 2588 2471 3082 2997 3373 3178 3516 3533 3572 3677 4082 3997 4186 4490 4757 4541 5106 4932 5442 5100 5669 5275 5528 5569 6404 208 295 352 491 572 563 1274 1434 1608 1871 1782 1948 1964 2482 2510 2349 2703 2639 3322 3250 3453 3292 3773 3546 3705 3868 4528 4143 4692 4942 4653 4900 5491 5604 5767 5456 5988 6229 5937 6528 151 340 382 386 481 542 1471 1224 1655 1852 1826 2236 2254 2259 2660 2478 3005 3102 3279 3574 3518 3419 3913 3813 4349 4130 4665 4223 4992 4574 5144 4806 5422 5797 5742 5872 6083 6177 6460 6220
Output
11130

Large 2 Validator
Input
40 40 1 1 1 5 4 1 3 10 4 12 3 10 5 14 20 21 16 6 20 16 22 13 23 28 22 28 36 15 35 24 12 25 18 45 36 27 15 48 50 30 1 2 3 4 6 7 4 5 7 14 13 14 20 9 24 22 12 22 27 22 32 29 31 35 35 39 24 37 49 45 24 52 30 37 44 64 34 50 63 68 1 1 4 6 9 9 5 8 15 20 22 11 24 17 25 26 33 20 34 36 31 43 27 52 48 56 32 40 62 37 63 44 43 62 73 53 60 49 77 74 5 5 5 6 10 11 7 20 13 14 14 25 33 21 28 34 44 30 47 43 35 47 50 57 51 51 52 53 52 51 48 57 55 66 53 66 63 85 64 74 5 8 10 7 10 9 12 11 23 20 26 24 38 31 42 36 38 50 54 44 60 48 55 44 61 60 69 74 53 62 78 71 66 97 74 84 104 84 91 112 5 5 13 6 14 10 22 22 19 27 36 27 32 36 45 43 43 49 64 51 69 53 53 62 65 60 71 92 88 81 98 95 106 101 114 119 100 122 117 100 7 4 14 15 16 12 212 250 247 225 288 366 393 498 464 602 464 670 696 730 674 655 605 857 718 682 717 801 986 919 1098 953 1169 1266 1286 1153 1075 1170 1394 1113 7 12 7 16 18 13 218 294 364 246 457 309 541 567 429 448 693 517 566 659 827 724 730 944 815 842 803 1110 1153 1174 1074 1276 1116 1052 1444 1162 1378 1473 1424 1483 4 6 13 12 15 19 232 371 414 330 413 388 494 603 549 519 735 593 835 787 766 837 939 978 885 1094 1020 1097 1326 1176 1128 1172 1263 1376 1313 1393 1440 1620 1605 1459 8 6 18 14 21 20 215 317 297 346 466 489 547 603 588 592 800 808 825 822 847 1005 1013 1159 994 995 1194 1262 1100 1202 1298 1566 1226 1579 1374 1678 1489 1897 1871 1747 12 10 20 14 23 30 318 347 315 505 517 505 545 571 634 860 847 966 977 786 909 937 927 1127 1137 1348 1177 1481 1406 1464 1554 1639 1635 1485 1590 1938 1618 1977 1974 1924 8 13 21 28 24 31 450 499 373 486 419 674 545 639 717 917 966 1014 1086 987 1131 1093 1305 1304 1223 1414 1341 1463 1623 1458 1532 1444 1686 1971 1838 2047 2128 2199 1972 1945 12 11 21 24 26 32 488 395 506 575 479 540 546 711 870 939 962 877 861 976 1223 1243 1399 1159 1173 1508 1418 1726 1465 1568 1861 1572 1925 1764 1971 2162 1825 2184 2155 2362 9 14 14 32 30 30 520 430 435 653 572 616 846 713 803 859 967 1167 1092 1318 1069 1278 1296 1242 1570 1353 1445 1808 1692 1629 1735 1857 1975 1967 1973 2299 2261 2153 2194 2241 13 16 28 24 25 44 458 555 535 552 797 620 862 879 1008 914 1177 980 1191 1265 1208 1308 1349 1368 1507 1759 1558 1626 1761 1916 1836 2078 2207 2201 1997 2369 2262 2238 2586 2689 21 19 34 32 41 48 453 664 714 574 860 745 934 1055 1011 1101 1179 1036 1163 1274 1377 1358 1328 1666 1518 1628 1881 2057 2018 1904 2211 2199 2331 2283 2367 2236 2287 2488 2353 2581 9 28 22 28 43 55 497 524 597 766 917 896 797 893 1056 1012 1045 1181 1215 1486 1464 1332 1671 1731 1571 1959 2062 2115 1976 2060 2079 2131 2185 2335 2515 2728 2789 2544 2866 2824 18 18 32 31 48 59 665 498 624 667 853 1025 829 906 1159 1293 1395 1158 1469 1509 1692 1702 1873 1661 1791 2102 2091 1851 1993 2390 2514 2337 2310 2350 2557 2478 2804 2878 3108 2905 10 31 38 38 51 47 469 665 599 807 927 1008 893 1016 1228 1378 1435 1201 1263 1626 1714 1666 1705 1813 1752 1817 2162 2362 2360 2421 2346 2333 2329 2657 2748 2831 3150 2999 3173 3399 21 15 40 45 43 62 497 689 649 735 992 1034 936 1037 1152 1214 1225 1504 1598 1564 1656 1776 1798 1903 2116 2050 2365 2204 2539 2228 2692 2853 2661 2706 2612 2761 3178 2942 2945 3239 17 31 31 52 47 58 661 808 733 943 989 917 1071 1384 1465 1407 1329 1530 1509 1734 1918 1726 2010 2053 2203 2016 2094 2632 2540 2680 2580 2972 2635 3045 3071 2920 3023 3218 3377 3446 14 35 27 44 45 53 820 726 858 826 875 968 1240 1272 1193 1331 1619 1510 1655 1942 1772 2021 2163 1939 2132 2112 2567 2497 2463 2860 2638 2797 2809 3111 3386 3434 3186 3198 3525 3667 21 22 39 41 54 60 846 726 777 954 1071 1321 1288 1331 1570 1493 1543 1813 1897 1803 2069 1984 2083 1989 2439 2534 2689 2852 2716 2730 2792 3058 3095 2984 3382 3098 3221 3505 3974 3852 33 33 30 39 43 73 808 882 913 1150 1221 1070 1182 1562 1484 1556 1540 1606 1903 1880 2007 2153 2388 2436 2212 2491 2692 2729 3013 2893 2965 2978 3043 3426 3120 3581 3591 3939 4134 3678 25 23 29 60 55 78 632 773 1090 946 1275 1329 1193 1449 1355 1746 1850 1662 1763 2203 2284 2070 2195 2186 2604 2618 2894 2750 2719 3006 3223 3347 3591 3621 3701 3691 3989 3584 4223 4106 27 40 33 54 68 88 658 781 925 1293 1217 1322 1408 1619 1480 1834 1800 1735 2009 2160 2269 2175 2373 2710 2458 2921 2997 2698 2847 3327 3254 3247 3375 3562 3502 3863 4084 3765 4051 3923 31 39 47 61 74 64 957 1039 1021 1238 1128 1533 1446 1408 1481 1672 1884 1797 2168 2017 2150 2310 2336 2679 2665 2698 3049 3035 2993 3138 3261 3208 3878 3449 3544 3685 4108 4046 4480 4501 35 44 46 52 60 73 940 961 1161 1367 1181 1351 1570 1606 1827 1841 1910 2273 2185 2468 2335 2648 2538 2954 2937 2760 3028 2952 3103 3093 3502 3524 3673 3728 4267 4122 4070 4293 4106 4545 35 31 52 75 78 70 794 913 1095 1434 1291 1582 1408 1676 1906 2060 2048 2081 2414 2145 2255 2555 2765 2778 2968 3023 3192 3110 3254 3400 3378 3647 3730 3897 3840 4180 4446 4346 4779 4356 29 40 62 64 59 85 939 1135 1265 1424 1475 1687 1587 1636 1932 1794 1888 2307 2384 2689 2737 2692 2572 3041 2993 3179 3095 3106 3508 3462 3903 3562 3771 3914 4260 4248 4659 4517 4635 5092 18 34 35 74 88 104 1034 1105 1094 1417 1364 1594 1660 1861 1731 1884 2079 2511 2213 2735 2856 2904 2628 3215 3364 3364 3248 3573 3397 3766 4087 3983 4293 3969 4306 4405 4319 4931 4916 5336 35 28 54 62 77 91 887 996 1364 1279 1345 1773 1933 1846 2134 2090 2191 2362 2640 2660 2864 2993 3049 3223 2992 3599 3413 3802 3940 3643 3881 3864 4378 4499 4284 4536 4660 5161 5228 5103 33 29 66 70 76 79 1098 1184 1282 1488 1406 1642 1816 2141 2179 2000 2131 2657 2562 2735 2616 2859 2993 2978 3210 3277 3594 3865 3843 3709 4187 3943 4111 4192 4309 5027 4793 4904 5290 5228 28 35 49 84 92 112 1181 1059 1318 1695 1813 1606 1700 2241 2187 2275 2397 2329 2600 2736 3161 2969 3041 3397 3280 3328 3831 3573 3952 4281 4305 4326 4479 4662 4887 4570 4985 5542 5490 5531 13 34 71 56 65 102 1016 1341 1594 1733 1775 1764 1775 2009 2302 2322 2465 2779 3008 2742 3277 2904 3165 3450 3718 3420 3988 3957 3777 4409 4101 4412 4936 4552 4829 4756 5475 5362 5703 5316 39 27 75 56 90 92 1069 1451 1325 1400 1925 1962 1845 2191 2411 2148 2411 2849 2738 3186 3324 3509 3174 3684 3470 3587 4151 3865 4485 4073 4705 4419 4889 4559 5196 5516 5472 5135 5917 5495 23 34 49 59 109 110 1216 1347 1665 1437 1870 1951 1980 2126 2119 2681 2531 2808 2762 3120 2920 3340 3352 3878 3677 3769 4160 4046 4186 4667 4798 4737 4630 5095 4987 5052 5312 5676 5747 5805 40 31 47 72 78 116 1139 1562 1292 1867 1917 1711 1927 2315 2625 2610 2520 2754 3078 3192 3077 3556 3463 3470 3594 3790 4225 4459 4173 4432 4537 4716 5357 4955 5612 5166 5705 6004 5723 6233 35 31 71 74 83 94 1199 1535 1700 1573 2002 1773 1962 2080 2660 2677 2752 3009 3152 3004 3615 3656 3695 3546 3778 4260 4079 4671 4674 5060 4769 5204 5405 5466 5250 5839 5757 5929 6027 6414 52 62 53 85 102 107 1120 1582 1750 1525 1928 2124 2220 2365 2277 2928 2975 3094 3002 3123 3211 3902 3763 3647 4110 4331 4346 4778 5014 5067 4710 5014 5645 5211 5529 5404 5734 6061 6249 6124
Output
8474

Solution language

Solution

Stub generator input