Given a wooden stick of length n units. The stick is labelled from 0 to n. For example, a stick of length 6 is labelled as follows:

Given an integer array cuts where cuts[i] denotes a position you should perform a cut at.
You should perform the cuts in order, you can change the order of the cuts as you wish.
The cost of one cut is the length of the stick to be cut, the total cost is the sum of costs of all cuts. When you cut a stick, it will be split into two smaller sticks (i.e. the sum of their lengths is the length of the stick before the cut). Please refer to the first example for a better explanation.
Return the minimum total cost of the cuts.
 
Example 1:

Input: n = 7, cuts = [1,3,4,5]
Output: 16
Explanation: Using cuts order = [1, 3, 4, 5] as in the input leads to the following scenario:

The first cut is done to a rod of length 7 so the cost is 7. The second cut is done to a rod of length 6 (i.e. the second part of the first cut), the third is done to a rod of length 4 and the last cut is to a rod of length 3. The total cost is 7 + 6 + 4 + 3 = 20.
Rearranging the cuts to be [3, 5, 1, 4] for example will lead to a scenario with total cost = 16 (as shown in the example photo 7 + 4 + 3 + 2 = 16).
Example 2:
Input: n = 9, cuts = [5,6,1,4,2]
Output: 22
Explanation: If you try the given cuts ordering the cost will be 25.
There are much ordering with total cost <= 25, for example, the order [4, 6, 5, 2, 1] has total cost = 22 which is the minimum possible.

 
Constraints:

2 <= n <= 10^6
1 <= cuts.length <= min(n - 1, 100)
1 <= cuts[i] <= n - 1
All the integers in cuts array are distinct.

```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 = "import itertools\nimport sys\nfrom functools import lru_cache\nfrom math import comb\nfrom typing import List\n\n'''\n给你一个整数数组 cuts ，其中 cuts[i] 表示你需要将棍子切开的位置。定义切割成本是要切割的棍子长度，求最小的切割成本，即找到一个最小成本的切割顺序\n\n\nn = 7, cuts = [1,3,4,5]\n0 1| 2 3| 4| 5| 6 7\n\ndfs:\n        a\n      b c d\n      \ndp[start][end]= min(dp[start][cut] + dp[cut][end])\n斜向上扫描。\n\n\n'''\n\n\nclass Solution1:\n    def dfs(self, start, end, path, cuts):\n        if self.dp[start][end] != sys.maxsize:\n            return self.dp[start][end]\n        min_cut = sys.maxsize\n        flag = False\n        nums = cuts[self.cuts_map[start]:self.cuts_map[end]]\n        for cut in nums:\n            if cut not in path and start < cut and cut < end:\n                flag = True\n                path.add(cut)\n                min_cut = min(min_cut, end - start + self.dfs(start, cut, path, cuts) + self.dfs(cut, end, path, cuts))\n                path.remove(cut)\n        # 如果没切割点则返回0\n        if not flag:\n            min_cut = 0\n        self.dp[start][end] = min_cut\n        return min_cut\n\n    def minCost(self, n: int, cuts: List[int]) -> int:\n        self.dp = [[sys.maxsize for _ in range(n + 1)] for _ in range(n + 1)]\n        cuts = sorted(cuts)\n        self.cuts_map = {}\n        for i, cut in enumerate(cuts):\n            self.cuts_map[cut] = i\n        self.cuts_map[0] = 0\n        self.cuts_map[n] = n\n        return self.dfs(0, n, set(), cuts)\n\n    \nclass Solution:\n    def dfs(self, start, end, path, cuts):\n        if self.dp[self.cuts_map[start]][self.cuts_map[end]] != sys.maxsize:\n            return self.dp[self.cuts_map[start]][self.cuts_map[end]]\n        min_cut = sys.maxsize\n        flag = False\n        nums = cuts[self.cuts_map[start]:self.cuts_map[end]]\n        for cut in nums:\n            if cut not in path and start < cut and cut < end:\n                flag = True\n                path.add(cut)\n                min_cut = min(min_cut, end - start + self.dfs(start, cut, path, cuts) + self.dfs(cut, end, path, cuts))\n                path.remove(cut)\n        # 如果没切割点则返回0\n        if not flag:\n            min_cut = 0\n        self.dp[self.cuts_map[start]][self.cuts_map[end]] = min_cut\n        return min_cut\n\n    def minCost(self, n: int, cuts: List[int]) -> int:\n        self.dp = [[sys.maxsize for _ in range(len(cuts) + 2)] for _ in range(len(cuts) + 2)]  # 内存太大，需要优化\n        cuts.extend([0, n])\n        cuts = sorted(cuts)\n        self.cuts_map = {}\n        for i, cut in enumerate(cuts):\n            self.cuts_map[cut] = i\n        return self.dfs(0, n, set(), cuts)"
_co = compile(_CODE, USER_FILENAME, "exec")
exec(_co, ns, ns)

_target = None
_fn_name = 'minCost'
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: 9778