Snuke lives in another world, where slimes are real creatures and kept by some people. Slimes come in N colors. Those colors are conveniently numbered 1 through N. Snuke currently has no slime. His objective is to have slimes of all the colors together.

Snuke can perform the following two actions:

* Select a color i (1≤i≤N), such that he does not currently have a slime in color i, and catch a slime in color i. This action takes him a_i seconds.

* Cast a spell, which changes the color of all the slimes that he currently has. The color of a slime in color i (1≤i≤N-1) will become color i+1, and the color of a slime in color N will become color 1. This action takes him x seconds.




Find the minimum time that Snuke needs to have slimes in all N colors.

Constraints

* 2≤N≤2,000
* a_i are integers.
* 1≤a_i≤10^9
* x is an integer.
* 1≤x≤10^9

Input

The input is given from Standard Input in the following format:


N x
a_1 a_2 ... a_N


Output

Find the minimum time that Snuke needs to have slimes in all N colors.

Examples

Input

2 10
1 100


Output

12


Input

3 10
100 1 100


Output

23


Input

4 10
1 2 3 4


Output

10
#include <bits/stdc++.h>
namespace tools {
template <typename T>
void read(std::vector<T>& vector,
          const typename std::vector<T>::size_type size) {
  vector.reserve(size);
  std::copy_n(std::istream_iterator<T>(std::cin), size,
              std::back_inserter(vector));
}
template <typename T, std::size_t N>
void read(std::array<T, N>& array) {
  std::copy_n(std::istream_iterator<T>(std::cin), N, array.begin());
}
}  // namespace tools
namespace tools {
template <typename T>
class dijkstra {
 private:
  class edge {
   public:
    std::size_t from;
    std::size_t to;
    T distance;
    edge(const std::size_t from, const std::size_t to, const T distance)
        : from(from), to(to), distance(distance) {}
  };
  class task {
   public:
    std::size_t vertex;
    T distance;
    task(const std::size_t vertex, const std::size_t distance)
        : vertex(vertex), distance(distance) {}
  };
  std::vector<std::vector<edge>> edges;

 public:
  static constexpr T INF = std::numeric_limits<T>::max();
  static constexpr std::size_t NONE = std::numeric_limits<std::size_t>::max();
  class result {
   public:
    std::vector<T> distances;
    std::vector<std::size_t> prev_nodes;
    result(const std::size_t node_count, const std::size_t start_node)
        : distances(node_count, INF), prev_nodes(node_count, NONE) {
      this->distances[start_node] = 0;
    }
  };
  dijkstra(const std::size_t node_count) : edges(node_count) {}
  std::size_t node_count() const { return this->edges.size(); }
  void add_edge(const std::size_t from, const std::size_t to,
                const T distance) {
    this->edges[from].emplace_back(from, to, distance);
  }
  result calc(const std::size_t start_node) const {
    assert(start_node < this->node_count());
    result result(this->node_count(), start_node);
    std::vector<bool> visited(this->node_count(), false);
    std::priority_queue<task, std::vector<task>,
                        std::function<bool(task, task)>>
        tasks([](const task& x, const task& y) {
          return x.distance > y.distance;
        });
    tasks.emplace(start_node, 0);
    while (!tasks.empty()) {
      const task task = tasks.top();
      tasks.pop();
      if (visited[task.vertex]) continue;
      visited[task.vertex] = true;
      for (const edge& edge : this->edges[task.vertex]) {
        const T new_distance = task.distance + edge.distance;
        if (new_distance < result.distances[edge.to]) {
          result.distances[edge.to] = new_distance;
          result.prev_nodes[edge.to] = edge.from;
          tasks.emplace(edge.to, new_distance);
        }
      }
    }
    return result;
  }
};
}  // namespace tools
int main() {
  std::int_fast64_t N, x;
  std::cin >> N >> x;
  std::vector<std::int_fast64_t> a;
  tools::read(a, N);
  tools::dijkstra<std::int_fast64_t> dijkstra(N + 1);
  for (std::int_fast64_t i = 0; i < N; ++i) {
    dijkstra.add_edge(N, i, a[i]);
    dijkstra.add_edge(i, (i + 1) % N, x);
  }
  const auto result = dijkstra.calc(N);
  std::vector<std::vector<std::int_fast64_t>> tree(N + 1);
  for (std::int_fast64_t i = 0; i < N; ++i) {
    tree[result.prev_nodes[i]].push_back(i);
  }
  std::vector<std::int_fast64_t> path_lengths(N + 1, 0);
  std::queue<std::int_fast64_t> queue;
  queue.push(N);
  while (!queue.empty()) {
    const std::int_fast64_t from = queue.front();
    queue.pop();
    for (const std::int_fast64_t& to : tree[from]) {
      path_lengths[to] = path_lengths[from] + 1;
      queue.push(to);
    }
  }
  std::int_fast64_t answer =
      (*std::max_element(path_lengths.begin(), path_lengths.end()) - 1) * x;
  for (std::int_fast64_t i = 0; i < N; ++i) {
    answer += a[(i - (path_lengths[i] - 1) + N) % N];
  }
  std::cout << answer << std::endl;
  return 0;
}
