#include #define show(x) std::cerr << #x << " = " << x << std::endl using ll = long long; template constexpr T INF = std::numeric_limits::max() / 10; int main() { int N; ll V; std::cin >> N >> V; std::vector C(N); ll sum = 0; for (auto& e : C) { std::cin >> e, sum += e, V--; } if (V <= 0) { return std::cout << sum << std::endl, 0; } for (int i = 1; i < N; i++) { C[i] += C[i - 1]; } std::vector dp(N * N, INF); // 合計iリットル使う最安値 dp[0] = 0; std::vector tmp(N * N, INF); for (int i = 0; i < N; i++) { for (int j = 0; j < N * N; j++) { tmp[j] = (j <= i ? dp[j] : std::min(dp[j], tmp[j - i - 1] + C[i])); } std::swap(dp, tmp), std::fill(tmp.begin(), tmp.end(), INF); } ll min = INF; for (int i = 0; i < N * N; i++) { for (int j = 0; j < N; j++) { min = std::min(min, dp[i] + std::max(0LL, (V - i + j) / (j + 1) * C[j])); } } std::cout << min + sum << std::endl; return 0; }