2 лютого 2020 року відбувся 2-й тур ІІІ обласного етапу Всеукраїнської учнівської олімпіади з інформатики 2019/2020 н.р.

Є два види оцiнювання:

«Потестове оцiнювання». Кожний тест оцiнюється незалежно вiд iнших. Проходження тесту приносить певну кiлькiсть балiв. Приклади оцiнюються в 0 балiв.

«Блочне оцiнювання». Усi тести подiленi на блоки, якi описанi в умовi задачi. Бали нараховуються лише при проходженнi всiх тестiв блоку. Якщо обмеження блока i не меншi за обмеження блока j, то для нарахування балiв за блок i, також потрiбно, щоб пройшли всi тести блока j. В умовi про це не буде сказано. Також є «нульовий блок», який складається з прикладiв, вiн оцiнюється в 0 балiв. В умовi про це згадувати не будуть.

У саду Потоколяндiї є газон шириною в 1 метр та довжиною в n метрiв.

Козак Вус хоче покосити цей газон за допомогою наступних дiй: вiн вибирає деякий пiдвiдрiзок цього газону довжиною k (частина газону шириною в 1 метр та довжиною в k метрiв) такий, що вiн повнiстю покритий травою та косить траву цiєї частини газону. На цю дiю йому необхiдно витратити одну годину.

Також вiдомо, що рiвно через годину з моменту, коли було завершено описану дiю, трава на цiй дiлянцi знову виросте. Це виростання вiдбувається миттєво в описаний момент часу.

Тодi Козак Вус зрозумiв, що його задовольнить навiть не повнiстю покошений газон - достатньо щоб будь-яка дiлянка газону була покошена хоча б один раз.

Допоможiть Козаку дiзнатись мiнiмальний час, який йому знадобиться, щоб будь-яка дiлянка газону була покошена хоча б один раз.

Початково на всьому газонi трава не є покошеною.

Перший рядок мiстить два цiлих числа n та k (1 ≤ k ≤ n ≤ 100) - довжина газону в метрах та довжина пiдвiдрiзку, який вибирається для того, щоб покосити газон, вiдповiдно.

Виведiть одне цiле число - вiдповiдь на задачу у годинах. Легко показати що вiдповiдь завжди є цiлим числом.

Пояснення до першого прикладу:

Кожний тест, крiм прикладiв, оцiнюється в 4 бали.

Нещодавно у Потоколяндiї розробили онлайн версiю гри «Мафiя».

Оскiльки Козак Вус - головний програмiст Потоколяндiї, то саме йому i довiрили протестувати цю гру.

Всiм вiдомо, що головне у грi «Мафiя» - чати повiдомлень. Козак Вус вважає гру протестованою, якщо у чатах сумарно буде написано хоча б n слiв.

Оскiльки програмiсти не тестують чати, Козаку доведеться найняти кiлька тестувальникiв на наступних умовах: кожен тестувальник напише привiтальне повiдомлення, що складатиметься з a слiв у загальний чат гри, а також напише кожному iншому тестувальнику привiтальне повiдомлення, що складатиметься з b слiв у особистий чат. Тестувальники не писатимуть iнших повiдомлень, крiм описаних вище.

Припустимо, що є 3 тестувальники, кожен з яких має написати «Усiм привiт!» (2 слова) у загальний чат, а також «Привiт!» (1 слово) кожному iншому тестувальнику в особистий чат. Тодi у загальному чатi буде написано 2 · 3 = 6 слiв (кожен тестувальник напише 2 слова), а в кожному особистому чатi буде написано по два слова (по одному слову вiд кожного тестувальника). Оскiльки всього 3 особистих чатiв (мiж першим та другим, мiж першим та третiм, мiж другим та третiм тестувальниками), то всього буде написано 3 · 2 = 6 слiв в особистих чатах. Отже, всього буде написано 6 + 6 = 12 слiв у всiх чатах.

Пiд час тестування лише тестувальники писатимуть повiдомлення у чати повiдомлень.

Через те, що Козак Вус не хоче витратити багато грошей на найм тестувальникiв, вiн вирiшив мiнiмiзувати їх кiлькiсть. Допоможiть йому дiзнатись мiнiмальну кiлькiсть тестувальникiв, яку доведеться найняти, щоб у чатах сумарно було написано хоча б n слiв.

Перший рядок мiстить три цiлих числа n, a та b (1 ≤ n ≤ 10¹², 0 ≤ a, b ≤ 10⁶, 0 < a + b) - мiнiмальна кiлькiсть слiв, яка має бути написана, кiлькiсть слiв, яку має написати кожний тестувальник у загальний чат, а також кiлькiсть слiв, яку має написати кожний тестувальник кожному iншому в особистий чат.

Виведiть одне цiле число - мiнiмальну кiлькiсть тестувальникiв, яку доведеться найняти, щоб у чатах сумарно було написано хоча б n слiв.

У першому прикладi, якщо буде найнято 3 тестувальника, то у загальний чат буде написано 3 слова, а в особистих чатах буде написано 18 слiв.

У другому прикладi, якщо буде найнято 2 тестувальника, то у загальний чат буде написано 16 слiв, а в особистих чатах буде написано 4 слова.

Кожний тест, крiм прикладiв, оцiнюється в 5 балiв.

Бути мiньйоном – це звiсно ж круто, але Козак Вус сильнiший за них...

У розпорядженнi у Козака Вуса є n мiньйонiв, пронумерованих цiлими числами вiд 1 до n.

Кожен мiньйон характеризується своїми силою та витривалiстю. У i-го мiньйона сила рiвна a_i, а витривалiсть рiвна b_i.

Козак Вух попросив Козака Вуса передати йому в розпорядження загiн мiньйонiв. Припустимо, що Козак Вух попросив передати k мiньйонiв. Тодi Козак Вус може передати будь-якi k мiньйонiв своєму другу. Цi мiньйони можуть мати будь-якi номери, не обов’язково послiдовнi. В кожному загонi має бути один лiдер, який вибирається Козаком Вусом.

Герої для кожного загону мiньйонiв визначили його цiну. Вони вважають, що цiна загону рiвна сумi сили лiдера та витривалостей всiх iнших мiньйонiв в загонi (якщо такi є). Розмiром загону називають кiлькiсть мiньйонiв у ньому.

Припустимо, що є чотири мiньйони, у яких:

1. сила 3, а витривалiсть 6,

2. сила 7, а витривалiсть 3,

3. сила 1, а витривалiсть 8,

4. сила 6, а витривалiсть 5.

Якщо Козак Вух просить передати йому загiн з 3 мiньйонiв, то Козак Вус може, наприклад, вибрати першого, другого та четвертого. Якщо вiн назначить другого лiдером, то цiна загону буде рiвна 7 (сила лiдера) + 6 (витривалiсть першого) + 5 (витривалiсть четвертого) = 18.