from functools import lru_cache

@lru_cache(maxsize=None)
def solve_dp(graph, lines_left, distance_since_last):
    """
    This function aims to minimize the sum of squared distances from points in a graph to selected lines, 
    subject to constraints.

    Args:
        graph (list of int): Represents the positions of points on a line.
        lines_left (int): The remaining number of lines allowed to be used.
        distance_since_last (int):  The distance from the last selected line to the current point.

    Returns:
        tuple: A tuple containing:
            - The minimum sum of squared distances achieved.
            - A list of indices indicating the selected line positions in the original graph.
    """

    if len(graph) < lines_left: return 1e9, []
    if lines_left == 0 and len(graph) == 0: return 0, []

    # option 1: don't take the line
    value = (1e9, [])
    if distance_since_last < 10:
        value = min(value, solve_dp(graph[1:], lines_left, distance_since_last+1))

    # option 2: take the line
    if lines_left > 0:
        sub, how = solve_dp(graph[1:], lines_left-1, 0)
        sub += graph[0] + (distance_since_last-8)**2
        value = min(value, (sub, how + [len(graph)]))

    return value


def solve_iterative(graph, lines_left, distance_since_last):
    """
    Iterative version of solve_dp.

    This function utilizes dynamic programming to solve the problem iteratively. 
    It creates a 3D table `dp` to store calculated results for subproblems. 
    Each cell in `dp` corresponds to a state defined by (graph index, lines left, distance since last line).
    """
    n = len(graph)
    dp = [[[None for _ in range(11)] for _ in range(lines_left + 1)] for _ in range(n + 1)]

    # Base cases
    for i in range(n + 1):
        for j in range(11):
            dp[i][0][j] = (0, []) if i == 0 else (1e9, [])

    # Fill the dp table iteratively
    for i in range(1, n + 1):
        for j in range(1, lines_left + 1):
            for k in range(11):
                dp[i][j][k] = dp[i - 1][j][k]  # Initialize with not taking the line
                if k > 0:
                    dp[i][j][k] = min(dp[i][j][k], dp[i - 1][j][k - 1])  # Consider not taking the line
                if j > 0:
                    sub, how = dp[i - 1][j - 1][0]
                    sub += graph[i - 1] + (k - 8) ** 2
                    dp[i][j][k] = min(dp[i][j][k], (sub, how + [i]))

    return dp[n][lines_left][distance_since_last]

from functools import lru_cache

@lru_cache(maxsize=None)
def solve_dp(graph, lines_left, distance_since_last):
    """
    This function aims to minimize the sum of squared distances from points in a graph to selected lines, 
    subject to constraints.

    Args:
        graph (list of int): Represents the positions of points on a line.
        lines_left (int): The remaining number of lines allowed to be used.
        distance_since_last (int):  The distance from the last selected line to the current point.

    Returns:
        tuple: A tuple containing:
            - The minimum sum of squared distances achieved.
            - A list of indices indicating the selected line positions in the original graph.
    """

    if len(graph) < lines_left: return 1e9, []
    if lines_left == 0 and len(graph) == 0: return 0, []

    # option 1: don't take the line
    value = (1e9, [])
    if distance_since_last < 10:
        value = min(value, solve_dp(graph[1:], lines_left, distance_since_last+1))

    # option 2: take the line
    if lines_left > 0:
        sub, how = solve_dp(graph[1:], lines_left-1, 0)
        sub += graph[0] + (distance_since_last-8)**2
        value = min(value, (sub, how + [len(graph)]))

    return value


def solve_iterative(graph, lines_left, distance_since_last):
    """
    Iterative version of solve_dp.

    This function utilizes dynamic programming to solve the problem iteratively. 
    It creates a 3D table `dp` to store calculated results for subproblems. 
    Each cell in `dp` corresponds to a state defined by (graph index, lines left, distance since last line).
    """
    n = len(graph)
    dp = [[[None for _ in range(11)] for _ in range(lines_left + 1)] for _ in range(n + 1)]

    # Base cases
    for i in range(n + 1):
        for j in range(11):
            dp[i][0][j] = (0, []) if i == 0 else (1e9, [])

    # Fill the dp table iteratively
    for i in range(1, n + 1):
        for j in range(1, lines_left + 1):
            for k in range(11):
                dp[i][j][k] = dp[i - 1][j][k]  # Initialize with not taking the line
                if k > 0:
                    dp[i][j][k] = min(dp[i][j][k], dp[i - 1][j][k - 1])  # Consider not taking the line
                if j > 0:
                    sub, how = dp[i - 1][j - 1][0]
                    sub += graph[i - 1] + (k - 8) ** 2
                    dp[i][j][k] = min(dp[i][j][k], (sub, how + [i]))

    return dp[n][lines_left][distance_since_last]

from functools import lru_cache

@lru_cache(maxsize=None)
def solve_dp(graph, lines_left, distance_since_last):
    """
    This function aims to minimize the sum of squared distances from points in a graph to selected lines, 
    subject to constraints.

    Args:
        graph (list of int): Represents the positions of points on a line.
        lines_left (int): The remaining number of lines allowed to be used.
        distance_since_last (int):  The distance from the last selected line to the current point.

    Returns:
        tuple: A tuple containing:
            - The minimum sum of squared distances achieved.
            - A list of indices indicating the selected line positions in the original graph.
    """

    if len(graph) < lines_left: return 1e9, []
    if lines_left == 0 and len(graph) == 0: return 0, []

    # option 1: don't take the line
    value = (1e9, [])
    if distance_since_last < 10:
        value = min(value, solve_dp(graph[1:], lines_left, distance_since_last+1))

    # option 2: take the line
    if lines_left > 0:
        sub, how = solve_dp(graph[1:], lines_left-1, 0)
        sub += graph[0] + (distance_since_last-8)**2
        value = min(value, (sub, how + [len(graph)]))

    return value


