Гео­де­зист из­ме­ря­ет вы­со­ту над уров­нем моря (в мил­ли­мет­рах) от­но­си­тель­но уров­ня на­ча­ла до­ро­ги, для каж­дой из N её мет­ро­вых от­ме­ток. Ну­ме­ра­ция от­ме­ток на­чи­на­ет­ся с еди­ни­цы.

Про­ек­ти­ров­щи­кам не­об­хо­ди­мо вы­брать уча­сток до­ро­ги дли­ной не менее К мет­ров, на ко­то­ром зна­че­ние суммы всех высот, вы­ра­жен­ное в мил­ли­мет­рах, мак­си­маль­но. Это зна­че­ние на­зы­ва­ет­ся оцен­кой участ­ка до­ро­ги. На­ча­ло и конец ис­ко­мо­го участ­ка сов­па­да­ют с мет­ро­вы­ми от­мет­ка­ми на до­ро­ге. На­ча­лом участ­ка счи­та­ет­ся мет­ро­вая от­мет­ка до­ро­ги с мень­шим но­ме­ром.

Опре­де­ли­те две мет­ро­вые от­мет­ки до­ро­ги так, чтобы рас­сто­я­ние между ними было не менее К мет­ров, а оцен­ка со­от­вет­ству­ю­ще­го участ­ка до­ро­ги  — мак­си­маль­но воз­мож­ной. Ука­жи­те в от­ве­те най­ден­ное чис­ло­вое зна­че­ние мак­си­маль­ной оцен­ки, вы­ра­жен­ное в мил­ли­мет­рах.

Вход­ные дан­ные.

Даны два вход­ных файла (файл А и файл В), каж­дый из ко­то­рых в пер­вой стро­ке вход­ных дан­ных задаётся про­тя­жен­ность до­ро­ги N (1 ≤ N ≤ 10 000), а во вто­рой  — на­ту­раль­ное число К  — ми­ни­маль­но до­пу­сти­мое рас­сто­я­ние (в мет­рах) между двумя от­мет­ка­ми до­ро­ги (N > К).

В каж­дой из сле­ду­ю­щих N строк на­хо­дит­ся одно целое число, не пре­вы­ша­ю­щее по мо­ду­лю 10 000 000: вы­со­та от­но­си­тель­но уров­ня на­чаль­но­го участ­ка до­ро­ги (в мил­ли­мет­рах) на со­от­вет­ству­ю­щей мет­ро­вой от­мет­ке до­ро­ги.

В от­ве­те ука­жи­те два числа: сна­ча­ла зна­че­ние ис­ко­мой ве­ли­чи­ны для файла А, затем  — для файла В.

Ответ: