# Reduce the array

Medium

Execution time limit is 1 second

Runtime memory usage limit is 1,228 megabytes

Given an array consisting of $n$ integers and an integer $k$. Find the minimum cost to reduce the array to a single element. You can perform the following operation any number of times:

Choose any pair of consecutive array elements $a_{i}$ and $a_{j}$ and replace them with $(a_{i}+a_{i+1})$ at a cost of $k⋅(a_{i}+a_{i+1})$.

## Input

The first line contains two integer $n$ and $k(n,k≤100)$. The second line contains $n$ integers $a_{1},a_{2},…,a_{n}(0≤a_{i}≤100)$.

## Output

Print the minimum cost to reduce the array to a single element.

## Examples

Input #1

Answer #1

Input #2

Answer #2

Submissions 2

Acceptance rate 100%