import copy

def question_1():
    while True:
        try:
            s1 = list(map(str, input().strip().split()))
            s1 = s1[0]
            k = 1
            value_ = []
            for i in range(len(s1)):
                if i == len(s1)-1:
                    value_.append(k)
                    break
                if s1[i] != s1[i+1]:
                    value_.append(k)
                    k = 1
                else:
                    k+= 1
            for i in value_:
                ans += int(i*(i+1)/2)
            print(ans)
        except EOFError:
            break

def question_2():
    while True:
        try:
            s1 = list(map(int, input().strip().split()))
            # print(s1)
            flag = True
            for j in range(len(s1)-1, 0, -1):
                if not flag:
                    break
                for i in range(j):
                    sum_ = sum(s1[i:j+1])
                    if sum_ %2 == 1:
                        continue
                    all_ = int(sum_/2)
                    dp = [[0 for _ in range(all_+1)] for i in range(j-i+1)]
                    dp[0][s1[0]] = 1
                    for _ in range(j-i+1):
                        dp[_][0] = 1
                    for k in range(i+1,j+1):
                        for m in range(s1[k],all_+1):
                            dp[k-i][m] = dp[k-1-i][m] + dp[k-i][m-s1[k]]
                    if dp[j-i][all_] != 0:
                        print(all_)
                        flag = False
                        break
            if flag:
                print(0)
        except EOFError:
            break          

def question_3():
    while True:
        try:
            s1 = list(map(int, input().strip().split()))
            s2 = list(map(int, input().strip().split()))
            m = s1[0]
            length = len(s2)
            dp = [[[0,[]] for _ in range(length+1)] for i in range(m+1)]
            # print(dp[0][0][1])
            # input()
            pre = [0 for _ in range(length+1)]
            for i in range(1,length+1):
                pre[i] += s2[i-1]
            dp[1][1][0] = s2[0]
            dp[1][1][1].append(1)
            for i in range(2,length+1):
                dp[1][i][0] = dp[1][i-1][0] + s2[i-1]
                dp[1][i][1].append(i)
            # print(dp)
            # input()
            for i in range(2,m+1):
                dp[i][i][0] = max(dp[i-1][i-1][0], s2[i-1])
                dp[i][i][1] = copy.copy(dp[i-1][i-1][1])
                dp[i][i][1].append(i)
            # print(dp)
            # input()
            for i in range(2, m+1):
                for j in range(i+1, length-m+i+1):
                    ans = s2[j-1]
                    z = j-1
                    dp[i][j][0] = max(dp[i-1][j-1][0],ans)
                    for k in range(j-2, i-2, -1):
                        ans += s2[k]
                        z = k if max(dp[i-1][k][0],ans) < dp[i][j][0] else z
                        dp[i][j][0] = max(dp[i-1][k][0],ans) if max(dp[i-1][k][0],ans) < dp[i][j][0] else dp[i][j][0]
                    
                    dp[i][j][1] = copy.copy(dp[i-1][z][1])
                    dp[i][j][1].append(j)
                    # print(i,z,j)
                    # print(dp[i][j])
                    # input()
            print(dp[m][length][0])
            k = 0
            for i in dp[m][length][1]:
                value_ = []
                while k!= i:
                    value_.append(s2[k])
                    k+=1
                print(value_,end=' ')
        except EOFError:
            break