В ряд стоят \(n\) воинов. Сила \(i\)-го воина равна \(a_i\). Все силы различны.
Вы можете использовать заклинания двух типов:
- Огненный Шар: вы тратите \(x\) маны и уничтожаете ровно \(k\) последовательных воинов;
- Берсерк: вы тратите \(y\) маны, выбираете двух соседних воинов, и воин с большей силой убивает воина с меньшей силой.
Например, пусть силы воинов равны \([2, 3, 7, 8, 11, 5, 4]\), и \(k = 3\). Если использовать Берсерк на воинах с силой \(8\) и \(11\), последовательность станет \([2, 3, 7, 11, 5, 4]\). Если после этого использовать Огненный Шар на воинах с силами \([7, 11, 5]\), последовательность станет \([2, 3, 4]\).
Вам необходимо превратить последовательность сил воинов \(a_1, a_2, \dots, a_n\) в \(b_1, b_2, \dots, b_m\). Посчитайте минимальное количество маны, которое вы должны затратить.
Выходные данные
Выведите минимальное количество маны для превращения последовательности \(a_1, a_2, \dots, a_n\) в \(b_1, b_2, \dots, b_m\) (или \(-1\), если это невозможно).