Harryxun/sft_time huggingface dataset:
### BUGGY CODE ###

import sys
def solve(matrix):
    N = len(matrix)
    #print  matrix
    day = 0
    worst = N * (N-1) / 2
    remaining = worst
    while remaining:
        prev = remaining
        day+=1
        #print "day %d" % day
        #print "matrix: %r" % matrix
        #print "remaining:%d" % remaining
        match = {}
        for i, order in enumerate(matrix):
            me = i+1
            if match.get(me) and order and order[0] in match[me]:
                x = matrix[order[0]-1].pop(0)
                y = order.pop(0)
                remaining -= 1
                #print "%d and %d" % (x, y)
                #print "matrix: %r" % matrix
            elif order:
                if match.get(order[0]):
                    match[order[0]].append(me)
                else:
                    match[order[0]] = [me]
                #print 'match: %r' % match
        if remaining  == prev:
            print -1
            return
    print day



N = raw_input()
N = int(N)

matrix = [] 
for x in range(N):
    matrix.append([int(b) for b in raw_input().split()])
solve(matrix)


### FIXED CODE ###

import sys
import time
def solve(matrix):
    N = len(matrix)
    #print  matrix
    day = 0
    worst = N * (N-1) / 2
    remaining = worst
    start = time.time()
    while remaining:
        prev = remaining
        day+=1
        #print "day %d" % day
        #print "matrix: %r" % matrix
        #print "remaining:%d" % remaining
        match = {}
        for i, order in enumerate(matrix):
            me = i+1
            if match.get(me) and order and order[0] in match[me]:
                x = matrix[order[0]-1].pop(0)
                y = order.pop(0)
                remaining -= 1
                #print "%d and %d" % (x, y)
                #print "matrix: %r" % matrix
            elif order:
                if match.get(order[0]):
                    match[order[0]].append(me)
                else:
                    match[order[0]] = [me]
                #print 'match: %r' % match
        if time.time() - start > 1.5:
            print worst
            return
        if remaining  == prev:
            print -1
            return
    print day



N = raw_input()
N = int(N)

matrix = [] 
for x in range(N):
    matrix.append([int(b) for b in raw_input().split()])
solve(matrix)
### BUGGY CODE ###

n=int(input())
a=[0]*(n-1)
a=list(map(int,input().split()))

for i in range(n):
    print(a.count(i+1))

### FIXED CODE ###

n=int(input())
a=[0]*(n-1)
a=list(map(int,input().split()))
a=sorted(a)
ans=0
target=1
j=0
for i in range(n):
    if (j<n-1):
        while(a[j]==target):
            ans+=1
            j+=1
            #print(j,"here")
            if (j>n-2):
                break
    print(ans)
    ans=0
    target+=1
### BUGGY CODE ###

S = list(input())
Q = int(input())
query = [input().split() for _ in range(Q)]

for i in range(Q):
    if query[i][0] == "1":
        S.reverse()
    else:
        if query[i][1] == "1":
            S.insert(0, query[i][2])
        else:
            S.append(query[i][2])

print("".join(S))

### FIXED CODE ###

S = input()

from collections import deque
S = deque(S)
Q = int(input())
query = [input().split() for _ in range(Q)]
reverse = 0
for i in range(Q):
    if query[i][0] == "1":
        reverse += 1
    else:
        if query[i][1] == "1":
            if reverse % 2 != 0:
                S.append(query[i][2])
            else:
                S.appendleft(query[i][2])
        else:
            if reverse % 2 != 0:
                S.appendleft(query[i][2])
            else:
                S.append(query[i][2])

result = "".join(S)
if reverse % 2 != 0:
    result = result[::-1]

print(result)
### BUGGY CODE ###

N, Q = map(int, input().split())
S = input()
result = []
for i in range(Q):
  l, r = map(int, input().split())
  result.append(S.count('AC',l-1,r))
