import math
from typing import Tuple, List
 
TSection = Tuple[int, int]
 
def solve(tasks: List[int], days: int) -> Tuple[int, List[TSection]]:
    n = len(tasks)
    d = [[0 for i in range(n)] for j in range(n)]
    v = [[(0, []) for i in range(n)] for j in range(n)]
 
    def day_value(start: int, end: int) -> int:
        if end < start:
            return -math.inf
        if d[start][end] != 0:
            return d[start][end]
 
        res = max(tasks[end], day_value(start, end - 1))
        d[start][end] = res
        return res
 
    def best_variant(start: int, days: int) -> Tuple[int, List[TSection]]:
        if start >= len(tasks):
            return math.inf, []
        if v[start][days] != (0, []):
            return v[start][days]
 
        if days <= 1:
            end = len(tasks) - 1
            return day_value(start, end), [(start, end)]
 
        variants = []
        for end in range(start, len(tasks)):
            value, descriptions = best_variant(end + 1, days - 1)
            new_value = day_value(start, end) + value
            new_descriptions = [(start, end)] + descriptions
            new_variant = new_value, new_descriptions
            variants.append(new_variant)
 
        res2 = min(variants)
        v[start][days] = res2
        print(f'v[{start}, {days}] = {res2}')
        return res2
 
    res3 = best_variant(0, days)
    print(f'd:')
    for k in range(n):
    	print(f'{d[k]}')
    print(f'v:')
    for k in range(n):
    	s = list(map(lambda x: x[0], v[k]))
    	print(f'{s}')
    return res3
 
 
def print_solve(tasks: List[int], days: int) -> None:
    print(f'Tasks={tasks} Days={days}')
    print(f'Solve:')
    value, descriptions = solve(tasks, days)
    for start, end in descriptions:
        section = tasks[start: end + 1]
        print(f'Day {section} => max is {max(section)}')
    print(f'Total = {value}\n')
 
 
print_solve([2, 2, 2, 4, 1, 1, 1, 3], 5)

