KBO Juniors 2025 информатика олимпиадасының финалы ежелгі әрі күн шуақты Түркістан қаласында өтті. Бұл жыл ерекше болды — қатысушылар саны рекордтық көрсеткішке жетіп, барлығы \(N\) адам тіркелді. Ұйымдастырушылар мұқият дайындалды: аудиториялар әзірленді, компьютерлер орнатылды, тестілеу жүйесі бапталды. Бәрі мінсіз көрінген еді, бірақ дәл олимпиаданың басталуына аз уақыт қалғанда жаңа мектепте, яғни финал өтетін жерде, барлық қатысушыларға интернет жеткілікті болмайтыны анықталды.

Тексеріс нәтижесінде белгілі болды: мектеп желісі тек бір бөлігін ғана қамтамасыз ете алады, ал дәл \(M\) қатысушы интернетсіз қалады. Ұйымдастырушылар қалғандарына мобильді интернет беруді шешті, ал осы \(M\) қатысушыны қосымша роутерлер арқылы желіге қосудың жолын табу қажет болды.

Мәселені ести салысымен, біздің кейіпкерлер — Kalashnikov, Serikbay және APMAH — бәрін өз қолдарына алды. Олар роутер жеткізушісімен байланысып, оның қоймасында сан түрлі модельдер бар екенін білді. Әр модельдің әрекет ету радиусы оның нөміріне тең. Мысалы, PT-LINK-10 моделінің радиусы \(10\), ал PT-LINK-1732 моделінікі — \(1732\). Модель нөмірі әрқашан нөлден үлкен немесе тең бүтін сан болып табылады.

Жеткізушінің әр түрлі модельдері бар, және әр модельден дәл \(P\) дана бар. Біздің кейіпкерлер үйлесімділік пен баптау қиындықтарынан қашу үшін тек бір ғана модельді пайдалануға шешім қабылдады. Яғни, олар бір модельдің бар болғаны \(P\) роутерін ғана сатып ала алады, және олардың барлығының радиусы бірдей болады.

Кейбір модельдердің радиусы тым кішкентай — олар барлық қажетті қатысушыларды қамти алмайды. Басқаларының радиусы тым үлкен, сондықтан қымбат әрі артық болады. Сондықтан біздің кейіпкерлер барлық \(M\) интернетсіз қалған қатысушыларды қамти алатын ең аз радиусты модельді таңдағысы келеді.

Барлық қатысушылар ұзын дәліз бойымен орналасқан, оның ұзындығы \(L\) — яғни координаталық осьтегі нүктелер \(1\)-ден \(L\)-ге дейінгі аралық. Қатысушылардың орындары бүтін сандармен берілген: әрқайсысы өз орнында, яғни координатасы \(x_i\). Біздің кейіпкерлер роутерлерді \(1\) мен \(L\) аралығындағы кез келген бүтін нүктелерге орната алады. Радиусы \(R\) болатын роутер өзінен \(R\) қашықтықтан аспайтын барлық қатысушыларды қамтиды. Басқаша айтқанда, қатысушы интернет алады, егер оның ең жақын роутерге дейінгі арақашықтығы \(R\)-дан аспаса.

Біздің кейіпкерлерге көмектесіңіз: минималды радиус \(R\)-ды табыңыз, сонда олар \(P\) роутер орнатып, бастапқыда интернетсіз қалған кем дегенде \(M\) қатысушыны қамти алады.

Ескерту: роутерге қол жеткізе алмай қалған қатысушыларға ұйымдастырушылар мобильді интернет береді.

Енгізу

Бірінші жолда төрт бүтін сан беріледі: \(N\), \(L\), \(M\), \(P\) — қатысушылар саны, дәліздің ұзындығы, интернеті жоқ қатысушылар саны және сатып алуға болатын роутерлер саны. \((1 \le M \le N \le 10^6, N \le L \le 10^{12}, 1 \le P \le 3)\)

Екінші жолда \(N\) әр түрлі бүтін сан \(x_1, x_2, \dots, x_N\) берілген — қатысушылардың координаттары. \((1 \le x_i \le L)\)

Шығару

Бір бүтін бейтарап санды шығарыңыз — ең кіші мүмкін радиус \(R\), онда \(P\) роутерді дәліз бойымен орналастырып, кем дегенде \(M\) қатысушыны интернетпен қамтамасыз етуге болады.

Бағалау жүйесі

Мысалдар

Енгізу 1

6 12 5 2
1 4 5 6 8 10

Жауап 1

1