[print(i) for i in result]

### FIXED CODE ###

n,q=map(int,input().split())
s=input()
t=[0]*(n+1)
for i in range(n):
  t[i+1] = t[i] + (1 if s[i:i+2]=='AC' else 0)
for _ in range(q):
  l,r=map(int,input().split())
  print(t[r-1]-t[l-1])
### BUGGY CODE ###

from math import gcd

n = int(input())
a = list(map(int, input().split()))

d = a[0]
m = a[0]

g = True

for i in range(1, n):
    d = gcd(d, a[i])

if d != 1:
    print("not coprime")
else:
    for i in range(1, n):
        #pairwise
        if gcd(m, a[i]) != 1:
            g = False
            break
        else:
            m *= a[i]

    if not g:
        print("setwise coprime")
    else:
        print("pairwise coprime")

### FIXED CODE ###

from math import gcd

n = int(input())
a = list(map(int, input().split()))

d = a[0]
m = a[0]

g = True

for i in range(1, n):
    d = gcd(d, a[i])

if d != 1:
    print("not coprime")
else:
    while len(a) > 1:
        b = []
        for i in range(0, len(a), 2):
            #print(i, a)
            if i == len(a)-1:
                b.append(a[i])
            else:
                e = gcd(a[i], a[i+1])
                if e != 1:
                    g = False
                    break
                else:
                    b.append(a[i] * a[i+1])
        a = b.copy()
        #print(a)


    if not g:
        print("setwise coprime")
    else:
        print("pairwise coprime")
### BUGGY CODE ###

from collections import deque
import sys
H, W = map(int, input().split())
ch, cw = map(int, input().split())
dh, dw = map(int, input().split())
ch, cw, dh, dw = ch-1, cw-1, dh-1, dw-1
S = [input() for _ in range(H)]
d = [[0]*W for _ in range(H)]

que = deque([[cw, ch]])
count = 0
while que:
    while que:
        x, y = que.popleft()
        if x == dw and y == dh:
            print(count)
            sys.exit()
                
        d[y][x] = -1
        for i in range(-2, 3):
            for j in range(-2, 3):
                nnx, nny = x+i, y+j
                if 0<=nnx<W and 0<=nny<H and d[nny][nnx]==0 and S[nny][nnx]!='#':
                    d[nny][nnx] = 1
        
        for dx, dy in [1, 0], [0, 1], [-1, 0], [0, -1]:
            nx, ny = x+dx, y+dy
            if 0<=nx<W and 0<=ny<H and S[ny][nx]!='#' and d[ny][nx]!=-1:
                if nx == dw and ny == dh:
                    print(count)
                    sys.exit()
                
                d[ny][nx] = -1
                for i in range(-2, 3):
                    for j in range(-2, 3):
                        nnx, nny = nx+i, ny+j
                        if 0<=nnx<W and 0<=nny<H and d[nny][nnx]==0 and S[nny][nnx]!='#':
                            d[nny][nnx] = 1
                que.append([nx, ny])
                
    for i in range(W):
        for j in range(H):
            if d[j][i] == 1:
                d[j][i] == -1
                que.append([i, j])
    count += 1
print(-1)

### FIXED CODE ###

from collections import deque
H, W = map(int, input().split())
ch, cw = map(int, input().split())
dh, dw = map(int, input().split())
ch, cw, dh, dw = ch-1, cw-1, dh-1, dw-1
s = [input() for _ in range(H)]

d = [[-1]*W for _ in range(H)]

que = deque([[cw, ch, 0]])
while que:
    x, y, cost = que.popleft()
    if d[y][x]==-1 or d[y][x]>cost:
        d[y][x] = cost
        for dx in range(-2, 3):
            for dy in range(-2, 3):
                nx, ny = x+dx, y+dy
                if 0<=nx<W and 0<=ny<H and s[ny][nx]!='#':
                    if abs(dx)+abs(dy) == 1:
                        que.appendleft([nx, ny, cost])
                    else:
                        que.append([nx, ny, cost+1])  
