1924: Колісниці Цезаря

Перегляд у форматі PDF
Надіслати розв'язок
Бали: 18,00 (partial)
Time limit: 1.0s
Memory limit: 256M
Input: stdin
Output: stdout
Author:
zvit
Problem type

У розпоряджені Цезаря є ~n~ колісниць. У кожну колісницю імператор хоче запрягти по дві групи коней, у кожній з яких буде по ~k~ гривастих. Цезар бажає, щоб різниця швидкостей між групами в кожній колісниці була як можна меншою. Швидкість групи визначається найнижчою швидкістю серед коней в цій групі.

Кінниця Цезаря складається із ~2nk~ коней. Перед походом, потрібно вирахувати, якою буде найбільша різниця між швидкостями для всіх колісниць, враховуючи, що це значення потрібно мінімізувати.

Input

В першому рядку знаходяться два числа ~n~ і ~k~ (~2nk \le 10^6~).

В другому рядку мітисться ~2nk~ цілих чисел - швидкостя коней (~1 \le S_i \le 10^9~).

Output

Виведіть одне ціле число - відповідь для Цезаря.

Sample Input 1

2 3
1 2 3 4 5 6 7 8 9 10 11 12

Sample Output 1

1

Sample Input 2

2 2
3 1 3 3 3 3 3 3

Sample Output 2

2

Notes

Пояснення до прикладу 1

Є 2 колісниці, а в кожну групу входить 3 коня. Можна розбити коней наступним чином.

У першу групу першої колісниці ввійдуть коні із швидкостями 1 11 12. (швидкість групи - 1)

У другу групу першої колісниці ввійдуть коні із швидкостями 2 10 9. (швидкість групи - 2) Різниця між групами - (2-1) = 1.

У першу групу другої колісниці ввійдуть коні із швидкостями 3 7 8. (швидкість групи - 3)

У другу групу другої колісниці ввійдуть коні із швидкостями 4 5 6. (швидкість групи - 4) Різниця між групами - (4-3) = 1.

Найбільша різниця серед усіх колісниць - max(1, 1) = 1.

Коментарі

Please read the guidelines before commenting.


  • 0
    Jodah  commented on Жов. 12, 2024, 10:15 до полудня

    чи завжди n і k більші від нуля?


    • 0
      zvit  commented on Жов. 12, 2024, 10:58 до полудня

      так


  • 0
    zoi274  commented on Жов. 11, 2024, 7:29 після полудня

    Добре 1. Щоб сформулювати групу потрібно взяти найменше число, найбільше і найбільше перед ним? 2. Щоб сформулювати групу потрбно взяти 1 число і 2 останніх?


    • 0
      zvit  commented on Жов. 12, 2024, 4:47 до полудня
      1. так (читаємо умову, та пояснення до прикладу)
      2. ні

  • 0
    zoi274  commented on Жов. 11, 2024, 5:20 після полудня

    Добрий вечір не зовсім зрозуміло яким чином вибирати швидкості типу в 1 прикладі взято (1, 11, 12) можна зробити 2 висновки. 1) Береться 1 число списка і 2 останніх і таким чином вийде 3 коня. 2) Взято найменше число, найбільше і найбільше перед найбільшим типу 1, 12 і найбільше крім 12 це 11 тому (1,12, 11) чи там якийсь інший метод вибірки? Не дуже зрозуміло як створюється сама група і яким чином вибираються числа.


    • 0
      zvit  commented on Жов. 11, 2024, 5:42 після полудня

      Запитання необхідно формулювати так, щоб на нього можна було би відповісти: так або ні.