D-Ginger的大花环_牛客小白月赛63

时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

Ginger 有一个 $n$ 朵花的大花环，但是花环没有颜色，所有 Ginger 请来了他的好朋友 m_rd 来给染颜色，但 Ginger 只能提供 $k$ 种颜色，第 $i$ 种颜色有一个花费 $w_i$ ，他想让你用最小的花费来给大花环染色，但 Ginger 还有一个条件，环上的连续三朵花不能是同一种颜色。

注意花环是环状结构。

输入描述:

第一行给定两个正整数 $n, k$ $(3 \le n \le 10 ^ 5, 1 \le k \le 4)$ 表示花的个数和颜色个数。

第二行给定 $k$ 个正整数 $w_i$ $(1 \le w_i \le 10 ^ 9)$ 表示每个颜色的花费。

输出描述:

输出最小花费，如果不能染色输出 Ginger666

示例1

输入

复制

5 4
1 2 3 4

输出

复制

说明

样例  为 
由于是环形，所以不能是

示例2

输入

复制

3 1
1

输出

复制

Ginger666