Дом Адилбека расположен на улице, которая может быть представлена, как ось OX. На этой улице очень темно, поэтому Адилбек хочет установить фонари, чтобы осветить ее. На улице есть \(n\) позиции для установки фонарей, они соответствуют целым числам от \(0\) до \(n - 1\) на оси OX. Однако, некоторые позиции заблокированы, в них нельзя установить фонари.
Существуют фонари различных типов, они отличаются только своей мощностью. Когда фонарь мощности \(l\) устанавливают на позицию \(x\), сегмент улицы \([x; x + l]\) становится освещен. Мощность любого фонаря — это положительное целое число.
Магазин по продаже фонарей имеет ассортимент из бесконечного количество фонарей мощности от \(1\) до \(k\). Однако, каждый покупатель может купить фонари ровно одного типа. Каждый фонарь мощности \(l\) стоит \(a_l\).
Какую минимальную цену придется заплатить Адилбеку за покупку фонарей ровно одного типа таких, что они могут осветить весь отрезок улицы \([0; n]\)? Некоторые фонари могут освещать и другие отрезки улицы, эти отрезки Адилбеку не важны. Например, он может поставить фонарь мощности \(3\) в позицию \(n - 1\) (даже несмотря на то, что он освещает участок, который не полностью принадлежит \([0; n]\)).
Выходные данные
Выведите минимальную цену придется заплатить Адилбеку за покупку фонарей ровно одного типа таких, что они могут осветить весь отрезок улицы \([0; n]\).
Если невозможно осветить весь отрезок улицы \([0; n]\), то выведите -1.