using System; using System.Collections.Generic; using System.Text; using System.Linq; class Program { public void Proc() { Reader.IsDebug = false; int ieCount = int.Parse(Reader.ReadLine()); List tempList = new List(); int okashiTotal = 0; for(int i=0; i[ieCount + 1]; tempList.Sort((a,b)=>{ if(a.Okashi + a.Sikii < b.Okashi + b.Sikii) { return -1; } else if(a.Okashi + a.Sikii > b.Okashi + b.Sikii) { return 1; } else if(a.Sikii < b.Sikii) { return -1; } else if(a.Sikii > b.Sikii) { return 1; } return 0; }); this.IeList = tempList.ToArray(); int ans = this.GetAns(0,0); Console.WriteLine(ans); } private Dictionary[] dic; private int GetAns(int idx, int hasOkashi) { if(this.dic[idx] == null) { this.dic[idx] = new Dictionary(); } if(this.dic[idx].ContainsKey(hasOkashi)) { return this.dic[idx][hasOkashi]; } int ans = 0; if(idx >= this.IeList.Length) { return ans; } if(idx == this.IeList.Length - 1) { if(IeList[idx].Sikii > hasOkashi) { ans = IeList[idx].Okashi; } else { ans = 0; } } else { for(int i=idx; i ret) { break; } } } dic[idx].Add(hasOkashi, ans); return ans; } private Ie[] IeList; public class Ie { public int Index; public int Okashi; public int Sikii; public Ie(int idx, string init) { int[] inpt = init.Split(' ').Select(a=>int.Parse(a)).ToArray(); this.Index = idx; this.Okashi = inpt[0]; this.Sikii = inpt[1]; } } public class Reader { public static bool IsDebug = true; private static String PlainInput = @" 2748 2745 1503 4697 2859 3664 655 1868 241 892 1163 1213 3150 4235 4363 169 538 4742 4319 4950 3772 2021 1625 660 461 206 2633 3119 2997 298 1924 849 343 550 3382 2059 2912 3027 1553 4881 162 1398 2292 3935 4335 965 637 7 1466 1265 4914 4266 2539 1710 731 1707 235 2458 452 14 4933 2391 287 2709 1211 851 200 1513 2369 4912 4594 396 1376 3132 4304 2734 753 3862 1836 1511 4390 1597 385 3257 4199 1262 2768 2655 4031 4469 678 1845 48 279 3136 4793 2879 4036 729 706 4692 1931 373 4884 2769 567 2364 1362 2306 4595 4283 2771 805 2134 1604 2551 1245 803 423 1706 4075 3952 3419 2725 104 4439 4593 1197 2518 781 4766 4536 2154 3922 2437 1412 2839 2277 102 1161 3179 3406 4423 4025 1712 3914 4695 4426 3490 4314 3588 223 4023 240 373 2485 293 3764 1307 2561 1331 2790 1027 239 1398 4573 5000 3518 2270 1924 1083 3766 700 3557 1126 4859 134 240 4369 788 4758 795 2041 3409 3462 4967 3300 2591 3293 2352 1294 395 3056 2930 4041 3895 4388 2751 3707 3326 3474 4250 2404 864 2728 1101 4177 1273 3732 4950 2505 3836 1240 1387 2440 1482 628 4014 874 363 3115 2881 213 2504 3825 2263 2551 865 2282 1037 1986 1396 4612 3601 2926 3500 1075 2480 1468 103 25 3833 4489 1893 3999 4946 2135 3828 848 3226 1411 3996 1232 4070 2586 2041 861 1468 1913 2651 4711 3972 446 813 585 2466 3630 3432 3469 2470 2371 3315 1695 1688 805 2921 3148 4583 2297 3649 3204 396 3982 876 2493 4714 458 2659 2527 4164 3010 2679 1969 3507 1860 3016 3497 2533 2601 4044 1549 4940 4810 4656 4500 2529 1387 3204 1177 2651 2861 598 2921 1026 396 1708 3326 1808 1999 2287 2220 4619 154 3517 2609 4156 4197 2863 87 768 2147 3301 2394 3961 3515 1169 282 432 215 3710 2950 1694 1788 3900 1976 346 572 2931 4721 251 2546 3015 3620 2364 509 3008 3959 370 4234 437 3646 3015 536 1261 1090 2729 1981 2076 2572 3529 2668 1635 4854 3856 1144 3465 431 4115 3782 4949 2499 1628 589 4592 4776 1191 2505 1836 3037 3600 4226 2084 2889 2610 879 4635 1829 2835 606 2517 2289 3644 3136 4610 613 1240 2490 1486 991 678 3275 3645 2375 4584 1197 4037 3546 52 761 14 382 1578 4150 3202 319 1518 4622 900 45 1362 3525 4658 1045 4080 381 95 1259 4729 4096 2027 4274 1809 1783 2714 2289 4267 4386 3868 1887 3352 13 4802 4296 2307 2006 251 2542 1492 2182 4458 3086 3305 1641 3662 4543 3040 3151 2444 1767 3766 2467 1099 2322 4805 403 4281 4540 3363 925 1435 1486 3134 545 2542 2993 249 4691 4519 79 2743 3206 2353 1920 1843 4335 1018 3566 198 3552 144 1849 4580 682 4723 2817 3367 3359 334 192 2210 3091 1877 3243 659 2621 1934 2159 2226 1939 111 4128 2644 3959 2031 1374 3921 2378 2741 79 3923 672 735 3402 4385 1059 2485 1526 4738 1140 2444 3272 492 2855 2183 3100 4886 2425 1218 426 527 824 3688 2812 1935 4339 3658 1415 3679 4533 4925 915 1628 1955 903 2126 4024 4628 4072 476 615 4521 2297 2255 3018 21 3874 1720 337 2002 1800 249 723 3335 3433 4399 963 2027 4483 1956 1208 341 4175 1564 782 4838 4247 796 1574 4924 1307 4341 4332 1961 520 1324 2081 2795 1792 510 1864 706 795 1697 1686 4510 4772 4988 3437 1261 2754 3707 4138 1608 385 2560 3059 1134 4222 1697 4409 3595 3161 2553 1811 2883 1313 3926 3901 3306 1506 1493 3807 647 4992 1659 319 3643 311 3175 195 3739 3689 2554 4557 77 4387 966 4129 1670 4764 714 2216 328 1261 4645 3783 4323 374 1109 1646 559 2829 3533 1049 3648 3757 950 3489 1054 1531 4184 505 4153 4989 4979 3766 3797 2971 4451 1597 3683 1082 589 3476 4589 3384 1304 1775 3472 3634 2143 2544 3336 1953 2396 4463 2202 3347 1835 4671 2924 4712 980 3370 2849 4406 2008 2360 4673 3751 477 3589 3465 3132 837 2893 1683 2440 3659 375 3588 4287 4926 1561 536 4688 2172 3256 1930 163 3462 2793 1704 3595 4846 1365 3122 1868 4204 3147 4721 2411 3068 474 1766 4263 1814 2286 626 3437 3278 3256 784 620 3682 4182 1455 3327 532 1704 3053 420 2699 799 4580 1285 2937 4487 630 3645 185 4397 3506 4803 4690 2241 4448 2543 459 2433 1338 947 402 478 4208 2149 1428 753 3513 4611 346 2786 3357 3748 2892 1405 2512 3890 306 1523 2449 1067 1180 919 4269 1417 720 4015 894 2254 180 3381 3649 4548 2889 4555 2085 1554 4750 4925 4911 1318 134 1207 167 3213 3023 2573 2333 3404 3905 1448 3245 1304 4130 476 1255 1704 4019 2213 2671 3070 2418 701 621 4761 3393 2794 1153 4906 3340 3659 4744 4958 879 3326 3826 4271 4784 188 4426 2318 1053 2326 1083 2680 806 3031 727 771 2094 3857 4947 4410 2355 209 3691 1973 2250 3401 1970 2713 1833 1334 3046 2086 1676 1461 175 143 58 441 3451 2478 4879 245 362 2051 481 320 3164 939 4371 1517 3161 2457 1292 3644 2125 850 3606 2856 2596 4247 1428 421 3277 1726 1734 108 4537 1115 1315 4422 4651 679 4242 766 4379 1728 3620 3262 4167 655 2050 1411 2450 2369 3182 2792 4292 2734 2248 2066 3168 2686 3786 1246 4751 1408 1230 1540 4710 268 2410 2413 3224 3496 620 391 24 3450 4121 4702 1543 3281 3071 2142 2324 3149 2829 4586 3252 3536 3675 3772 3838 3549 4722 3338 2516 4322 3498 3308 455 3132 2299 402 4250 3854 4469 548 2098 1913 2577 4980 1081 3236 4670 1581 4099 2708 3240 4642 4163 4607 4877 3743 3599 3936 180 848 2155 77 1080 134 1996 3761 4162 1288 697 1835 3559 1606 4767 342 3086 2838 3532 2000 1033 4397 3586 585 4642 1771 1002 4108 3347 3225 2491 68 1986 4566 2050 1583 3116 2700 20 4744 2435 3304 1990 2226 781 4394 2643 622 1085 4155 261 1497 3556 2728 1530 858 2660 932 102 1361 1813 166 4678 623 897 3003 573 541 1583 830 4682 3632 255 3141 641 1304 3929 1754 3989 474 4726 1019 109 2317 1186 2499 4302 2727 3147 2156 3010 1689 1188 1716 4912 3383 4432 70 724 4046 3881 3563 1112 3295 4811 1284 4454 359 4947 2603 3559 184 2285 3623 4934 4323 3379 2885 2351 1264 1186 2916 1156 4249 4249 481 870 2669 1977 1826 4706 4805 4274 3633 3930 3704 3111 2050 1786 3454 1160 1022 2564 1382 3106 2503 1348 2111 3141 1415 3900 853 1746 1458 4841 348 2534 2067 3877 88 4696 4821 953 2467 1664 3828 3260 2641 653 838 2387 1926 970 2861 3270 372 4582 3598 1147 2833 2675 2225 1408 3793 4493 3594 4040 4747 3967 1371 498 1074 2707 3508 1083 3570 1231 2753 4752 2833 511 1081 1294 3124 1524 2361 717 3517 2667 3650 2928 3885 4120 4953 3278 1588 273 444 3526 2462 3697 163 2519 4734 2056 4248 4304 2595 2403 2486 1106 3009 327 3408 3301 884 859 1303 4077 2162 3430 3433 2402 2961 2894 1776 3318 1401 1744 4638 4801 3541 671 3423 2797 4488 3970 3390 1757 1636 686 626 2598 387 4717 4516 489 245 2019 3167 135 4626 3135 1312 3893 2965 1126 101 462 193 676 2477 2354 3337 2419 1953 4501 2020 3899 1938 3306 1188 837 4240 4116 2086 587 3238 328 3902 1641 4819 1399 2732 4364 4637 535 4291 3696 3387 1237 4038 4407 4551 1730 768 567 3756 1219 2022 2839 4294 4257 4541 3882 3198 1192 2963 2854 1336 1836 2893 518 3213 1341 386 673 1469 657 1963 4365 2622 2495 102 3960 2311 1912 2065 4575 1692 454 239 3443 3588 4532 3290 489 408 2542 2376 3082 1481 2319 4036 3632 4615 4265 1721 2280 133 2856 140 4503 941 1887 3814 1321 3097 4531 2506 1191 4890 2992 2321 3420 1089 2777 1460 3183 1447 1616 2368 3530 4954 2164 1588 2158 3842 2308 1277 293 4115 2269 1484 1921 3889 3596 3702 3374 1132 2375 3644 2131 1444 653 967 3709 2200 2912 743 4908 1078 4635 4791 4102 1552 204 657 4948 1025 2061 3736 1969 4774 528 3889 2292 2826 1829 1408 3 1961 4733 3513 2486 4868 4921 3878 3951 1526 627 4348 1440 4170 2652 4836 4716 4195 2148 4845 1978 3391 3331 716 4511 4401 1915 2081 678 3981 4552 4378 3847 2855 2044 2338 2342 1825 3949 5 2736 4537 2309 1965 147 3508 103 3507 579 743 4584 629 2277 4564 2519 2101 4898 2103 3201 1569 646 648 4990 3729 4219 1672 2360 1214 4134 3627 448 1603 142 3304 3927 3340 2595 2002 2368 1505 2871 526 2035 982 3817 3884 3140 4436 3253 19 4682 2470 3492 1022 3372 4792 2682 1667 2138 1293 3211 4000 2950 4576 53 3821 2339 2967 3502 1783 4830 2055 2341 3070 4594 733 2892 3247 961 3865 2244 2369 4900 692 50 4194 1436 2828 2790 4772 3838 943 4134 624 2955 4639 4770 2404 1556 3391 3544 2701 950 141 3316 1539 3620 1164 451 3963 1274 1118 17 4838 1564 3982 2614 1771 2184 1422 1487 820 2837 3403 190 2934 451 1763 4399 3680 1440 4624 3498 2715 1830 679 612 3383 2998 1346 2921 1138 795 1058 4174 1785 1155 334 4441 2655 2395 1057 4663 234 1167 2430 3632 3704 320 432 3529 2655 1344 2175 2248 2674 4795 3110 1864 685 3475 3711 4986 3071 1695 4267 4275 3795 4723 1270 4365 3462 386 350 4373 2674 564 3421 4137 1885 2115 3201 2694 3356 1197 1194 1122 2999 3465 4923 2760 2725 2547 1366 1858 3170 256 3193 380 3048 2384 2470 4003 2084 1533 2483 217 4132 2333 2542 2997 4224 724 46 2118 1568 2524 4229 2092 4754 1844 1601 2691 3248 2427 4643 3500 1891 2658 343 131 4033 3995 4275 57 1897 4043 4293 2381 4994 1533 1326 518 3151 404 1024 254 4145 1913 93 2310 2614 4903 491 3302 4936 3575 4390 3337 1196 398 1025 1858 2091 3531 4553 4218 4117 2478 548 3833 1557 2975 4273 4155 3426 4704 4729 4591 2405 4421 1350 2497 2230 3172 1104 2466 3587 1287 4491 3934 4027 2829 3145 1232 2286 4650 1424 3165 789 1539 894 4182 3494 1536 1933 4861 70 4758 52 2266 2107 4426 2910 1681 4480 3833 4338 1153 4508 2860 1141 2143 1304 4340 1551 3944 1109 4946 3352 1161 937 2596 1980 2702 4790 4296 1979 4163 56 3462 3735 2946 2508 1407 4239 778 4126 821 3128 725 3607 2820 1340 1233 3939 3653 4433 1923 3518 1402 4096 2750 2345 477 2256 3007 625 1981 765 4460 267 3029 1237 1505 2009 3185 2681 2525 357 1424 2021 3127 695 3718 3143 2479 2373 2757 4268 591 2808 4521 31 3050 1489 3012 1953 1893 2719 2232 2874 43 4238 3420 3388 2978 2871 4089 397 257 1728 1891 3178 1498 2497 4984 135 3739 1129 2969 817 4651 811 3666 2325 3137 4114 825 729 4839 628 2184 1158 1333 148 4158 1355 2305 2528 570 2410 3035 2999 4539 1299 3689 2866 2362 2651 2487 886 623 3677 4907 929 1072 1485 3042 3950 4887 501 665 1507 2866 4761 4856 2597 2021 2400 1364 3968 1759 3272 4620 1362 3873 4979 1186 2709 398 3232 833 574 4886 1879 3627 1503 2068 1761 4829 2078 4318 945 2852 821 2912 2633 1421 647 2109 3946 778 2704 2462 4836 3794 4562 4197 1981 953 2114 502 3823 8 1987 207 3039 933 2004 3975 2919 3283 4438 1942 176 27 1514 4094 30 37 4630 4793 3438 4017 2826 1094 2650 3531 3423 1240 946 2681 2191 2073 2201 1824 4414 894 4558 4732 4573 1204 1875 1687 4985 105 3104 3098 4144 1167 506 43 4229 1046 1509 1283 4633 64 3457 1511 1252 282 2021 3939 4113 4196 151 4606 1792 314 4377 1678 3371 4046 1687 204 1983 4233 4962 1558 461 3536 890 3967 328 3646 943 674 1351 1094 1308 4490 2653 3280 3914 750 2867 393 875 1094 4879 2233 3778 1673 4283 3647 420 4350 4949 1654 2512 1446 2956 1230 1753 3603 3130 1766 3943 4146 2425 2977 4797 4006 4228 2508 4874 1066 3219 3955 3137 827 946 1775 4736 3399 2436 680 2368 1069 4741 3173 432 2466 2854 2705 862 1810 4047 1435 196 744 905 4285 2901 945 4671 3187 103 3658 369 1334 4654 4486 3484 3516 4326 3390 62 207 4139 4907 4287 4894 366 1770 4076 1951 2125 2541 3857 4382 3240 4632 2400 3514 1932 1444 1761 2632 3086 4911 2833 1096 2218 2721 4438 4199 3680 1134 2186 231 3106 1776 2461 2808 164 1900 650 2422 2518 1585 4633 2760 2635 400 3127 4164 1113 1651 3748 3394 3350 1040 18 952 1057 1947 1455 2591 3988 2716 2647 1441 720 2823 3607 2620 789 388 80 286 4511 539 2936 2246 4427 3161 4536 2276 4255 3822 2633 2911 3149 3203 2006 342 942 4609 2654 3956 2056 487 2953 647 3187 898 199 2343 3400 3519 177 4479 1469 1499 1790 1024 2423 928 2014 3892 53 1279 1839 2161 577 3033 4055 1101 1521 1423 1416 1663 2919 1280 1467 409 2006 2109 1154 138 4118 1751 1841 1091 3554 4974 3908 2140 2758 1782 177 4973 3498 4703 789 817 1599 1078 3292 3675 4399 3094 3690 3426 1992 653 424 2354 1875 4989 3285 4913 3956 4301 303 4555 1606 3526 3707 1742 4268 3319 2241 1244 897 2281 3858 1413 3518 649 125 1417 4456 3995 325 4663 4284 668 3283 1686 3454 4746 3398 2170 1439 382 2324 3160 1516 3624 576 697 2159 1888 975 494 1006 1202 1244 2 2361 4581 1856 440 2895 333 1914 1494 3155 3709 4907 388 3496 125 3539 2611 385 4608 1853 1380 1587 3234 926 2089 2484 4112 3737 4805 4784 2995 4209 829 1691 2401 1005 2543 4544 274 3660 861 1130 4829 2076 1617 4841 356 1875 997 375 4060 1635 1515 386 2619 1502 2089 4915 3190 4094 230 1251 222 2235 2502 350 412 835 3698 1878 3552 2769 285 256 141 1839 2782 3769 4707 1735 2759 2387 4500 3282 2153 2578 868 1466 1713 1316 2493 2514 1413 1965 2010 4562 3172 1622 2179 589 607 3294 3042 849 4740 4518 3732 184 4829 2222 2129 1278 864 2118 3265 3305 947 254 648 753 1952 2618 3934 3659 3643 1609 939 3625 2207 1321 1932 2936 2825 3116 811 3839 3168 1801 626 3554 198 2388 3506 1320 435 3470 1298 2591 4205 2242 3674 2193 4786 1500 3636 2738 4858 2195 3772 2884 883 2317 3376 1117 2949 842 1142 1956 2111 2904 3271 688 1988 1142 3992 3798 3626 4721 1861 1845 804 3916 4410 4903 2572 3357 2372 3460 87 3376 3537 1552 4568 2966 1412 3301 2370 2124 3024 2156 3988 103 4067 2292 1808 1859 2960 3378 2247 4863 3395 494 2912 4978 4482 1447 3313 3086 3300 56 830 1379 449 3714 3915 1989 4266 1655 99 3999 4624 619 2482 2768 1428 1052 3811 1086 4033 4714 649 2627 4040 1532 1033 2745 322 1273 4310 160 4480 895 1885 4042 4191 4340 2560 2260 3533 3607 2152 1840 2222 2757 2570 2530 1875 4465 2435 2578 2725 2844 1356 674 324 4842 863 3410 1533 2908 1684 4505 3673 1171 3112 4471 35 4695 3819 1029 4626 2830 4004 561 1130 3231 2675 496 673 3012 1320 1197 4174 4236 958 2463 2504 1456 4470 3802 2471 2433 3287 685 2930 2177 3641 807 1309 4644 3895 4066 139 2425 3615 2551 1072 3498 1452 4015 3496 1164 928 4171 3472 973 3752 4303 4070 1289 3277 1126 4559 721 2484 2881 466 4666 1025 4612 719 4348 4083 1231 3616 2812 2508 4853 3543 4375 1696 503 1629 3710 2351 2225 1095 592 638 70 2908 1814 378 3200 1816 1947 316 3169 2310 3781 2821 358 3011 2860 4483 977 1235 1829 2432 3073 3641 1113 3886 806 3202 4928 4805 3067 931 4056 775 1105 1629 210 4660 1670 2113 869 3544 605 1258 3082 3130 3536 1487 1106 1717 1265 3901 4540 75 4536 3870 3510 1852 4623 2970 3082 4320 4741 3404 4375 3482 3791 4548 1453 4241 721 1647 1372 1074 3609 591 144 1565 4881 865 1775 3145 4420 2243 246 2356 3174 2417 3520 3077 476 3115 2754 1127 1341 1195 3380 2897 2297 3830 4873 1731 3776 145 3793 1252 3148 93 1241 2169 3204 3987 3587 92 3401 2031 4207 4771 3655 3394 2904 1121 2732 2589 2501 3223 3592 63 4126 2892 4008 2297 1665 3800 676 4284 3502 2545 4218 1848 2616 4767 4340 4876 2471 2572 2002 2497 1569 321 2251 1571 3383 2679 3174 2494 358 3640 1791 2262 1453 4738 122 391 856 2576 2861 1836 3266 102 3131 3321 822 1265 3710 639 2125 3024 1480 66 995 1489 1943 4057 1821 1766 4627 4995 4658 3899 3611 58 3181 27 3928 4797 1230 1344 4025 4036 1868 689 3104 231 4660 4389 4993 4719 1478 1541 1107 4999 510 2797 4262 1476 2922 3534 4131 3266 2692 1155 4272 1839 4461 1345 4259 1234 1714 2072 3767 3673 1512 3506 641 1696 1185 1365 2418 3994 1546 114 144 3449 3048 1426 373 1103 1952 209 3162 4977 4702 1538 1572 3326 2759 3203 1619 3895 2711 2251 1733 1401 1483 4381 224 182 3303 38 4161 2224 4178 3372 3748 2417 4207 3394 3895 4474 4973 1669 2415 1809 701 2181 3281 1383 991 715 4487 4053 902 3547 4742 2777 584 846 4798 3718 1447 4938 4363 2345 202 3333 302 134 4711 2813 2958 1975 4103 3142 3623 2509 2630 4442 4402 2922 1303 3541 3295 331 4997 4778 4395 3520 841 588 4567 2909 1835 783 1254 112 4459 647 2665 4336 80 1707 4000 1892 293 2537 939 1981 4342 813 1789 1404 1992 2571 4589 3121 4943 1698 2686 489 4978 781 1574 229 3808 922 3896 1587 241 4860 859 963 7 2892 4803 1449 1126 4903 4359 3907 1922 3028 3635 3446 73 1871 2853 678 2096 1102 3090 887 161 799 2602 4101 3759 3228 36 1980 614 1164 3671 761 4940 3430 4265 2306 1128 1513 2708 4407 1840 3858 1321 3012 1992 3383 2521 4359 2843 1751 4640 2191 511 802 2859 260 3127 920 2575 3328 4142 1167 1687 1292 2372 1142 1410 3034 2108 1088 3662 4236 4431 95 1124 716 4983 1875 2658 533 3182 4606 1501 296 888 3709 2971 2901 2993 835 2148 3536 2502 154 4253 1865 341 1696 1141 1063 1014 634 3333 2008 208 4230 3295 712 1565 2647 1820 1646 1765 4883 522 3390 4443 3039 1778 3119 2742 1642 3317 4250 2492 3360 2852 3865 632 3756 4225 1604 2802 3422 2898 967 1516 2325 996 2688 4694 4491 584 3949 3887 3423 4280 4048 1439 4146 2426 2124 318 4492 1880 88 4943 3742 3421 3995 4191 4692 4020 1042 840 1591 4780 1784 2004 572 1600 1455 1047 406 4264 4383 3945 4881 2117 2047 1845 1315 4261 1745 1552 3611 789 1716 3011 3760 82 2939 1240 4371 2442 2299 2313 878 884 3888 1437 3046 2860 1632 4958 3561 3293 4127 3844 227 1657 406 4196 3254 3027 4726 1080 4336 2187 272 2377 3657 2805 1917 3606 4501 2663 4675 1162 4979 376 2845 3344 3149 1431 4934 498 1024 3785 1307 4864 1063 3318 2152 3224 4451 1858 2296 2337 1097 3053 635 833 3746 1494 4666 1751 1046 1056 659 1033 2041 4521 1256 2987 1241 1267 2552 4200 2730 774 358 483 3266 309 299 3759 4922 580 1529 4139 2826 1964 1045 4767 3197 4004 2321 4015 2210 873 2211 753 781 1066 698 3170 975 4372 134 924 3215 1627 556 2661 2436 1615 3559 3396 825 805 4994 1338 3324 4467 1569 36 2836 571 3712 559 4485 163 4020 4822 3732 674 2205 379 1805 1417 2862 370 3596 2133 1205 4073 3662 473 272 1439 3467 4333 182 2070 4060 4566 3916 4748 4437 2185 3569 4520 4263 1426 1233 1422 120 2914 2772 3755 203 4727 3128 1737 1312 2764 981 3809 3116 833 3059 1605 4176 2347 1224 4076 1911 4823 95 1417 4029 377 1137 2875 2520 511 4155 449 871 4297 407 4390 2054 1117 3305 4024 110 2622 3944 4019 3944 4310 1697 1007 2562 2916 389 2612 4350 2574 2431 1034 1696 934 1700 4502 61 2245 2426 4067 3245 863 206 2472 3753 2107 1123 4475 2794 3552 4706 28 3992 122 1716 2898 656 4298 1875 2433 4568 4749 2415 1520 390 4040 3519 2961 834 305 1165 2272 2599 2819 3976 4743 4485 3989 130 2671 4223 1933 256 1400 2837 519 1221 691 419 1535 374 1370 4042 3821 912 3073 1244 3348 2676 1473 814 3828 1592 988 3779 3734 880 4805 2201 261 2763 2766 2061 647 950 1460 640 4196 3438 744 2143 3864 1935 2975 44 2351 2214 2919 2887 1469 3332 2610 4943 3256 3619 173 4642 1772 1626 3746 784 3927 3511 1362 2788 3726 3160 2772 1311 201 2476 1421 1218 413 4601 763 588 3661 4438 1945 2266 4392 889 188 4647 2925 2917 4447 4208 488 3693 3609 908 2156 4673 3542 456 1164 1082 1080 2491 4823 4815 910 790 1710 1338 1525 4323 1109 3776 741 4475 2330 570 876 3417 2884 4950 3743 2935 1668 79 1181 2085 807 2222 4530 708 1421 205 202 4859 3975 4024 1329 2788 4483 2746 228 2864 3486 85 2520 4076 4490 3905 2998 2951 2462 3489 1473 2629 2723 4102 4626 3406 1315 4257 4510 2543 4087 4939 374 3241 3562 1190 1580 4834 2273 2056 3993 3069 4022 1337 447 438 270 625 58 2367 3066 1092 2717 3483 1131 2721 441 477 2444 4561 4081 338 233 2906 2569 2048 339 3573 1494 537 4331 4914 2663 1749 503 4405 1857 4573 4380 3471 1458 2984 2722 4061 4928 739 3434 900 3247 1034 4398 3748 2862 3627 2931 3387 1251 2521 755 3992 4728 652 333 1447 3445 326 4007 4703 1861 4974 3391 3410 2932 1163 4847 4372 3660 3486 1280 4509 915 1767 2800 519 3736 2130 456 2435 3106 4300 289 3421 2941 2636 3385 3113 2137 1935 3748 2169 3862 4961 1208 2763 4183 1724 3769 1073 812 3081 2018 4249 2522 3818 32 504 244 3533 4655 2139 4214 3807 767 4317 3739 1065 3831 1844 3436 3459 539 1103 4447 4030 971 3739 1229 4418 4480 3657 2897 3704 1351 3129 1633 4485 1441 208 4621 1534 2002 1558 3192 1940 3178 2165 4885 1445 1364 3967 2831 10 1361 1346 189 704 879 4886 954 975 4125 4912 1824 2535 526 4962 2427 2607 3901 3555 3973 1627 4820 1811 2781 3592 3469 2752 2284 4893 2934 1409 2576 4353 2551 3307 3835 4390 1442 2948 368 212 2737 738 703 2072 587 1406 1144 144 4248 3528 2108 2151 184 2825 2400 1479 3834 2655 4232 1198 3964 2693 4245 3769 4103 4341 2392 3741 1656 2629 3074 3713 699 4436 2171 2062 1170 35 373 2454 71 1405 4500 3091 4000 4245 4152 1793 1987 459 4439 2764 354 1216 365 1861 2577 3977 4605 4015 1608 1776 439 4571 456 2977 1734 3575 1358 954 3663 4750 371 1095 3906 128 2755 3005 4786 4160 925 1195 1322 1930 3803 3314 2642 2795 130 482 332 948 4005 4463 4977 1697 4959 2735 3629 2698 77 4432 2972 2256 3579 1074 4125 1449 448 62 1125 3424 1681 1501 1059 4167 2915 3607 4259 496 2149 1288 4312 3623 2125 4489 3434 2195 345 2197 1711 1362 3548 2091 1451 1557 441 1412 4400 4808 3194 3779 1437 743 1566 3002 1928 4658 2615 136 3756 271 1011 4752 1826 3848 1699 1789 2083 4311 363 4149 2851 2797 2293 4113 4047 631 4263 3402 1967 2341 4002 2484 274 1503 393 1422 2399 756 4368 1779 3001 383 3442 778 3761 4533 4218 4252 1726 3435 32 4823 359 4114 183 4992 3457 81 1024 4290 246 633 238 3675 4262 2548 2195 3906 506 2816 4689 459 1734 1059 4001 2776 3554 4577 4163 2448 4902 3679 1037 2535 4928 3521 3042 318 3895 3054 1846 4592 178 3545 1248 2394 1356 1225 4930 2076 1986 913 4463 631 1196 3449 2169 3468 3544 2750 2662 4764 2802 2519 1368 3274 588 4662 4307 2097 206 1354 333 522 2207 288 3673 1257 1039 3746 676 3305 4686 4931 1562 3556 4342 1015 557 2055 3210 3090 74 461 4394 1005 1694 784 3196 589 225 102 4801 244 2268 4009 1406 1254 1930 4648 2991 369 3807 2709 1742 543 4263 3862 133 873 1725 215 1809 4297 4998 3125 247 2032 977 3604 3927 4858 2118 1768 4934 4438 182 2810 3248 4104 1370 4567 1706 4894 4670 3370 1025 3555 2966 886 4412 2566 1114 4456 2905 629 2207 2040 3574 4185 3821 1588 299 2264 3180 3112 2800 2792 272 3230 2516 2601 1615 642 4573 971 1235 2280 3356 140 2713 2308 4862 1784 3589 2324 3294 1808 2012 3966 971 3643 2062 4395 2211 1691 2344 3196 977 4178 4199 2930 2872 708 2567 1807 907 2732 1247 4501 1998 445 4012 2565 2544 1526 1102 4941 3823 4429 3540 2830 369 1655 3097 4455 497 3602 2683 4623 690 2051 3233 1339 4551 4431 598 2123 4443 2233 2358 3052 904 3084 4456 3547 2521 3201 3960 3411 4604 2365 4456 4825 3693 81 2451 1899 513 4654 1874 2561 411 214 2277 161 2716 3920 2409 3283 1785 1218 2751 2024 4251 2997 3642 89 1056 172 3216 1557 2122 3687 4594 1419 1723 2495 3077 3975 3225 1940 2205 4819 2293 2265 1243 1478 3949 3326 4069 1253 4308 4691 4749 409 4725 204 3901 2735 1906 1237 1661 2513 738 1579 1024 2774 3671 3364 3903 1426 1333 4365 2638 436 3934 2241 1291 956 3389 903 2731 4593 1025 3818 3915 4155 3095 1923 4314 299 4183 1561 941 1667 1088 1765 2040 4080 3955 2781 111 4342 2903 3643 418 4325 2971 3953 3444 3642 13 1879 3520 1923 4905 630 1140 3945 1539 578 541 4704 4305 3539 2279 3444 2871 3932 2574 2291 3687 4276 2658 4990 27 2433 4736 443 2010 1513 2048 4864 2564 1564 4099 1061 150 2051 220 1196 3253 181 2945 606 4528 107 3317 4441 4539 4661 3540 779 4365 3186 4529 112 4996 2094 4945 992 1385 3548 611 3727 3621 1224 4409 2315 2928 745 3419 4785 821 3592 519 2308 561 2989 3563 411 2376 4363 2600 4391 1273 3095 1239 198 1495 2577 819 4165 2252 3610 2497 1704 4316 4202 4090 3432 3065 272 2519 992 858 3161 3110 455 762 3393 962 4588 1476 715 3853 2422 4088 2837 3062 3227 3322 1941 2372 2923 2512 4274 3985 3829 2194 4799 69 3717 4192 2065 2865 4171 2424 2245 4449 1015 4410 2644 2069 4870 1110 1103 3958 1997 2196 1570 1505 391 3115 2996 1719 2301 3064 2436 2192 4986 4717 2405 1832 4804 4849 1719 2891 638 1700 109 3476 4049 1574 254 3344 2339 1990 1571 2177 4358 2207 4413 2520 1279 3613 4584 4496 2762 1902 3285 356 3794 913 3383 1869 588 3050 2107 1639 3287 448 2702 1476 4755 2047 1942 1055 3639 2934 4766 1842 1570 190 1149 3950 1040 3926 4981 3326 2072 3525 487 2992 1589 3673 3207 3791 3821 1799 797 1762 4427 723 1813 2500 4316 874 88 2298 4689 4413 4394 753 1128 1102 499 4720 2024 3327 4928 835 3222 1196 44 3396 4010 185 1361 629 1866 3067 4299 522 4339 3367 105 4602 3012 2955 4137 4627 3257 1500 3680 3000 983 2935 2455 3258 2382 67 2792 4723 878 4526 355 1027 2675 3019 1479 803 4110 2725 1621 1267 3059 2770 4531 4368 3133 4237 3434 1800 2874 3719 326 4709 2470 3061 1189 2662 4153 2703 4364 2381 3868 4887 962 1241 4460 4356 4253 4275 3539 3936 4643 2907 2883 396 624 2248 4169 1980 6 3135 596 4273 479 1216 3649 4290 1017 101 3314 1454 4769 2562 1208 1163 2489 4898 871 856 583 1365 4970 1497 2808 4865 4094 4584 172 1190 2789 1610 3789 3985 1115 1183 4200 3163 563 3134 2939 2956 4306 2070 23 1603 4152 3330 278 325 19 1678 2489 1755 2450 4647 4628 33 1409 4115 4764 1072 104 2654 2787 4818 4718 2811 4937 4028 3893 2774 4243 4196 1535 4723 703 1694 1795 1369 4203 144 3687 2142 4270 1165 3308 830 3512 3201 3654 3051 2726 1440 3711 1257 682 1419 1596 280 504 1568 3535 3241 3669 4498 340 414 262 3704 2691 2010 2194 464 2000 529 1428 3200 1370 2908 398 2481 4162 4342 1922 39 2033 1775 4379 3699 4991 4293 3058 704 3581 1297 4652 3600 4939 2408 455 2051 24 806 4933 4941 3188 536 4831 3877 1832 2339 718 1223 4382 4702 947 4651 3431 4962 3995 620 704 3840 590 314 211 2528 4115 3397 845 178 1411 4127 2801 2048 4259 1188 952 1871 2640 1330 301 810 3165 2908 3228 3256 1190 734 2609 227 2789 3731 441 4301 2409 1467 4996 3143 4347 269 4253 3379 3821 1774 589 3999 2749 2065 1920 1487 2492 3187 3485 2825 2782 1545 4638 1454 2281 2356 1804 4480 4533 1824 1512 2450 1137 4573 1113 3975 431 4154 907 3330 764 2308 4281 1971 2003 4321 710 2972 1426 4122 4049 1751 873 39 860 1763 3414 3935 4260 58 826 4193 372 843 3709 2964 4963 4199 748 1854 1931 4527 1655 1594 400 1727 2112 2102 81 1573 1071 1087 2136 1822 4219 4062 3962 2612 3049 279 2483 4233 846 13 2516 4109 3865 399 712 2248 3045 2084 4133 3667 825 1679 1442 719 4820 2821 3691 2370 590 3716 1033 3600 1118 3903 3059 2126 4497 2424 3788 2804 1048 1334 1218 4633 3666 4994 226 1439 3565 4755 2294 3696 3232 462 4742 4657 2882 2899 3945 4094 4870 2407 4517 390 1743 1812 4772 3114 4876 1779 631 265 2301 2180 2619 131 1492 2079 931 2810 1755 1998 910 375 4797 928 2391 1909 3103 857 2443 1088 471 1579 3346 3119 308 2328 4400 1834 4956 61 3216 4065 1961 1271 4660 623 4063 3481 4073 2655 3026 3424 2925 3868 4870 2427 4678 3236 579 280 532 914 1828 603 3415 1161 1559 3095 321 3027 2372 2544 1899 439 3401 850 2367 2297 4951 729 892 2276 2089 3126 2923 2843 3328 1501 4566 4351 1624 143 2442 102 208 4914 3074 1632 4078 3673 4113 3721 726 2096 1874 4331 461 4131 1980 774 2098 4694 4210 2435 4357 914 2306 3600 4796 4768 711 3825 2890 4997 3535 548 2920 4793 2105 4629 2902 4831 3900 3298 2062 1529 2640 889 4359 3852 1433 1258 1848 4143 2920 17 2904 295 3926 1716 2504 1354 1511 3807 4175 2523 1139 4053 274 4325 4856 1941 3960 826 3414 2342 220 1738 4756 1054 532 4450 4678 3091 1966 727 1893 4399 3507 683 3713 3707 4265 2373 2689 1090 2428 944 490 2506 2806 3041 42 1699 2827 2179 4292 2746 2570 3152 1381 3719 2919 340 2356 1193 1177 2893 4793 1023 237 1357 1753 1212 3091 4963 915 1004 4444 3804 3261 1217 1243 2722 4699 1500 293 1433 4080 1594 2627 2975 2102 1978 3194 2817 1326 1901 2698 1217 2298 4679 4128 4646 357 196 4929 3369 962 1637 744 4610 1199 2884 1732 1895 4800 2477 2250 4400 2477 1312 1044 736 1542 953 2425 3063 523 705 4280 2674 3241 5000 2410 864 1588 2674 1031 4578 3892 897 3155 3837 2355 4717 3818 489 38 1830 1391 4397 3282 "; private static System.IO.StringReader Sr = null; public static string ReadLine() { if (IsDebug) { if (Sr == null) { Sr = new System.IO.StringReader(PlainInput.Trim()); } return Sr.ReadLine(); } else { return Console.ReadLine(); } } } static void Main() { Program prg = new Program(); prg.Proc(); } }