結果
| 問題 | No.54 Happy Hallowe'en |
| ユーザー |
 14番
|
| 提出日時 | 2016-06-13 05:18:18 |
| 言語 | C#(csc) (csc 3.9.0) |
| 結果 |
WA
|
| 実行時間 | - |
| コード長 | 29,461 bytes |
| コンパイル時間 | 963 ms |
| コンパイル使用メモリ | 117,116 KB |
| 実行使用メモリ | 32,976 KB |
| 最終ジャッジ日時 | 2024-04-17 19:01:44 |
| 合計ジャッジ時間 | 8,118 ms |
|
ジャッジサーバーID （参考情報） |
judge5 / judge3 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 32 ms
19,456 KB |
| testcase_01 | AC | 32 ms
19,328 KB |
| testcase_02 | AC | 31 ms
19,456 KB |
| testcase_03 | AC | 31 ms
19,328 KB |
| testcase_04 | AC | 44 ms
21,376 KB |
| testcase_05 | WA | - |
| testcase_06 | AC | 57 ms
22,784 KB |
| testcase_07 | AC | 60 ms
23,424 KB |
| testcase_08 | WA | - |
| testcase_09 | AC | 87 ms
24,448 KB |
| testcase_10 | AC | 31 ms
19,584 KB |
| testcase_11 | AC | 32 ms
19,456 KB |
| testcase_12 | TLE | - |
| testcase_13 | -- | - |
| testcase_14 | -- | - |
| testcase_15 | -- | - |
| testcase_16 | -- | - |
| testcase_17 | -- | - |
| testcase_18 | -- | - |
コンパイルメッセージ
Microsoft (R) Visual C# Compiler version 3.9.0-6.21124.20 (db94f4cc) Copyright (C) Microsoft Corporation. All rights reserved.
ソースコード
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<Ie> tempList = new List<Ie>();
int okashiTotal = 0;
for(int i=0; i<ieCount; i++) {
Ie ins = new Ie(i, Reader.ReadLine());
tempList.Add(ins);
okashiTotal+=ins.Okashi;
}
this.dic = new Dictionary<int,int>[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<int, int>[] dic;
private int GetAns(int idx, int hasOkashi) {
if(this.dic[idx] == null) {
this.dic[idx] = new Dictionary<int, int>();
}
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<this.IeList.Length; i++) {
if(this.IeList[i].Sikii <= hasOkashi) {
continue;
}
int ret = this.GetAns(i+1, hasOkashi + this.IeList[i].Okashi) + this.IeList[i].Okashi;
if(ans < ret) {
ans = ret;
} else
{
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();
}
}