Uzb Eng

C8G. ARQON TORTISH
: 2 c
: 64

2086 yilda qishki olimpiada dasturiga muz ustida arqon tortish musobaqasi qoshilishi xal qilindi. Finalni otkazish uchun musobaqa tashkilotchilari n ta bolakli arqon topishdi. Musobaqa qizgin otishi uchun ulardan ayrim bolaklarni bittasiga uzunroq arqon qilib ulash xal etildi.
Ish boshlangan vaqtda ulash boyicha har bir ulanayotgan arqon oxirida arqonning ulanayotgan ikkita arqon boyicha tugunlar masofasi d santimetrga surilib bordi. Hamda shunday boglash kerakki ulanayotgan arqonlar masofasi bir-biriga yaqin bolmasligi kerak: qoshni tugunlar orasidagi masofa hyech bolmaganda d santimetr bolishi kerak. Masalan, agar d = 10 bolsa, u holda arqon bolaklari ulangandan song uzunligi 25 va 50 santimetr, kanat uzunligi 55 santimetr, bitta tugun joylashgan burchakdan 15 santimetrda.
Musobaqa boshlanishiga kam vaqt qoldi, shuning uchun ular sizga yordam bilan murojaat qilishdi. Tashkilotchilarga arqonni qanday maksimal uzunlikda olish mumkinligiga yordam bering.

:
Birinchi qatorda n (1 ≤ n ≤ 100 000 ) arqon bolaklari soni va d (1 ≤ d ≤ 1000) tugunni boglashga ketadigan arqon bolaklari uzunligi berilgan.
Ikkinchi qatorda ai (1 ≤ ai ≤ 1000) bilan n ta arqon bolaklari uzunliklari berilgan.

:
Bitta son bilan mumkin bolgan eng katta arqon uzunligini chiqaring.

2 10
25 50
5 2
4 5 6 7 8
1 1
1
1 10
1
55


14


1


1
: Arufmetika
: acm.tuit.uz 8-contest


Design by TUIT © 2012-2017 TUIT Online Judge. All rights reserved.