Aşağı güc
Siz hesablama maşınları üçün inkişaf etmiş çiplər dizayn edirsiniz. Çiplərin istehsalı sadədir və artıq yoluna qoyulub, lakin mövcud batareyaların müxtəlif çıxış güclərinə malik olması enerji mənbələri ilə bağlı problemlər yaradır.
Təsəvvür edin ki, hər birində iki çip olan n maşın var və hər çip k batareya ilə qidalanır. Maraqlıdır ki, çiplərin nə qədər enerji istehlak etdiyi əhəmiyyət kəsb etmir, lakin çiplərin çıxış güclərinin bir-birindən mümkün qədər az fərqlənməsi vacibdir, çünki bu halda maşın ən yaxşı şəkildə işləyir. Çipin çıxış gücü çipdəki k batareyanın ən aşağı çıxış gücüdür.
Sizin 2nk batareyanız var və onları maşınların çiplərinə bölüşdürməlisiniz. Elə bir vəziyyət ola bilər ki, batareyaları elə bölüşdürmək mümkün deyil ki, bütün maşınlar üçün çiplərin çıxış gücləri bərabər olsun. Buna baxmayaraq, güc fərqini minimallaşdırmalısınız. Yəni, müştərilərinizə çiplərin çıxış gücləri arasındakı fərqin bütün maşınlarda d-dən çox olmadığını təmin etmək istəyirsiniz, eyni zamanda d-ni minimallaşdırmağa çalışırsınız. Bunun üçün batareyaların çiplərə optimal bölüşdürülməsini tapmalısınız.
1 nümunəsini nəzərdən keçirək. 2 maşın var, hər biri çip üçün 3 batareya tələb edir və batareyaların çıxış gücləri 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12-dir. Məsələn, 1, 3, 5 güclü batareyalarla birinci çipi, 2, 4, 12 güclü batareyalarla eyni maşının ikinci çipini, 6, 8, 9 güclü batareyalarla üçüncü çipi və 7, 10, 11 güclü batareyalarla dördüncü çipi qidalandırmaq olar. Çiplərin çıxış gücləri müvafiq olaraq 1, 2, 6 və 7-dir və hər iki maşında çıxış gücləri arasındakı fərq 1-dir. Qeyd edək ki, bu nəticəyə başqa yollarla da nail olmaq mümkündür.
Giriş verilənləri
Giriş məlumatları bir testdən ibarətdir və iki sətir ehtiva edir. Birinci sətirdə iki natural ədəd verilir: maşınların sayı n və çipdəki batareyaların sayı k (2nk ≤ 10^6). İkinci sətir 2nk ədəd p_i (1 ≤ p_i ≤ 10^9) ehtiva edir ki, bu da batareyaların çıxış güclərini təsvir edir.
Çıxış verilənləri
Elə minimal d çıxarın ki, batareyaların çiplərə elə bir bölüşdürülməsi mövcuddur ki, hər bir maşında çiplərin çıxış gücləri arasındakı fərq d-dən çox olmasın.