print(d[dh][dw])
### BUGGY CODE ###

N = int(input())
A = [int(a) for a in input().split()]
X = [[] for i in range(N)]
for i in range(N-1):
    x, y = map(int, input().split())
    x, y = x-1, y-1
    X[x].append(y)
    X[y].append(x)

def EulerTour(n, X, i0):
    def bl(k):
        l, r = -1, n
        while r - l > 1:
            m = (l + r) // 2
            if L[m][-1] < k:
                l = m
            else:
                r = m
        return l + 1

    inf = 1 << 30
    P = [-1] * n
    Q = [~i0, i0]
    ANS = [0] * n
    L = [[inf] for _ in range(n)]
    I = [0] * n
    while Q:
        i = Q.pop()
        if i < 0:
            i = ~i
            L[I[i]].pop()
            continue
        if i >= 0:
            k = A[i]
            b = bl(k)
            L[b].append(k)
            I[i] = b
            ANS[i] = bl(inf)
        for a in X[i][::-1]:
            if a != P[i]:
                P[a] = i
                for k in range(len(X[a])):
                    if X[a][k] == i:
                        del X[a][k]
                        break
                Q.append(~a)
                Q.append(a)
    return ANS

print("\n".join(map(str, EulerTour(N, X, 0))))

### FIXED CODE ###

N = int(input())
A = [int(a) for a in input().split()]
X = [[] for i in range(N)]
for i in range(N-1):
    x, y = map(int, input().split())
    x, y = x-1, y-1
    X[x].append(y)
    X[y].append(x)

def EulerTour(n, X, i0):
    def bl(k):
        l, r = -1, n
        while r - l > 1:
            m = (l + r) // 2
            if L[m][-1] < k:
                l = m
            else:
                r = m
        return l + 1

    inf = 1 << 30
    P = [-1] * n
    Q = [~i0, i0]
    ANS = [0] * n
    L = [[inf] for _ in range(n)]
    I = [0] * n
    while Q:
        i = Q.pop()
        if i < 0:
            i = ~i
            L[I[i]].pop()
            continue
        if i >= 0:
            k = A[i]
            b = bl(k)
            L[b].append(k)
            I[i] = b
            ANS[i] = bl(inf)
        for a in X[i][::-1]:
            if a != P[i]:
                P[a] = i
                for k in range(len(X[a])):
                    if X[a][k] == i:
                        del X[a][k]
                        break
                Q.append(~a)
                Q.append(a)
    return ANS

print("\n".join(map(str, EulerTour(N, X, 0))))
### BUGGY CODE ###

def solve(n, a):
    from itertools import accumulate

    inf = (400 ** 2) * (10 ** 9) + 10

    # [l,r)
    def dfs(l, r):
        if memo[l][r] != -1:
            return memo[l][r]
        if r - l == 1:
            return 0
        res = inf
        for c in range(l + 1, r):
            # [l, c), [c, r)
            res = min(res, dfs(l, c) + dfs(c, r))
        res += acc[r] - acc[l]
        memo[l][r] = res
        return res

    acc = (0,) + tuple(accumulate(a))
    memo = [[-1] * (n + 1) for _ in range(n + 1)]

    return dfs(0, n)


if __name__ == '__main__':
    n = int(input())
    a = tuple(map(int, input().split()))
    print(solve(n, a))


### FIXED CODE ###

# https://kyopro-friends.hatenablog.com/entry/2019/01/12/231035