def solve_iterative(graph, lines_left, distance_since_last):
    """
    Iterative version of solve_dp.

    This function utilizes dynamic programming to solve the problem iteratively. 
    It creates a 3D table `dp` to store calculated results for subproblems. 
    Each cell in `dp` corresponds to a state defined by (graph index, lines left, distance since last line).
    """
    n = len(graph)
    dp = [[[None for _ in range(11)] for _ in range(lines_left + 1)] for _ in range(n + 1)]

    # Base cases
    for i in range(n + 1):
        for j in range(11):
            dp[i][0][j] = (0, []) if i == 0 else (1e9, [])

    # Fill the dp table iteratively
    for i in range(1, n + 1):
        for j in range(1, lines_left + 1):
            for k in range(11):
                dp[i][j][k] = dp[i - 1][j][k]  # Initialize with not taking the line
                if k > 0:
                    dp[i][j][k] = min(dp[i][j][k], dp[i - 1][j][k - 1])  # Consider not taking the line
                if j > 0:
                    sub, how = dp[i - 1][j - 1][0]
                    sub += graph[i - 1] + (k - 8) ** 2
                    dp[i][j][k] = min(dp[i][j][k], (sub, how + [i]))

    return dp[n][lines_left][distance_since_last]






answer = 0
import random
mylist = list(range(100))
random.shuffle(mylist)
from functools import lru_cache


@lru_cache(maxsize=None)
def my_solve_dp(graph, lines_left, distance_since_last):
    if len(graph) < lines_left: return 1e9, []
    if lines_left == 0 and len(graph) == 0: return 0, []

    # option 1: don't take the line
    value = (1e9, [])
    if distance_since_last < 10:
        value = min(value, my_solve_dp(graph[1:], lines_left, distance_since_last+1))

    # option 2: take the line
    if lines_left > 0:
        sub, how = my_solve_dp(graph[1:], lines_left-1, 0)
        sub += graph[0] + (distance_since_last-8)**2
        value = min(value, (sub, how + [len(graph)]))

    return value