aW1wb3J0IG1hdGgKZnJvbSB0eXBpbmcgaW1wb3J0IFR1cGxlLCBMaXN0CiAKVFNlY3Rpb24gPSBUdXBsZVtpbnQsIGludF0KCmRlZiBzb2x2ZSh0YXNrczogTGlzdFtpbnRdLCBkYXlzOiBpbnQpIC0+IFR1cGxlW2ludCwgTGlzdFtUU2VjdGlvbl1dOgogICAgbiA9IGxlbih0YXNrcykKICAgIGQgPSBbWzAgZm9yIGkgaW4gcmFuZ2UobildIGZvciBqIGluIHJhbmdlKG4pXQogICAgdiA9IFtbKDAsIFtdKSBmb3IgaSBpbiByYW5nZShuKV0gZm9yIGogaW4gcmFuZ2UobildCgogICAgZGVmIGRheV92YWx1ZShzdGFydDogaW50LCBlbmQ6IGludCkgLT4gaW50OgogICAgICAgIGlmIGVuZCA8IHN0YXJ0OgogICAgICAgICAgICByZXR1cm4gLW1hdGguaW5mCiAgICAgICAgaWYgZFtzdGFydF1bZW5kXSAhPSAwOgogICAgICAgICAgICByZXR1cm4gZFtzdGFydF1bZW5kXQogICAgICAgIAogICAgICAgIHJlcyA9IG1heCh0YXNrc1tlbmRdLCBkYXlfdmFsdWUoc3RhcnQsIGVuZCAtIDEpKQogICAgICAgIGRbc3RhcnRdW2VuZF0gPSByZXMKICAgICAgICByZXR1cm4gcmVzCiAKICAgIGRlZiBiZXN0X3ZhcmlhbnQoc3RhcnQ6IGludCwgZGF5czogaW50KSAtPiBUdXBsZVtpbnQsIExpc3RbVFNlY3Rpb25dXToKICAgICAgICBpZiBzdGFydCA+PSBsZW4odGFza3MpOgogICAgICAgICAgICByZXR1cm4gbWF0aC5pbmYsIFtdCiAgICAgICAgaWYgdltzdGFydF1bZGF5c10gIT0gKDAsIFtdKToKICAgICAgICAgICAgcmV0dXJuIHZbc3RhcnRdW2RheXNdCiAKICAgICAgICBpZiBkYXlzIDw9IDE6CiAgICAgICAgICAgIGVuZCA9IGxlbih0YXNrcykgLSAxCiAgICAgICAgICAgIHJldHVybiBkYXlfdmFsdWUoc3RhcnQsIGVuZCksIFsoc3RhcnQsIGVuZCldCiAKICAgICAgICB2YXJpYW50cyA9IFtdCiAgICAgICAgZm9yIGVuZCBpbiByYW5nZShzdGFydCwgbGVuKHRhc2tzKSk6CiAgICAgICAgICAgIHZhbHVlLCBkZXNjcmlwdGlvbnMgPSBiZXN0X3ZhcmlhbnQoZW5kICsgMSwgZGF5cyAtIDEpCiAgICAgICAgICAgIG5ld192YWx1ZSA9IGRheV92YWx1ZShzdGFydCwgZW5kKSArIHZhbHVlCiAgICAgICAgICAgIG5ld19kZXNjcmlwdGlvbnMgPSBbKHN0YXJ0LCBlbmQpXSArIGRlc2NyaXB0aW9ucwogICAgICAgICAgICBuZXdfdmFyaWFudCA9IG5ld192YWx1ZSwgbmV3X2Rlc2NyaXB0aW9ucwogICAgICAgICAgICB2YXJpYW50cy5hcHBlbmQobmV3X3ZhcmlhbnQpCiAgICAgICAgCiAgICAgICAgcmVzMiA9IG1pbih2YXJpYW50cykKICAgICAgICB2W3N0YXJ0XVtkYXlzXSA9IHJlczIKICAgICAgICBwcmludChmJ3Zbe3N0YXJ0fSwge2RheXN9XSA9IHtyZXMyfScpCiAgICAgICAgcmV0dXJuIHJlczIKCiAgICByZXMzID0gYmVzdF92YXJpYW50KDAsIGRheXMpCiAgICBwcmludChmJ2Q6JykKICAgIGZvciBrIGluIHJhbmdlKG4pOgogICAgCXByaW50KGYne2Rba119JykKICAgIHByaW50KGYndjonKQogICAgZm9yIGsgaW4gcmFuZ2Uobik6CiAgICAJcyA9IGxpc3QobWFwKGxhbWJkYSB4OiB4WzBdLCB2W2tdKSkKICAgIAlwcmludChmJ3tzfScpCiAgICByZXR1cm4gcmVzMwogICAgCiAgICAKZGVmIHByaW50X3NvbHZlKHRhc2tzOiBMaXN0W2ludF0sIGRheXM6IGludCkgLT4gTm9uZToKICAgIHByaW50KGYnVGFza3M9e3Rhc2tzfSBEYXlzPXtkYXlzfScpCiAgICBwcmludChmJ1NvbHZlOicpCiAgICB2YWx1ZSwgZGVzY3JpcHRpb25zID0gc29sdmUodGFza3MsIGRheXMpCiAgICBmb3Igc3RhcnQsIGVuZCBpbiBkZXNjcmlwdGlvbnM6CiAgICAgICAgc2VjdGlvbiA9IHRhc2tzW3N0YXJ0OiBlbmQgKyAxXQogICAgICAgIHByaW50KGYnRGF5IHtzZWN0aW9ufSA9PiBtYXggaXMge21heChzZWN0aW9uKX0nKQogICAgcHJpbnQoZidUb3RhbCA9IHt2YWx1ZX1cbicpCiAgICAKICAgIApwcmludF9zb2x2ZShbMiwgMiwgMiwgNCwgMSwgMSwgMSwgM10sIDUp