def div_cost(left, right):
    # 区間[left, right]が一匹にまとまっているとき、それを分解するために必要な最小コスト
    if bl_calculated[left][right]:
        return memo[left][right]
    bl_calculated[left][right] = True
    if left == right:
        memo[left][right] = 0
        return memo[left][right]
    divided_to_alone_cost = INF
    # divided_to_alone_cost: 区間[left, right]を分解してできた2つの区間それぞれをaの各要素まで分解し切るのに必要なコスト
    for mid in range(left, right):
        divided_to_alone_cost = min(divided_to_alone_cost, div_cost(left, mid) + div_cost(mid + 1, right))
    memo[left][right] = divided_to_alone_cost + (c_sum[right] - c_sum[left - 1])
    # (c_sum[right] - c_sum[left - 1]): 区間[left, right]を分解するのにかかるコスト
    return memo[left][right]


INF = float('inf')

N = int(input())
a = list(map(int, input().split()))

c_sum = [0]
for aa in a:
    c_sum.append(c_sum[-1] + aa)
# 累積和c_sum

memo = [[0 for _ in range(N + 1)] for _ in range(N + 1)]
# memo[left][right] = (区間[left, right]に相当するスライムが一匹にまとまっているとき、それを分解するために必要な最小コスト)

bl_calculated = [[False for _ in range(N + 1)] for _ in range(N + 1)]
# memo[left][right]に最小コストが代入済かどうかのBoolean

print(div_cost(1, N))
### BUGGY CODE ###

import numpy as np

N = int(input())
A_ = list(map(int, input().split()))

A_ = sorted(A_)
A = np.array(A_)
ans = 0

for X in range(A[0],A[-1]+1):
    tmp = np.sum((X-1 <= A) & (A<= X+1))
    ans = max(tmp,ans)
print(ans)


### FIXED CODE ###

import collections

N = int(input())
A = sorted(list(map(int, input().split())))

dic = collections.Counter(A)
tmp = [0 for _ in range(A[-1]+1)]


for X in dic.keys():
    tmp[X] = dic[X]

ans = 0
for i in range(len(tmp)):
    ans = max(ans,sum(tmp[i:i+3]))

print(ans)
### BUGGY CODE ###

A, B, K = list(map(int, input().strip().split(' ')))
tmplist = list([i for i in range(A,B+1)])
newlist=[]
for j in range(len(tmplist)):
    if not(tmplist[j] >= A+K and tmplist[j] <= B-K):
        newlist.append(tmplist[j])

for k in newlist:
    print(k)


### FIXED CODE ###

A, B, K = list(map(int, input().strip().split(' ')))
for j in range(A,min(A+K,B+1)):
    if not(j >= A+K and j <= B-K):
        print(j)
for i in range(max(B-K,j+1),B+1):
    if not(i >= A+K and i <= B-K):
        print(i)
### BUGGY CODE ###

import bisect, collections, copy, heapq, itertools, math, string, sys
input = lambda: sys.stdin.readline().rstrip() 
sys.setrecursionlimit(10**7)
INF = float('inf')
def I(): return int(input())
def F(): return float(input())
def SS(): return input()
def LI(): return [int(x) for x in input().split()]
def LI_(): return [int(x)-1 for x in input().split()]
def LF(): return [float(x) for x in input().split()]
def LSS(): return input().split()

def resolve():
    H, W = LI()
    S = [list(SS()) for _ in range(H)]

    idx_w = []
    for i in range(H):
        tmp = [-1]
        for j in range(W):
            if S[i][j] == '#':
                tmp.append(j)
        tmp.append(W)
        idx_w.append(tmp)

    idx_h = []
    for i in range(W):
        tmp = [-1]
        for j in range(H):
            if S[j][i] == '#':
                tmp.append(j)
        tmp.append(H)
        idx_h.append(tmp)

    ans = [[0] * W for _ in range(H)]
    for i in range(H):
        for j in range(len(idx_w[i]) - 1):
            for k in range(idx_w[i][j] + 1, idx_w[i][j+1]):
                ans[i][k] += idx_w[i][j+1] - idx_w[i][j] - 1

    for i in range(W):
        for j in range(len(idx_h[i]) - 1):
            for k in range(idx_h[i][j] + 1, idx_h[i][j+1]):
                ans[k][i] += idx_h[i][j+1] - idx_h[i][j] - 2

    # for i in ans:
    #     print(i)

    print(max([max(i) for i in ans]))