answer = solve_iterative(tuple(mylist), len(mylist)//8, 4)
expected = my_solve_dp(tuple(mylist), len(mylist)//8, 4)
assert answer == expected, f'Wrong answer; got {answer} instead of {expected}'
print('All tests passed')

from functools import lru_cache

@lru_cache(maxsize=None)
def solve_dp(graph, lines_left, distance_since_last):
    """
    This function aims to minimize the sum of squared distances from each point in a graph to 
    a set of 'lines'. It uses dynamic programming to explore different combinations of lines.

    Args:
        graph (list of int): Represents the points on a line, with each element being the distance
                             from the origin.
        lines_left (int): The number of lines that can still be placed.
        distance_since_last (int): The distance from the last placed line to the current point 
                                    being considered.

    Returns:
        tuple: A tuple containing:
            - The minimum sum of squared distances achieved.
            - A list of indices in the graph where lines were placed to achieve the minimum.
    """
    if len(graph) < lines_left: return 1e9, []  # Not enough points for remaining lines
    if lines_left == 0 and len(graph) == 0: return 0, []  # Base case: no points, no lines left

    # Option 1: Don't place a line at the current point
    value = (1e9, [])  # Initialize with a large value
    if distance_since_last < 10:  # Check if placing a line is allowed based on distance
        value = min(value, solve_dp(graph[1:], lines_left, distance_since_last+1))

    # Option 2: Place a line at the current point
    if lines_left > 0:
        sub, how = solve_dp(graph[1:], lines_left-1, 0)  # Recursively explore placing a line
        sub += graph[0] + (distance_since_last-8)**2  # Calculate cost with the placed line
        value = min(value, (sub, how + [len(graph)]))  # Update if this placement is better

    return value


def solve_iterative(graph, lines_left, distance_since_last):
    """
    Iterative version of solve_dp, using a 3D array for memoization.

    Args:
        graph (list of int): Represents the points on a line.
        lines_left (int): The number of lines that can still be placed.
        distance_since_last (int): The distance from the last placed line.

    Returns:
        tuple: A tuple containing:
            - The minimum sum of squared distances achieved.
            - A list of indices in the graph where lines were placed.
    """
    n = len(graph)
    dp = [[[None for _ in range(distance_since_last + 1)] for _ in range(lines_left + 1)] for _ in range(n + 1)]

    # Initialize base cases
    for i in range(n + 1):
        for j in range(lines_left + 1):
            for k in range(distance_since_last + 1):
                if i < j:
                    dp[i][j][k] = (1e9, [])
                elif j == 0 and i == 0:
                    dp[i][j][k] = (0, [])

    # Fill the dp table iteratively
    for i in range(1, n + 1):
        for j in range(1, min(i + 1, lines_left + 1)):
            for k in range(distance_since_last + 1):
                # Option 1: Don't take the line
                value = (1e9, [])
                if k < 10:
                    value = dp[i - 1][j][k + 1]

                # Option 2: Take the line
                sub, how = dp[i - 1][j - 1][0]
                sub += graph[i - 1] + (k - 8) ** 2
                value = min(value, (sub, how + [i]))

                dp[i][j][k] = value

    return dp[n][lines_left][0]  # Return the result from the last cell

from functools import lru_cache

@lru_cache(maxsize=None)
def solve_dp(graph, lines_left, distance_since_last):
    """
    This function aims to minimize the sum of squared distances from each point in a graph to 
    a set of 'lines'. It uses dynamic programming to explore different combinations of lines.

    Args:
        graph (list of int): Represents the points on a line, with each element being the distance
                             from the origin.
        lines_left (int): The number of lines that can still be placed.
        distance_since_last (int): The distance from the last placed line to the current point 
                                    being considered.

    Returns:
        tuple: A tuple containing:
            - The minimum sum of squared distances achieved.
            - A list of indices in the graph where lines were placed to achieve the minimum.
    """
    if len(graph) < lines_left: return 1e9, []  # Not enough points for remaining lines
    if lines_left == 0 and len(graph) == 0: return 0, []  # Base case: no points, no lines left

    # Option 1: Don't place a line at the current point
    value = (1e9, [])  # Initialize with a large value
    if distance_since_last < 10:  # Check if placing a line is allowed based on distance
        value = min(value, solve_dp(graph[1:], lines_left, distance_since_last+1))

    # Option 2: Place a line at the current point
    if lines_left > 0:
        sub, how = solve_dp(graph[1:], lines_left-1, 0)  # Recursively explore placing a line
        sub += graph[0] + (distance_since_last-8)**2  # Calculate cost with the placed line
        value = min(value, (sub, how + [len(graph)]))  # Update if this placement is better

    return value


def solve_iterative(graph, lines_left, distance_since_last):
    """
    Iterative version of solve_dp, using a 3D array for memoization.

    Args:
        graph (list of int): Represents the points on a line.
        lines_left (int): The number of lines that can still be placed.
        distance_since_last (int): The distance from the last placed line.

    Returns:
        tuple: A tuple containing:
            - The minimum sum of squared distances achieved.
            - A list of indices in the graph where lines were placed.
    """
    n = len(graph)
    dp = [[[None for _ in range(distance_since_last + 1)] for _ in range(lines_left + 1)] for _ in range(n + 1)]

    # Initialize base cases
    for i in range(n + 1):
        for j in range(lines_left + 1):
            for k in range(distance_since_last + 1):
                if i < j:
                    dp[i][j][k] = (1e9, [])
                elif j == 0 and i == 0:
                    dp[i][j][k] = (0, [])

    # Fill the dp table iteratively
    for i in range(1, n + 1):
        for j in range(1, min(i + 1, lines_left + 1)):
            for k in range(distance_since_last + 1):
                # Option 1: Don't take the line
                value = (1e9, [])
                if k < 10:
                    value = dp[i - 1][j][k + 1]

                # Option 2: Take the line
                sub, how = dp[i - 1][j - 1][0]
                sub += graph[i - 1] + (k - 8) ** 2
                value = min(value, (sub, how + [i]))

                dp[i][j][k] = value

    return dp[n][lines_left][0]  # Return the result from the last cell

from functools import lru_cache

@lru_cache(maxsize=None)
def solve_dp(graph, lines_left, distance_since_last):
    """
    This function aims to minimize the sum of squared distances from each point in a graph to 
    a set of 'lines'. It uses dynamic programming to explore different combinations of lines.

    Args:
        graph (list of int): Represents the points on a line, with each element being the distance
                             from the origin.
        lines_left (int): The number of lines that can still be placed.
        distance_since_last (int): The distance from the last placed line to the current point 
                                    being considered.

    Returns:
        tuple: A tuple containing:
            - The minimum sum of squared distances achieved.
            - A list of indices in the graph where lines were placed to achieve the minimum.
    """
    if len(graph) < lines_left: return 1e9, []  # Not enough points for remaining lines
    if lines_left == 0 and len(graph) == 0: return 0, []  # Base case: no points, no lines left

    # Option 1: Don't place a line at the current point
    value = (1e9, [])  # Initialize with a large value
    if distance_since_last < 10:  # Check if placing a line is allowed based on distance
        value = min(value, solve_dp(graph[1:], lines_left, distance_since_last+1))

    # Option 2: Place a line at the current point
    if lines_left > 0:
        sub, how = solve_dp(graph[1:], lines_left-1, 0)  # Recursively explore placing a line
        sub += graph[0] + (distance_since_last-8)**2  # Calculate cost with the placed line
        value = min(value, (sub, how + [len(graph)]))  # Update if this placement is better

    return value


def solve_iterative(graph, lines_left, distance_since_last):
    """
    Iterative version of solve_dp, using a 3D array for memoization.

    Args:
        graph (list of int): Represents the points on a line.
        lines_left (int): The number of lines that can still be placed.
        distance_since_last (int): The distance from the last placed line.

    Returns:
        tuple: A tuple containing:
            - The minimum sum of squared distances achieved.
            - A list of indices in the graph where lines were placed.
    """
    n = len(graph)
    dp = [[[None for _ in range(distance_since_last + 1)] for _ in range(lines_left + 1)] for _ in range(n + 1)]

    # Initialize base cases
    for i in range(n + 1):
        for j in range(lines_left + 1):
            for k in range(distance_since_last + 1):
                if i < j:
                    dp[i][j][k] = (1e9, [])
                elif j == 0 and i == 0:
                    dp[i][j][k] = (0, [])

    # Fill the dp table iteratively
    for i in range(1, n + 1):
        for j in range(1, min(i + 1, lines_left + 1)):
            for k in range(distance_since_last + 1):
                # Option 1: Don't take the line
                value = (1e9, [])
                if k < 10:
                    value = dp[i - 1][j][k + 1]

                # Option 2: Take the line
                sub, how = dp[i - 1][j - 1][0]
                sub += graph[i - 1] + (k - 8) ** 2
                value = min(value, (sub, how + [i]))

                dp[i][j][k] = value

    return dp[n][lines_left][0]  # Return the result from the last cell







answer = 0
import random
mylist = list(range(100))
random.shuffle(mylist)
from functools import lru_cache


@lru_cache(maxsize=None)
def my_solve_dp(graph, lines_left, distance_since_last):
    if len(graph) < lines_left: return 1e9, []
    if lines_left == 0 and len(graph) == 0: return 0, []

    # option 1: don't take the line
    value = (1e9, [])
    if distance_since_last < 10:
        value = min(value, my_solve_dp(graph[1:], lines_left, distance_since_last+1))

    # option 2: take the line
    if lines_left > 0:
        sub, how = my_solve_dp(graph[1:], lines_left-1, 0)
        sub += graph[0] + (distance_since_last-8)**2
        value = min(value, (sub, how + [len(graph)]))

    return value

answer = solve_iterative(tuple(mylist), len(mylist)//8, 4)
expected = my_solve_dp(tuple(mylist), len(mylist)//8, 4)
assert answer == expected, f'Wrong answer; got {answer} instead of {expected}'
print('All tests passed')

from functools import lru_cache

@lru_cache(maxsize=None)
def solve_dp(graph, lines_left, distance_since_last):
    """
    This function aims to minimize the sum of squared distances from points in 
    the input 'graph' to selected lines, subject to constraints.

    Args:
        graph (list of int): Represents points on a line. Each element is the distance 
                              of a point from the origin.
        lines_left (int): The remaining number of lines allowed to be used.
        distance_since_last (int): The distance from the last selected line to the 
                                  current point being considered.

    Returns:
        tuple: A tuple containing:
            - The minimum sum of squared distances achieved.
            - A list of indices in 'graph' where lines were placed to achieve the minimum.
    """

    if len(graph) < lines_left: return 1e9, []  # Not enough points for remaining lines
    if lines_left == 0 and len(graph) == 0: return 0, []  # Base case: no points left

    # option 1: don't take the line
    value = (1e9, [])  # Initialize with a large value
    if distance_since_last < 10:  # Check if allowed to skip
        value = min(value, solve_dp(graph[1:], lines_left, distance_since_last+1))

    # option 2: take the line
    if lines_left > 0:
        sub, how = solve_dp(graph[1:], lines_left-1, 0)  # Recursively solve for rest
        sub += graph[0] + (distance_since_last-8)**2  # Add cost of current point
        value = min(value, (sub, how + [len(graph)]))  # Update if better

    return value

def solve_iterative(graph, lines_left, distance_since_last):
    """
    Iterative version of solve_dp.

    Args:
        graph (list of int): Represents points on a line.
        lines_left (int): The number of lines allowed.
        distance_since_last (int): Initial distance since the last line.

    Returns:
        tuple: A tuple containing:
            - The minimum sum of squared distances achieved.
            - A list of indices in 'graph' where lines were placed.
    """

    n = len(graph)
    dp = [[[ (1e9, []) for _ in range(distance_since_last + n + 1)] for _ in range(lines_left + 1)] for _ in range(n + 1)]

    # Initialize base cases
    for i in range(n + 1):
        for j in range(distance_since_last + n + 1):
            dp[i][0][j] = (0, []) if i == 0 else (1e9, [])

    # Iterate through the subproblems
    for i in range(1, n + 1):
        for j in range(1, lines_left + 1):
            for k in range(distance_since_last + n + 1):
                # Don't take the line
                dp[i][j][k] = dp[i - 1][j][k + 1] if k < distance_since_last + n else (1e9, [])

                # Take the line
                if j > 0:
                    sub_problem = dp[i - 1][j - 1][0]
                    cost = sub_problem[0] + graph[i - 1] + (k - 8) ** 2
                    if cost < dp[i][j][k][0]:
                        dp[i][j][k] = (cost, sub_problem[1] + [i])

    return dp[n][lines_left][distance_since_last]

from functools import lru_cache

@lru_cache(maxsize=None)
def solve_dp(graph, lines_left, distance_since_last):
    """
    This function aims to minimize the sum of squared distances from points in 
    the input 'graph' to selected lines, subject to constraints.

    Args:
        graph (list of int): Represents points on a line. Each element is the distance 
                              of a point from the origin.
        lines_left (int): The remaining number of lines allowed to be used.
        distance_since_last (int): The distance from the last selected line to the 
                                  current point being considered.

    Returns:
        tuple: A tuple containing:
            - The minimum sum of squared distances achieved.
            - A list of indices in 'graph' where lines were placed to achieve the minimum.
    """

    if len(graph) < lines_left: return 1e9, []  # Not enough points for remaining lines
    if lines_left == 0 and len(graph) == 0: return 0, []  # Base case: no points left

    # option 1: don't take the line
    value = (1e9, [])  # Initialize with a large value
    if distance_since_last < 10:  # Check if allowed to skip
        value = min(value, solve_dp(graph[1:], lines_left, distance_since_last+1))

    # option 2: take the line
    if lines_left > 0:
        sub, how = solve_dp(graph[1:], lines_left-1, 0)  # Recursively solve for rest
        sub += graph[0] + (distance_since_last-8)**2  # Add cost of current point
        value = min(value, (sub, how + [len(graph)]))  # Update if better

    return value

def solve_iterative(graph, lines_left, distance_since_last):
    """
    Iterative version of solve_dp.

    Args:
        graph (list of int): Represents points on a line.
        lines_left (int): The number of lines allowed.
        distance_since_last (int): Initial distance since the last line.

    Returns:
        tuple: A tuple containing:
            - The minimum sum of squared distances achieved.
            - A list of indices in 'graph' where lines were placed.
    """

    n = len(graph)
    dp = [[[ (1e9, []) for _ in range(distance_since_last + n + 1)] for _ in range(lines_left + 1)] for _ in range(n + 1)]

    # Initialize base cases
    for i in range(n + 1):
        for j in range(distance_since_last + n + 1):
            dp[i][0][j] = (0, []) if i == 0 else (1e9, [])

    # Iterate through the subproblems
    for i in range(1, n + 1):
        for j in range(1, lines_left + 1):
            for k in range(distance_since_last + n + 1):
                # Don't take the line
                dp[i][j][k] = dp[i - 1][j][k + 1] if k < distance_since_last + n else (1e9, [])

                # Take the line
                if j > 0:
                    sub_problem = dp[i - 1][j - 1][0]
                    cost = sub_problem[0] + graph[i - 1] + (k - 8) ** 2
                    if cost < dp[i][j][k][0]:
                        dp[i][j][k] = (cost, sub_problem[1] + [i])

    return dp[n][lines_left][distance_since_last]

from functools import lru_cache

@lru_cache(maxsize=None)
def solve_dp(graph, lines_left, distance_since_last):
    """
    This function aims to minimize the sum of squared distances from points in 
    the input 'graph' to selected lines, subject to constraints.

    Args:
        graph (list of int): Represents points on a line. Each element is the distance 
                              of a point from the origin.
        lines_left (int): The remaining number of lines allowed to be used.
        distance_since_last (int): The distance from the last selected line to the 
                                  current point being considered.

    Returns:
        tuple: A tuple containing:
            - The minimum sum of squared distances achieved.
            - A list of indices in 'graph' where lines were placed to achieve the minimum.
    """

    if len(graph) < lines_left: return 1e9, []  # Not enough points for remaining lines
    if lines_left == 0 and len(graph) == 0: return 0, []  # Base case: no points left

    # option 1: don't take the line
    value = (1e9, [])  # Initialize with a large value
    if distance_since_last < 10:  # Check if allowed to skip
        value = min(value, solve_dp(graph[1:], lines_left, distance_since_last+1))

    # option 2: take the line
    if lines_left > 0:
        sub, how = solve_dp(graph[1:], lines_left-1, 0)  # Recursively solve for rest
        sub += graph[0] + (distance_since_last-8)**2  # Add cost of current point
        value = min(value, (sub, how + [len(graph)]))  # Update if better

    return value

def solve_iterative(graph, lines_left, distance_since_last):
    """
    Iterative version of solve_dp.

    Args:
        graph (list of int): Represents points on a line.
        lines_left (int): The number of lines allowed.
        distance_since_last (int): Initial distance since the last line.

    Returns:
        tuple: A tuple containing:
            - The minimum sum of squared distances achieved.
            - A list of indices in 'graph' where lines were placed.
    """

    n = len(graph)
    dp = [[[ (1e9, []) for _ in range(distance_since_last + n + 1)] for _ in range(lines_left + 1)] for _ in range(n + 1)]

    # Initialize base cases
    for i in range(n + 1):
        for j in range(distance_since_last + n + 1):
            dp[i][0][j] = (0, []) if i == 0 else (1e9, [])

    # Iterate through the subproblems
    for i in range(1, n + 1):
        for j in range(1, lines_left + 1):
            for k in range(distance_since_last + n + 1):
                # Don't take the line
                dp[i][j][k] = dp[i - 1][j][k + 1] if k < distance_since_last + n else (1e9, [])

                # Take the line
                if j > 0:
                    sub_problem = dp[i - 1][j - 1][0]
                    cost = sub_problem[0] + graph[i - 1] + (k - 8) ** 2
                    if cost < dp[i][j][k][0]:
                        dp[i][j][k] = (cost, sub_problem[1] + [i])

    return dp[n][lines_left][distance_since_last]






answer = 0
import random
mylist = list(range(100))
random.shuffle(mylist)
from functools import lru_cache


@lru_cache(maxsize=None)
def my_solve_dp(graph, lines_left, distance_since_last):
    if len(graph) < lines_left: return 1e9, []
    if lines_left == 0 and len(graph) == 0: return 0, []

    # option 1: don't take the line
    value = (1e9, [])
    if distance_since_last < 10:
        value = min(value, my_solve_dp(graph[1:], lines_left, distance_since_last+1))

    # option 2: take the line
    if lines_left > 0:
        sub, how = my_solve_dp(graph[1:], lines_left-1, 0)
        sub += graph[0] + (distance_since_last-8)**2
        value = min(value, (sub, how + [len(graph)]))

    return value

answer = solve_iterative(tuple(mylist), len(mylist)//8, 4)
expected = my_solve_dp(tuple(mylist), len(mylist)//8, 4)
assert answer == expected, f'Wrong answer; got {answer} instead of {expected}'
print('All tests passed')

from functools import lru_cache

@lru_cache(maxsize=None)
def solve_dp(graph, lines_left, distance_since_last):
    """
    This function solves a dynamic programming problem where the goal is to minimize the cost of 
    selecting a subset of elements from a 'graph' while adhering to certain constraints.

    Args:
        graph (list): A list of integers representing the elements to choose from.
        lines_left (int): The remaining number of elements allowed to be selected.
        distance_since_last (int): The distance (in index positions) from the last selected element.

    Returns:
        tuple: A tuple containing the minimum cost and the indices of the selected elements.
    """
    if len(graph) < lines_left: return 1e9, []  # Base case: Not enough elements left to satisfy 'lines_left'
    if lines_left == 0 and len(graph) == 0: return 0, []  # Base case: All elements processed, and constraints met

    # Option 1: Don't take the current element
    value = (1e9, [])  # Initialize with a very high cost
    if distance_since_last < 10:  # Check if allowed to skip based on distance constraint
        value = min(value, solve_dp(graph[1:], lines_left, distance_since_last+1))  

    # Option 2: Take the current element (if allowed)
    if lines_left > 0:
        sub, how = solve_dp(graph[1:], lines_left-1, 0)  # Recursively explore taking the element
        sub += graph[0] + (distance_since_last-8)**2  # Calculate cost with the current element
        value = min(value, (sub, how + [len(graph)]))  # Update 'value' if the new cost is lower

    return value  # Return the minimum cost and corresponding element selections

def solve_iterative(graph, lines_left, distance_since_last):
    """
    Iterative version of the `solve_dp` function using dynamic programming.

    Args:
        graph (list): A list of integers representing the elements to choose from.
        lines_left (int): The remaining number of elements allowed to be selected.
        distance_since_last (int): The distance (in index positions) from the last selected element.

    Returns:
        tuple: A tuple containing the minimum cost and the indices of the selected elements.
    """
    n = len(graph)
    dp = [[[ (1e9, []) for _ in range(11)] for _ in range(lines_left + 1)] for _ in range(n+1)]

    # Initialize base cases
    for i in range(n+1):
        for d in range(11):
            dp[i][0][d] = (0, [])

    # Fill the DP table iteratively
    for i in range(1, n+1):
        for j in range(1, min(i+1, lines_left+1)):
            for d in range(1, 11):
                # Option 1: Don't take the line
                dp[i][j][d] = dp[i-1][j][d-1] 

                # Option 2: Take the line
                if j > 0:
                    sub, how = dp[i-1][j-1][0] 
                    sub += graph[i-1] + (d-9)**2
                    dp[i][j][0] = min(dp[i][j][0], (sub, how + [i]))

    return dp[n][lines_left][distance_since_last]

from functools import lru_cache

@lru_cache(maxsize=None)
def solve_dp(graph, lines_left, distance_since_last):
    """
    This function solves a dynamic programming problem where the goal is to minimize the cost of 
    selecting a subset of elements from a 'graph' while adhering to certain constraints.

    Args:
        graph (list): A list of integers representing the elements to choose from.
        lines_left (int): The remaining number of elements allowed to be selected.
        distance_since_last (int): The distance (in index positions) from the last selected element.

    Returns:
        tuple: A tuple containing the minimum cost and the indices of the selected elements.
    """
    if len(graph) < lines_left: return 1e9, []  # Base case: Not enough elements left to satisfy 'lines_left'
    if lines_left == 0 and len(graph) == 0: return 0, []  # Base case: All elements processed, and constraints met

    # Option 1: Don't take the current element
    value = (1e9, [])  # Initialize with a very high cost
    if distance_since_last < 10:  # Check if allowed to skip based on distance constraint
        value = min(value, solve_dp(graph[1:], lines_left, distance_since_last+1))  

    # Option 2: Take the current element (if allowed)
    if lines_left > 0:
        sub, how = solve_dp(graph[1:], lines_left-1, 0)  # Recursively explore taking the element
        sub += graph[0] + (distance_since_last-8)**2  # Calculate cost with the current element
        value = min(value, (sub, how + [len(graph)]))  # Update 'value' if the new cost is lower

    return value  # Return the minimum cost and corresponding element selections

def solve_iterative(graph, lines_left, distance_since_last):
    """
    Iterative version of the `solve_dp` function using dynamic programming.

    Args:
        graph (list): A list of integers representing the elements to choose from.
        lines_left (int): The remaining number of elements allowed to be selected.
        distance_since_last (int): The distance (in index positions) from the last selected element.

    Returns:
        tuple: A tuple containing the minimum cost and the indices of the selected elements.
    """
    n = len(graph)
    dp = [[[ (1e9, []) for _ in range(11)] for _ in range(lines_left + 1)] for _ in range(n+1)]

    # Initialize base cases
    for i in range(n+1):
        for d in range(11):
            dp[i][0][d] = (0, [])

    # Fill the DP table iteratively
    for i in range(1, n+1):
        for j in range(1, min(i+1, lines_left+1)):
            for d in range(1, 11):
                # Option 1: Don't take the line
                dp[i][j][d] = dp[i-1][j][d-1] 

                # Option 2: Take the line
                if j > 0:
                    sub, how = dp[i-1][j-1][0] 
                    sub += graph[i-1] + (d-9)**2
                    dp[i][j][0] = min(dp[i][j][0], (sub, how + [i]))

    return dp[n][lines_left][distance_since_last]

from functools import lru_cache

@lru_cache(maxsize=None)
def solve_dp(graph, lines_left, distance_since_last):
    """
    This function solves a dynamic programming problem where the goal is to minimize the cost of 
    selecting a subset of elements from a 'graph' while adhering to certain constraints.

    Args:
        graph (list): A list of integers representing the elements to choose from.
        lines_left (int): The remaining number of elements allowed to be selected.
        distance_since_last (int): The distance (in index positions) from the last selected element.

    Returns:
        tuple: A tuple containing the minimum cost and the indices of the selected elements.
    """
    if len(graph) < lines_left: return 1e9, []  # Base case: Not enough elements left to satisfy 'lines_left'
    if lines_left == 0 and len(graph) == 0: return 0, []  # Base case: All elements processed, and constraints met

    # Option 1: Don't take the current element
    value = (1e9, [])  # Initialize with a very high cost
    if distance_since_last < 10:  # Check if allowed to skip based on distance constraint
        value = min(value, solve_dp(graph[1:], lines_left, distance_since_last+1))  

    # Option 2: Take the current element (if allowed)
    if lines_left > 0:
        sub, how = solve_dp(graph[1:], lines_left-1, 0)  # Recursively explore taking the element
        sub += graph[0] + (distance_since_last-8)**2  # Calculate cost with the current element
        value = min(value, (sub, how + [len(graph)]))  # Update 'value' if the new cost is lower

    return value  # Return the minimum cost and corresponding element selections

def solve_iterative(graph, lines_left, distance_since_last):
    """
    Iterative version of the `solve_dp` function using dynamic programming.

    Args:
        graph (list): A list of integers representing the elements to choose from.
        lines_left (int): The remaining number of elements allowed to be selected.
        distance_since_last (int): The distance (in index positions) from the last selected element.

    Returns:
        tuple: A tuple containing the minimum cost and the indices of the selected elements.
    """
    n = len(graph)
    dp = [[[ (1e9, []) for _ in range(11)] for _ in range(lines_left + 1)] for _ in range(n+1)]

    # Initialize base cases
    for i in range(n+1):
        for d in range(11):
            dp[i][0][d] = (0, [])

    # Fill the DP table iteratively
    for i in range(1, n+1):
        for j in range(1, min(i+1, lines_left+1)):
            for d in range(1, 11):
                # Option 1: Don't take the line
                dp[i][j][d] = dp[i-1][j][d-1] 

                # Option 2: Take the line
                if j > 0:
                    sub, how = dp[i-1][j-1][0] 
                    sub += graph[i-1] + (d-9)**2
                    dp[i][j][0] = min(dp[i][j][0], (sub, how + [i]))

    return dp[n][lines_left][distance_since_last]






answer = 0
import random
mylist = list(range(100))
random.shuffle(mylist)
from functools import lru_cache


@lru_cache(maxsize=None)
def my_solve_dp(graph, lines_left, distance_since_last):
    if len(graph) < lines_left: return 1e9, []
    if lines_left == 0 and len(graph) == 0: return 0, []

    # option 1: don't take the line
    value = (1e9, [])
    if distance_since_last < 10:
        value = min(value, my_solve_dp(graph[1:], lines_left, distance_since_last+1))

    # option 2: take the line
    if lines_left > 0:
        sub, how = my_solve_dp(graph[1:], lines_left-1, 0)
        sub += graph[0] + (distance_since_last-8)**2
        value = min(value, (sub, how + [len(graph)]))

    return value

answer = solve_iterative(tuple(mylist), len(mylist)//8, 4)
expected = my_solve_dp(tuple(mylist), len(mylist)//8, 4)
assert answer == expected, f'Wrong answer; got {answer} instead of {expected}'
print('All tests passed')

from functools import lru_cache

@lru_cache(maxsize=None)
def solve_dp(graph, lines_left, distance_since_last):
    """
    This function aims to minimize the sum of squared distances from points in a graph 
    to selected "lines". It uses dynamic programming to explore different combinations 
    of lines and their placements.

    Args:
      graph: A list of integers representing points on a line.
      lines_left: The number of lines allowed to be placed.
      distance_since_last: The distance from the previous line placement.

    Returns:
      A tuple containing:
        - The minimum sum of squared distances achieved.
        - A list of indices in the graph where lines were placed to achieve that minimum.
    """
    if len(graph) < lines_left: return 1e9, []  # Not enough points for remaining lines
    if lines_left == 0 and len(graph) == 0: return 0, []  # Base case: no lines, no points

    # Option 1: Don't place a line at the current position
    value = (1e9, [])  # Initialize with a very large value
    if distance_since_last < 10:  # Only consider if distance constraint is met
        value = min(value, solve_dp(graph[1:], lines_left, distance_since_last+1))

    # Option 2: Place a line at the current position
    if lines_left > 0:
        sub, how = solve_dp(graph[1:], lines_left-1, 0)  # Recursively solve for rest of the graph
        sub += graph[0] + (distance_since_last-8)**2  # Add cost of placing line here
        value = min(value, (sub, how + [len(graph)]))  # Update if this placement is better

    return value


def solve_iterative(graph, lines_left, distance_since_last):
    """
    Iterative version of solve_dp using bottom-up dynamic programming.

    Args:
      graph: A list of integers representing points on a line.
      lines_left: The number of lines allowed to be placed.
      distance_since_last: The distance from the previous line placement.

    Returns:
      A tuple containing:
        - The minimum sum of squared distances achieved.
        - A list of indices in the graph where lines were placed to achieve that minimum.
    """
    n = len(graph)
    dp = [[[ (1e9, []) for _ in range(11)] for _ in range(lines_left + 1)] for _ in range(n + 1)]

    # Initialize base cases
    for i in range(n + 1):
        for d in range(11):
            dp[i][0][d] = (0, [])

    # Fill the dp table iteratively
    for i in range(1, n + 1):
        for j in range(1, min(i + 1, lines_left + 1)):
            for d in range(11):
                # Option 1: Don't take the line
                dp[i][j][d] = dp[i - 1][j][min(d + 1, 10)]

                # Option 2: Take the line
                if d == 0:
                    sub, how = dp[i - 1][j - 1][0]
                    sub += graph[i - 1] + (10 - 8)**2  # Assuming distance_since_last is initially 10
                    dp[i][j][d] = min(dp[i][j][d], (sub, how + [i]))

    return dp[n][lines_left][0]

from functools import lru_cache

@lru_cache(maxsize=None)
def solve_dp(graph, lines_left, distance_since_last):
    """
    This function aims to minimize the sum of squared distances from points in a graph 
    to selected "lines". It uses dynamic programming to explore different combinations 
    of lines and their placements.

    Args:
      graph: A list of integers representing points on a line.
      lines_left: The number of lines allowed to be placed.
      distance_since_last: The distance from the previous line placement.

    Returns:
      A tuple containing:
        - The minimum sum of squared distances achieved.
        - A list of indices in the graph where lines were placed to achieve that minimum.
    """
    if len(graph) < lines_left: return 1e9, []  # Not enough points for remaining lines
    if lines_left == 0 and len(graph) == 0: return 0, []  # Base case: no lines, no points

    # Option 1: Don't place a line at the current position
    value = (1e9, [])  # Initialize with a very large value
    if distance_since_last < 10:  # Only consider if distance constraint is met
        value = min(value, solve_dp(graph[1:], lines_left, distance_since_last+1))

    # Option 2: Place a line at the current position
    if lines_left > 0:
        sub, how = solve_dp(graph[1:], lines_left-1, 0)  # Recursively solve for rest of the graph
        sub += graph[0] + (distance_since_last-8)**2  # Add cost of placing line here
        value = min(value, (sub, how + [len(graph)]))  # Update if this placement is better

    return value


def solve_iterative(graph, lines_left, distance_since_last):
    """
    Iterative version of solve_dp using bottom-up dynamic programming.

    Args:
      graph: A list of integers representing points on a line.
      lines_left: The number of lines allowed to be placed.
      distance_since_last: The distance from the previous line placement.

    Returns:
      A tuple containing:
        - The minimum sum of squared distances achieved.
        - A list of indices in the graph where lines were placed to achieve that minimum.
    """
    n = len(graph)
    dp = [[[ (1e9, []) for _ in range(11)] for _ in range(lines_left + 1)] for _ in range(n + 1)]

    # Initialize base cases
    for i in range(n + 1):
        for d in range(11):
            dp[i][0][d] = (0, [])

    # Fill the dp table iteratively
    for i in range(1, n + 1):
        for j in range(1, min(i + 1, lines_left + 1)):
            for d in range(11):
                # Option 1: Don't take the line
                dp[i][j][d] = dp[i - 1][j][min(d + 1, 10)]

                # Option 2: Take the line
                if d == 0:
                    sub, how = dp[i - 1][j - 1][0]
                    sub += graph[i - 1] + (10 - 8)**2  # Assuming distance_since_last is initially 10
                    dp[i][j][d] = min(dp[i][j][d], (sub, how + [i]))

    return dp[n][lines_left][0]

from functools import lru_cache

@lru_cache(maxsize=None)
def solve_dp(graph, lines_left, distance_since_last):
    """
    This function aims to minimize the sum of squared distances from points in a graph 
    to selected "lines". It uses dynamic programming to explore different combinations 
    of lines and their placements.

    Args:
      graph: A list of integers representing points on a line.
      lines_left: The number of lines allowed to be placed.
      distance_since_last: The distance from the previous line placement.

    Returns:
      A tuple containing:
        - The minimum sum of squared distances achieved.
        - A list of indices in the graph where lines were placed to achieve that minimum.
    """
    if len(graph) < lines_left: return 1e9, []  # Not enough points for remaining lines
    if lines_left == 0 and len(graph) == 0: return 0, []  # Base case: no lines, no points

    # Option 1: Don't place a line at the current position
    value = (1e9, [])  # Initialize with a very large value
    if distance_since_last < 10:  # Only consider if distance constraint is met
        value = min(value, solve_dp(graph[1:], lines_left, distance_since_last+1))

    # Option 2: Place a line at the current position
    if lines_left > 0:
        sub, how = solve_dp(graph[1:], lines_left-1, 0)  # Recursively solve for rest of the graph
        sub += graph[0] + (distance_since_last-8)**2  # Add cost of placing line here
        value = min(value, (sub, how + [len(graph)]))  # Update if this placement is better

    return value


def solve_iterative(graph, lines_left, distance_since_last):
    """
    Iterative version of solve_dp using bottom-up dynamic programming.

    Args:
      graph: A list of integers representing points on a line.
      lines_left: The number of lines allowed to be placed.
      distance_since_last: The distance from the previous line placement.

    Returns:
      A tuple containing:
        - The minimum sum of squared distances achieved.
        - A list of indices in the graph where lines were placed to achieve that minimum.
    """
    n = len(graph)
    dp = [[[ (1e9, []) for _ in range(11)] for _ in range(lines_left + 1)] for _ in range(n + 1)]

    # Initialize base cases
    for i in range(n + 1):
        for d in range(11):
            dp[i][0][d] = (0, [])

    # Fill the dp table iteratively
    for i in range(1, n + 1):
        for j in range(1, min(i + 1, lines_left + 1)):
            for d in range(11):
                # Option 1: Don't take the line
                dp[i][j][d] = dp[i - 1][j][min(d + 1, 10)]

                # Option 2: Take the line
                if d == 0:
                    sub, how = dp[i - 1][j - 1][0]
                    sub += graph[i - 1] + (10 - 8)**2  # Assuming distance_since_last is initially 10
                    dp[i][j][d] = min(dp[i][j][d], (sub, how + [i]))

    return dp[n][lines_left][0]






answer = 0
import random
mylist = list(range(100))
random.shuffle(mylist)
from functools import lru_cache


@lru_cache(maxsize=None)
def my_solve_dp(graph, lines_left, distance_since_last):
    if len(graph) < lines_left: return 1e9, []
    if lines_left == 0 and len(graph) == 0: return 0, []

    # option 1: don't take the line
    value = (1e9, [])
    if distance_since_last < 10:
        value = min(value, my_solve_dp(graph[1:], lines_left, distance_since_last+1))

    # option 2: take the line
    if lines_left > 0:
        sub, how = my_solve_dp(graph[1:], lines_left-1, 0)
        sub += graph[0] + (distance_since_last-8)**2
        value = min(value, (sub, how + [len(graph)]))

    return value

answer = solve_iterative(tuple(mylist), len(mylist)//8, 4)
expected = my_solve_dp(tuple(mylist), len(mylist)//8, 4)
assert answer == expected, f'Wrong answer; got {answer} instead of {expected}'
print('All tests passed')