using System; using System.Linq; using System.Collections.Generic; using System.Text; public class Program { public void Proc() { Reader.IsDebug = false; long[] inpt = Reader.ReadLine().Split(' ').Select(a=>long.Parse(a)).ToArray(); int inputCount = (int)inpt[0]; this.Neru = inpt[1]; for(int i=0; ilong.Parse(a)).ToArray())); } OrderedSagyoList = SagyoList.OrderBy(a=>a.Dif).ToList(); long max = this.MaxNani(0, OrderedSagyoList.Last().Dif, OrderedSagyoList); long total = this.GetTotal(max, 0); Console.WriteLine(max); Console.WriteLine(total); } private Dictionary dic = new Dictionary(); private long GetTotal(long max, int idx) { if(dic.ContainsKey(idx)) { return dic[idx]; } if(idx >= this.SagyoList.Count) { return 0; } long ans = 0; long nextTime; int nextIdx = -1; if(this.SagyoList[idx].Dif > max) { nextTime = this.SagyoList[idx].Time + this.Neru; for(int i=idx+1; i= nextTime) { nextIdx = i; break; } else { ans+=this.SagyoList[i].Dif; } } if(nextIdx >= 0) { ans+=this.GetTotal(max, nextIdx); } } else { ans = this.GetTotal(max, idx+1) + this.SagyoList[idx].Dif; nextTime = this.SagyoList[idx].Time + this.Neru; long tmp = 0; for(int i=idx+1; i= nextTime) { nextIdx = i; break; } else if(this.SagyoList[i].Dif > max) { tmp+=this.SagyoList[idx].Dif; nextIdx = -1; ans = Math.Min(this.GetTotal(max, i) + tmp, ans); break; } else { tmp+=this.SagyoList[i].Dif; } } if(nextIdx >= 0) { ans = Math.Min(ans, this.GetTotal(max, nextIdx) + tmp); } else if(idx == this.SagyoList.Count - 1) { ans = 0; } } this.dic[idx] = ans; return ans; } private long MaxNani(long min, long max, List list) { if(max-min <= 1) { if(Kakunin(min, list)) { return min; } else { return max; } } long mid = (min+max)/2; if(Kakunin(mid, list)) { return MaxNani(min, mid, list); } else { return MaxNani(mid, max, list); } } private bool Kakunin(long target, List list) { int idx = this.GetIndex(target, list, 0, list.Count - 1); List sub = list.Skip(idx).OrderBy(a=>a.Time).ToList(); for(int i=1; i orderedList, int min, int max) { if(max-min<=1) { if(orderedList[min].Dif > targetNanido) { return min; } else { return max; } } int mid = (min+max)/2; if(orderedList[mid].Dif > targetNanido) { return this.GetIndex(targetNanido, orderedList, min, mid); } else { return this.GetIndex(targetNanido, orderedList, mid, max); } } List OrderedSagyoList = new List(); List SagyoList = new List(); public struct Sagyo { public long Time; public long Dif; public Sagyo(long[] init) { this.Time = init[0]; this.Dif = init[1]; } } private long Neru = 0; public class Reader { public static bool IsDebug = true; private static System.IO.StringReader SReader; private static string InitText = @" 345 140 32 4348 48 25211 75 60352 186 6070 219 1804 354 91496 435 9843 436 32324 541 26856 579 27340 661 2514 669 21453 801 25297 862 21733 1002 65226 1036 31353 1044 5458 1169 25734 1232 47401 1249 34429 1251 40126 1305 12150 1311 9419 1352 28220 1387 67411 1434 26760 1462 54311 1468 6193 1479 22968 1487 38979 1489 32430 1499 9866 1766 21179 1793 24139 1806 11610 1858 36179 1917 24503 1925 45950 1961 12531 1981 3244 2011 57524 2134 6235 2135 984 2307 36721 2358 46836 2423 9192 2451 5520 2536 7437 2574 2246 2641 59681 2649 32204 2843 4696 2916 29639 3010 27257 3065 22605 3078 23532 3186 3863 3305 37356 3314 1478 3394 11886 3436 20395 3451 22222 3494 11868 3528 13338 3610 14815 3751 27478 3995 17810 4186 3724 4291 42545 4606 16344 4610 8812 4719 15661 4844 43388 4893 7530 5127 25218 5328 1268 5479 19402 5621 6723 5804 68081 6023 1984 6058 11453 6073 6717 6171 61214 6263 7455 6569 6820 6719 33259 6741 55329 6786 36029 6830 37372 7006 24220 7088 34617 7323 13311 7569 2190 7579 20312 7631 2767 7663 25799 7731 2622 7840 51445 8023 25879 8100 37084 8550 32520 8611 27197 8634 690 8689 520 8732 38501 8987 14510 9107 6084 9310 31567 9333 50409 9376 3372 9437 3478 9521 48336 9532 39397 9881 8342 10163 81866 10217 34253 10288 8965 10327 6423 10412 10298 10461 38815 10795 21114 11077 24911 11212 80812 11351 51532 11583 2793 11587 27526 11619 5817 11633 60792 11693 56952 11917 483 11938 1310 11981 19180 12036 2454 12231 37679 12239 13756 12270 30333 12457 13272 12612 48692 12834 2035 12993 54632 13130 42320 13191 46098 13336 899 14044 11814 14214 27001 14258 13622 14464 12975 14478 22520 14629 1967 14754 28524 14830 49659 15205 32113 15285 35907 15406 33052 15462 3475 15495 45042 15638 33104 15749 27423 15975 21259 16000 18416 16682 57682 17228 35470 17230 18314 17275 3805 17332 35114 17385 34343 17600 13128 17872 4016 18301 7226 18384 20946 18597 13995 18604 12621 18912 59041 18931 17177 19154 75446 19841 64201 19864 35877 20309 86597 20565 21804 20761 57763 21025 3576 21036 23836 21174 66131 21431 35852 21479 16134 21504 691 21615 3350 22082 18318 22166 5974 22170 37940 22303 19568 22421 32214 22628 39319 22662 3679 22808 1586 22905 31798 22955 35710 22963 35151 23015 51303 23245 51530 23250 1717 23386 34236 23606 29987 23871 46709 24009 3473 24348 7135 24849 24245 25173 25571 25268 37840 25269 1194 25316 4133 25349 15310 25627 7621 25774 12431 25860 43333 25921 54338 26385 1585 26464 2885 26608 288 26805 161 27069 32251 27102 37614 27314 28680 27401 34780 27811 14461 27852 30440 27895 18193 27996 832 28818 28993 29459 21988 29793 56279 29815 2749 29899 49236 30137 38403 30325 3446 30631 20495 31110 1270 31316 17157 31350 33377 31768 2654 32234 29825 32304 38632 32373 32000 32428 5776 33072 9067 33354 30868 33780 786 34048 36459 34508 538 34598 19406 34867 9050 34889 18047 34942 25705 36184 2493 36311 60510 36475 7089 36539 41263 36549 76554 36684 5547 37497 9594 37637 16226 37865 78051 37952 64860 38746 9366 39131 33603 39516 6366 40026 6113 40053 53225 40648 8803 41485 28602 41506 27132 42938 9974 43264 18319 43523 6598 43695 10647 43961 53991 44159 6697 44431 80820 44801 4667 45487 7580 46324 74554 46498 34901 47584 47780 47721 22928 47961 19838 49470 46315 49613 378 49668 70627 50699 43967 51369 27386 51687 46783 51700 263 52091 31143 52264 807 52371 2663 52613 33694 52856 3419 52890 30321 52905 81789 53457 54568 54464 34352 55656 62362 55783 12025 56321 16197 58422 2406 58470 57291 59207 5258 59842 68070 59886 54947 59894 7916 60304 61020 60320 68386 60616 3901 60660 32334 60897 15079 62814 6211 63046 47579 63294 18452 65003 925 65346 25590 65791 72218 66571 18567 67408 14748 68350 23636 69238 40860 69334 17446 69453 15642 70649 48933 71953 86803 72901 14836 73669 3500 74150 7686 75246 8679 76201 34544 76481 2860 76841 54055 76996 1601 77702 26938 77721 14325 78516 53765 79235 6380 80039 2532 81016 36930 87331 81897 87421 58439 "; public static string ReadLine() { if(IsDebug) { if(SReader == null) { SReader = new System.IO.StringReader(InitText.Trim()); } return SReader.ReadLine(); } else { return Console.ReadLine(); } } } public static void Main(string[] args) { Program prg = new Program(); prg.Proc(); } }