if __name__ == '__main__':
    resolve()


### FIXED CODE ###

import bisect, collections, copy, heapq, itertools, math, string, sys
input = lambda: sys.stdin.readline().rstrip() 
sys.setrecursionlimit(10**7)
INF = float('inf')
def I(): return int(input())
def F(): return float(input())
def SS(): return input()
def LI(): return [int(x) for x in input().split()]
def LI_(): return [int(x)-1 for x in input().split()]
def LF(): return [float(x) for x in input().split()]
def LSS(): return input().split()

def resolve():
    H, W = LI()
    S = [list(SS()) for _ in range(H)]

    idx_w = []
    for i in range(H):
        tmp = [-1]
        for j in range(W):
            if S[i][j] == '#':
                tmp.append(j)
        tmp.append(W)
        idx_w.append(tmp)

    idx_h = []
    for i in range(W):
        tmp = [-1]
        for j in range(H):
            if S[j][i] == '#':
                tmp.append(j)
        tmp.append(H)
        idx_h.append(tmp)

    ans = [[0] * W for _ in range(H)]
    for i in range(H):
        for j in range(len(idx_w[i]) - 1):
            for k in range(idx_w[i][j] + 1, idx_w[i][j+1]):
                ans[i][k] += idx_w[i][j+1] - idx_w[i][j] - 1

    for i in range(W):
        for j in range(len(idx_h[i]) - 1):
            for k in range(idx_h[i][j] + 1, idx_h[i][j+1]):
                ans[k][i] += idx_h[i][j+1] - idx_h[i][j] - 2

    # for i in ans:
    #     print(i)

    print(max([max(i) for i in ans]))

if __name__ == '__main__':
    resolve()
### BUGGY CODE ###

N=int(raw_input())
a=[-1]
for _ in range(N):
    a.append(int(raw_input()))


if not 2 in a:
    print -1
else:
    alr=[]
    i=1
    c=1
    while(c<=N):
        if a[i]==2:
            print c
            break
        elif i in alr:
            print -1
            break
        else:
            alr.append(i)
            i=a[i]
            c+=1

    if c>N:
        print -1
            
        

### FIXED CODE ###

N=int(raw_input())
a=[-1]
for _ in range(N):
    a.append(int(raw_input()))
 
 
i=1
c=0
while(1):
    if i==2:
        print c
        break
    elif c>=N:
        print -1
        break
    c+=1
    i=a[i]
### BUGGY CODE ###

from collections import deque

N = int(input())
graph = [[] for _ in range(N+1)] #木構造を入れておく
long = [0] * (N+1) #Kから任意のノードまでの距離

for i in range(N-1):
  x, y, z = map(int, input().split())
  graph[x].append([y, z])
  graph[y].append([x, z])
  
Q, K = map(int, input().split())
x = list()
y = list()

for i in range(Q):
  x_i, y_i = map(int, input().split())
  x.append(x_i)
  y.append(y_i)

  
for i in range(1,N+1): #Kから任意のノードまでの距離を求める
  q = deque([K])
  while q:
    t = q.popleft()
    for i in range(len(graph[t])):
      next_t = graph[t][i][0]
      if(long[next_t] > 0):
        continue
        
      else:
        q.append(next_t)
        long[next_t] = long[t] + graph[t][i][1]
        

for i in range(Q):
  ans = long[x[i]] + long[y[i]]
  print(ans)

### FIXED CODE ###

import sys
sys.setrecursionlimit(500000)
 
N = int(input())
ABC = [list(map(int, input().split())) for i in range(N-1)]
Q, K = map(int, input().split())
D = [0] * (N+1)
L = [[] for i in range(N+1)]
for a, b, c in ABC:
    L[a].append([b, c])
    L[b].append([a, c])
 
 
