Дом Адилбека расположен на улице, которая может быть представлена, как ось OX. На этой улице очень темно, поэтому Адилбек хочет установить фонари, чтобы осветить ее. На улице есть $$$n$$$ позиции для установки фонарей, они соответствуют целым числам от $$$0$$$ до $$$n - 1$$$ на оси OX. Однако, некоторые позиции заблокированы, в них нельзя установить фонари.

Существуют фонари различных типов, они отличаются только своей мощностью. Когда фонарь мощности $$$l$$$ устанавливают на позицию $$$x$$$, сегмент улицы $$$[x; x + l]$$$ становится освещен. Мощность любого фонаря — это положительное целое число.

Магазин по продаже фонарей имеет ассортимент из бесконечного количество фонарей мощности от $$$1$$$ до $$$k$$$. Однако, каждый покупатель может купить фонари ровно одного типа. Каждый фонарь мощности $$$l$$$ стоит $$$a_l$$$.

Какую минимальную цену придется заплатить Адилбеку за покупку фонарей ровно одного типа таких, что они могут осветить весь отрезок улицы $$$[0; n]$$$? Некоторые фонари могут освещать и другие отрезки улицы, эти отрезки Адилбеку не важны. Например, он может поставить фонарь мощности $$$3$$$ в позицию $$$n - 1$$$ (даже несмотря на то, что он освещает участок, который не полностью принадлежит $$$[0; n]$$$).