Линдси Букингем сказала Стиви Никс «идти своим путем». Никс сейчас грустит и хочет уйти как можно быстрее, но она живет в двухмерном шестиугольном мире.
Рассмотрим шестиугольное покрытие плоскости, как на картинке ниже.
Ники хочет добраться от ячейки с координатами \((0, 0)\) к определенной ячейке, заданной координатами. Она может перейти от шестиугольника к любому из шести своих соседей, но у каждого из переходов есть своя стоимость. Стоимость зависит от направления, в котором вы путешествуете. Таким образом, переход от \((0, 0)\) до \((1, 1)\) будет стоить ровно столько же, как и переход от \((-2, -1)\) до \((-1, 0)\). Стоимости приведены во входных данных в порядке \(c_1\), \(c_2\), \(c_3\), \(c_4\), \(c_5\), \(c_6\), как на рисунке ниже.
Выведите наименьшую стоимость пути от начала координат, который имеет координаты \((0, 0)\), к данной ячейке.