def dfs(n, np):
    for nc in L[n]:
        if nc[0] == np:
            continue
        else:
            D[nc[0]] = D[n] + nc[1]
            dfs(nc[0], n)
 
 
dfs(K, 0)
for i in range(Q):
    x, y = map(int, input().split())
    print(D[x] + D[y])
### BUGGY CODE ###


def main(s,perse):
    query = input().split()
    query[0] = int(query[0])
    if query[0] == 1:
        return s,-perse
    else:
        query[1] = int(query[1])
        if query[1] == 1:
            if perse == 1:
                s.insert(0,query[2])
            else:
                s.append(query[2])
        if query[1] == 2:
            if perse == -1:
                s.insert(0,query[2])
            else:
                s.append(query[2])
        return s,perse
def conv(s):
    a = []
    for i in range(len(s)):
        a.append(s[i])
    return a

s = input()
s = conv(s)
q = int(input())
perse = 1
for i in range(q):
    s,perse = main(s,perse)
if perse == -1:
    s.reverse()
print(''.join(s))

### FIXED CODE ###

def main(s,end,start,perse):
    start.reverse()
    start.append(''.join(s))
    start.append(''.join(end))
    if perse == -1:
        start.reverse()
    print(''.join(start))
def conv(s):
    a = []
    for i in range(len(s)):
        a.append(s[i])
    return a
perse = 1
start = []
end = []
  
s = input()
q = int(input())
for i in range(q):
    query = input().split()
    query[0] = int(query[0])
    if query[0] == 1:
        perse = -perse
    else:
        query[1] = int(query[1])
        if (int(query[1])*2-3)*perse == 1:
            end.append(query[2])
        else:
            start.append(query[2])
s =  conv(s)
if perse == -1:
    s.reverse()
    end.reverse()
main(s,end,start,perse)
### BUGGY CODE ###

N, K = map(int, input().split())
MOD = 998244353
S = set()
for i in range(K):
    l, r = map(int, input().split())
    for i in range(l, r + 1):
        S.add(i)

dp = [0] * N
dp[0] = 1
for i in range(1, N):
    for s in S:
        if s > i:
            continue
        dp[i] += dp[i - s]
print(dp[-1] % MOD)


### FIXED CODE ###

N, K = map(int, input().split())
MOD = 998244353

L = []
R = []
for i in range(K):
    l, r = map(int, input().split())
    L.append(l)
    R.append(r)

dp = [0] * (N + 1)
dp[1] = 1
dp_sum = [0] * (N + 1)
dp_sum[1] = 1
for i in range(2, N + 1):
    for j in range(K):
        li = max(i - R[j], 1)
        ri = i - L[j]
        if ri < 1:
            continue
        dp[i] += (dp_sum[ri] - dp_sum[li - 1]) % MOD
    dp_sum[i] = (dp_sum[i - 1] + dp[i]) % MOD

print(dp[-1] % MOD)
### BUGGY CODE ###

h, w = map(int, input().split())
black = {}
white = {}

for ln in range(h):
    line = input().rstrip()
    for i, letter in enumerate(line):
        if letter == '.':
            white[(ln, i)] = letter
        elif letter == '#':
            black[(ln, i)] = letter

count = 0


while len(white) > 0:
    count += 1
    next = {}
    for row, col in black.keys():
        for r, c in [(row - 1, col), (row + 1, col), (row, col - 1), (row, col + 1)]:
            if white.get((r, c)):
                next[(r, c)] = white.pop((r, c))
    black.clear()
    for k, v in next.items():
        black[k] = v

print(count)

### FIXED CODE ###

from collections import deque
h, w = map(int, input().split())
que = deque()
data = []

