Лёлик любит играть в лотерею, а также жульничать. И недавно он нашёл лазейку в системе принятия лотерейных билетов! Существует задержка между оглашением выигрышной комбинации номеров и завершением принятия билетов.

Правила лотереи, как всегда, просты. Участник покупает лотерейный билет, на котором написаны $$$n$$$ положительных целых чисел. Затем в определённый день оглашаются $$$n$$$ положительных целых чисел — выигрышные номера. Все участники их увидят как массив целых чисел $$$b$$$. Также заранее оглашаются призы: если $$$i$$$-й элемент билета участника совпадает с $$$i$$$-м элементом выигрышного билета, участник получает $$$c_i$$$ монет.

Лёлик решил использовать лазейку в системе для своего обогащения. У него есть официальный шаблон лотерейного билета, который представляет собой массив $$$a$$$ размера $$$n$$$, заполненный единицами. Также у Лёлика есть аппарат для изменения цифр на билете.

К сожалению, аппарат самодельный, и работает следующим образом. Лёлик может выбрать два целых числа $$$i$$$ ($$$1 \leq i \leq n$$$) и $$$z$$$ ($$$z \gt 0$$$) и увеличить $$$a_i$$$ на $$$\left\lfloor \frac{a_i}{z} \right\rfloor$$$ (частное от деления $$$a_i$$$ на $$$z$$$, округлённое вниз). Лёлик может выбирать одно и то же $$$i$$$ для операций сколько угодно раз.

Но этот процесс не быстрый, а время лазейки ограничено. Всего Лёлик сможет совершить не более $$$k$$$ операций. Поэтому он попросил вас максимизировать свой выигрыш.

Ваша задача — определить максимальное количество монет, которое может получить Лёлик за не более чем $$$k$$$ операций.