Винни-Пух очень любит мёд! Именно поэтому он решил сходить в гости к своим друзьям. У Винни три лучших друга: Кролик, Сова и ослик Иа-Иа, каждый из которых живёт в своём домике.
Между каждой парой домиков есть извилистые тропинки. Длина тропинки между домами Кролика и Совы составляет a метров, между домами Кролика и ослика Иа-Иа b метров, между домами Совы и ослика Иа-Иа c метров.
Чтобы быть довольным жизнью и петь весёлые песенки, Винни-Пуху достаточно подкрепиться n раз в течение дня. Сейчас он находится в домике Кролика и подкрепляется первый раз. Каждый раз, когда в доме друга, у которого Винни находится в текущий момент, подходят к концу запасы мёда, а Винни ещё не поел нужное число раз, он выходит из дома и направляется к кому-то из других двух своих друзей. Для этого он выбирает одну из двух выходящих тропинок, проходит по ней до домика на другом конце и заходит в гости к живущему там другу. Можно считать, что пока Винни ест у одного из своих друзей, опустошённые запасы мёда других друзей восстанавливаются (скорее всего, они ходят в магазин).
Винни-Пух не любит физические нагрузки. Он хочет подкрепиться n раз, пройдя при этом минимальное суммарное расстояние. Помогите ему найти это расстояние.
Выходные данные
Выведите одно число — минимальное расстояние в метрах, которое Винни Пух должен пройти, чтобы покушать n раз.
Примечание
В первом тесте из условия оптимальный маршрут для Винни-Пуха — сначала подкрепиться в доме у Кролика, затем в доме у Совы, и наконец в доме у Иа-Иа. Таким образом он пройдёт расстояние 2 + 1 = 3.
Во втором тесте из условия Винни-Пух подкрепляется в доме у Кролика, и этого достаточно, чтобы наесться. Таким образом ему вообще не надо никуда перемещаться.