Свято наближається
Обмеження: 2 сек., 256 МіБ
«Свято наближається, свято наближається», — часто чуємо ми в різноманітних рекламних роликах, у телевізійних фільмах, просто на вулиці, у себе вдома, на роботі, в університеті і т. д. І чим ближче до Нового року, тим частіше і частіше лунають такі фрази. Весь український народ уже готується до низки свят, які будуть плавно переходити одне в одне. Що ж може бути краще для нас з вами, ніж глобальне свято, коли ніхто не думає про роботу, коли всі приймають гостей, коли мільярди вогників прикрашають всю нашу країну і, звичайно ж, коли Санта-Клаус роздає подарунки?
А чи задумувалися ви коли-небудь, як же ж насправді свято до нас наближається? Так от. Відповідь дуже проста. Наближається свято до нас, сидячи в санях, з мішком за спиною, який так і тріщить від подарунків. І уявіть собі, що їде свято найдовшою та найширшою вулицею Львова, мете сніг, світить місяць, а десь здалеку доносяться крики дітвори. Зупиняються сани біля кожного будинку. Санта-Клаус закидає на одне плече мішок з подарунками, на інше — ельфа-помічника та й заходить в будинок, щоб потішити його мешканців.
Іноді так буває, що їхати від одного будинку до наступного дуже довго, бо сани старі та й олені вже не ті. От у таких ситуаціях Санта-Клаусу та його оленям дуже нудно буває. Тож і гріються вони, як можуть. А від надмірного нагрівання дуже хочеться спати й виникає потенційна небезпека проспати наступний будинок. Тоді буде лихо — хтось залишиться без подарунків, а цього допускати не можна.
Тож адміністрація найширшої та найдовшої вулиці Львова вирішила, що окрім наявних nn будинків, варто побудувати ще додаткових mm так, щоб найдовша відстань між сусідніми будинками була якомога меншою.
Вхідні дані
Перший рядок містить два цілих числа nn, mm — кількість будинків на вулиці та кількість, яку ще треба побудувати.
Другий рядок містить n−1n−1 цілих чисел didi — відстані між будинком ii та будинком i+1i+1.
Вихідні дані
В одному рядку виведіть раціональне число у вигляді нескоротного дробу p/qp/q — мінімально можливу найдовшу відстань між сусідніми будинками після будівництва mm додаткових будинків.
Обмеження
2≤n≤1052≤n≤105,
1≤m≤1051≤m≤105,
1≤di≤1091≤di≤109.
Приклади
| Вхідні дані (stdin) | Вихідні дані (stdout) |
|---|---|
| 4 4 7 1 3 | 7/4 |