for ln in range(h):
    line = list(input().rstrip())
    data.append(line)
    for r, letter in enumerate(line):
        if letter == '#':
            que.append((ln, r))

count = 0
while len(que) > 0:
    count += 1
    next = deque()
    while len(que) > 0:
        row, col = que.popleft()
        for r, c in [(row - 1, col), (row + 1, col), (row, col - 1), (row, col + 1)]:
            if 0 <= r < h and 0 <= c < w and data[r][c] == '.':
                next.append((r, c))
                data[r][c] = '#'
    que = next

print(count - 1)
### BUGGY CODE ###

from collections import deque
def fi(i, x):
    a, b = lines[i]
    return a*x+b

def find(x):
    if len(lines) == 1:
        return 0
    def f(i):
        # 0<=i<len(lines)-1
        return fi(i+1,x) > fi(i,x)
    mn, mx = 0, len(lines)-2
    idx = (mn+mx)//2
    if f(mn):
        return 0
    if not f(mx):
        return mx+1
    while mx-mn>1:
        if f(idx):
            mx, idx = idx, (mn + idx)//2
            continue
        mn, idx = idx, (mx + idx)//2
    return idx+1

def remove_lines():
    (x, y) = lines.popleft()
    a, b = x, y
    (e, f) = lines[0]
    while len(lines)-1:
        (c, d), (e, f) = (e, f), lines[1]
        if (c-e)*(b-d) < (d-f)*(a-c):
            break
        lines.popleft()
    lines.appendleft((x, y))

def insert(a, b):
    lines.appendleft((a, b))
    if len(lines) >= 3:
        remove_lines()

N, C = map(int, input().split())
hs = map(int, input().split())
r = 0
lines = deque([])
for i, h in enumerate(hs):
    if i!= 0:
        r = fi(find(h), h) + h**2+C
    insert(-2*h, r+h**2)
print(r)


### FIXED CODE ###

def fi(i, x):
    a, b = lines[i]
    return a*x+b

def find(x):
    if len(lines) == 1:
        return 0
    def f(i):
        # 0<=i<len(lines)-1
        return fi(i+1,x) > fi(i,x)
    mn, mx = 0, len(lines)-2
    idx = (mn+mx)//2
    if f(mn):
        return 0
    if not f(mx):
        return mx+1
    while mx-mn>1:
        if f(idx):
            mx, idx = idx, (mn + idx)//2
            continue
        mn, idx = idx, (mx + idx)//2
    return idx+1

def remove_lines():
    (x, y) = lines.pop()
    a, b  = x, y
    (e, f) = lines[-1]
    while len(lines)-1:
        (c, d), (e, f) = (e, f), lines[-2]
        if (c-e)*(b-d) < (d-f)*(a-c):
            break
        lines.pop()
    lines.append((x, y))

def insert(a, b):
    lines.append((a, b))
    if len(lines) >= 3:
        remove_lines()

N, C = map(int, input().split())
hs = map(int, input().split())
r = 0
lines = []
for i, h in enumerate(hs):
    if i!= 0:
        r = fi(find(h), h) + h**2+C
    insert(-2*h, r+h**2)
print(r)
### BUGGY CODE ###

N,K=list(map(int,input().split()))
hcost=list(map(int,input().split()))
hcost=[0]+hcost
dp=[0]*(N+1)
tmp=range(K+1)

for i in range(2,N+1):
  dp[i]=dp[i-1]+abs(hcost[i-1]-hcost[i])
  for k in tmp:
    if i-k > 0:
      dp[i]=min(dp[i],dp[i-k]+abs(hcost[i-k]-hcost[i]))
print(dp[N])      

### FIXED CODE ###

N,K= list(map(int,input().split()))
hc=list(map(int,input().split()))
dp=[0]*N
for i in range(1,N):
  li=[abs(hc[i]-hc[j])+dp[j] for j in range( max(i-K,0),i) ]
  dp[i]=min(li)
print(dp[-1])