There are N piles of stones arranged in a row.  The i-th pile has stones[i] stones.
A move consists of merging exactly K consecutive piles into one pile, and the cost of this move is equal to the total number of stones in these K piles.
Find the minimum cost to merge all piles of stones into one pile.  If it is impossible, return -1.
 

Example 1:
Input: stones = [3,2,4,1], K = 2
Output: 20
Explanation: 
We start with [3, 2, 4, 1].
We merge [3, 2] for a cost of 5, and we are left with [5, 4, 1].
We merge [4, 1] for a cost of 5, and we are left with [5, 5].
We merge [5, 5] for a cost of 10, and we are left with [10].
The total cost was 20, and this is the minimum possible.


Example 2:
Input: stones = [3,2,4,1], K = 3
Output: -1
Explanation: After any merge operation, there are 2 piles left, and we can't merge anymore.  So the task is impossible.


Example 3:
Input: stones = [3,5,1,2,6], K = 3
Output: 25
Explanation: 
We start with [3, 5, 1, 2, 6].
We merge [5, 1, 2] for a cost of 8, and we are left with [3, 8, 6].
We merge [3, 8, 6] for a cost of 17, and we are left with [17].
The total cost was 25, and this is the minimum possible.

 
Note:

1 <= stones.length <= 30
2 <= K <= 30
1 <= stones[i] <= 100

```python

USER_FILENAME = "<user_code>"
import sys, json, builtins
import math, heapq, bisect, itertools, functools, collections, statistics, fractions, decimal, operator, array, random, re, string, os, pathlib
try:
    import resource as _res
except Exception:
    _res = None
from collections import Counter, defaultdict, deque, OrderedDict
from functools import lru_cache, reduce
from itertools import accumulate, permutations, combinations, product
from math import gcd, ceil, floor, sqrt
from decimal import Decimal
try:
    from typing import *
except Exception:
    pass
try:
    sys.setrecursionlimit(1_000_000)
except Exception:
    pass
try:
    import site as _site
    try:
        _sys_sites = _site.getsitepackages() if hasattr(_site, "getsitepackages") else []
        for _p in _sys_sites:
            if _p and _p not in sys.path:
                sys.path.append(_p)
    except Exception:
        pass
    try:
        _usp = _site.getusersitepackages()
        if isinstance(_usp, str):
            _usp = [_usp]
        for _p in _usp:
            if _p and _p not in sys.path:
                sys.path.append(_p)
    except Exception:
        pass
except Exception:
    pass

def _disabled_input(*args, **kwargs):
    raise RuntimeError("input() is disabled in callable mode")
builtins.input = _disabled_input

ns = {"__name__": "__judge__"}  # prevent if __name__ == "__main__" blocks
for _k, _v in list(globals().items()):
    if not _k.startswith("_"):
        ns[_k] = _v
_CODE = "class Solution:\n    def mergeStones(self, stones: List[int], K: int) -> int:\n        '''\n        dp[i][j][k]: the min cost to merge stone[i: j + 1] into k piles\n        the range for consecutive piles of stone[i:j + 1] to be k piles after merging can be divided into two parts (for stones[:n] be finally merged into 1 pile):\n            1. a sub-range from the start to the devide that is sured to be merged in to 1 pile: dp[i][divide][1]\n                divide goes from start by K - 1 step to make this happen: dp[i][divide][1] < math.inf\n            2. a sub-range from the divide + 1 to the end (not guaranteed to be realistic): dp[divide + 1][k - 1]\n        The longer ranges are always merged from the smaller ones, no matter how the smaller ones were merged from. That is why this is a DP problem.\n        '''\n        n = len(stones)\n        if K > 2 and n % (K - 1) != 1:\n            return -1\n        \n        dp = [[[math.inf] * (K + 1) for i in range(n)] for j in range(n)]\n        for i in range(n):\n            dp[i][i][1] = 0\n            \n        presum = [stones[0]]\n        for i in range(1, n):\n            presum.append(presum[i - 1] + stones[i])\n            \n        def stones_in_range(i, j):\n            return presum[j] - presum[i - 1] if i > 0 else presum[j]\n        \n        for rangelen in range(2, n + 1):\n            for start in range(n + 1 - rangelen):\n                end = start + rangelen - 1\n                for k in range(2, K + 1):\n                    for divide in range(start, end, K - 1):\n                        dp[start][end][k] = min(dp[start][end][k], dp[start][divide][1] + dp[divide + 1][end][k - 1])\n                if dp[start][end][K] < math.inf:\n                    dp[start][end][1] = dp[start][end][K] + stones_in_range(start, end)\n                    \n        return dp[0][n - 1][1]"
_co = compile(_CODE, USER_FILENAME, "exec")
exec(_co, ns, ns)

_target = None
_fn_name = 'mergeStones'
if _fn_name:
    if "Solution" in ns:
        try:
            _obj = ns["Solution"]()
            if hasattr(_obj, _fn_name):
                _target = getattr(_obj, _fn_name)
        except Exception:
            _target = None
    if _target is None and _fn_name in ns and callable(ns[_fn_name]):
        _target = ns[_fn_name]
# Fallback: if there's exactly one user-defined function, use it
if _target is None:
    _cands = [v for k, v in ns.items() if callable(v) and getattr(v, "__module__", "") in ("__judge__", "__main__")]
    _user_funcs = [c for c in _cands if getattr(c, "__name__", "").startswith("_") is False]
    if len(_user_funcs) == 1:
        _target = _user_funcs[0]
if _target is None:
    raise RuntimeError(f"Could not resolve callable '{_fn_name}'")

_raw = sys.stdin.read().strip()
if _raw:
    _parsed = json.loads(_raw)
    if isinstance(_parsed, dict):
        _kwargs = _parsed.get("kwargs", {})
        _args = _parsed.get("args", [])
    else:
        _args, _kwargs = _parsed, {}
else:
    _args, _kwargs = [], {}
if not isinstance(_args, (list, tuple)):
    _args = [_args]
_res = _target(*_args, **_kwargs)
try:
    sys.stdout.write(repr(_res) + "\n")
except Exception:
    pass

```

Measured memory_bytes: 8604