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

def main():
    n, k = map(int, input().rstrip("\n").split(" "))
    costs = list(map(int, input().rstrip("\n").split(" ")))
    volumes = list(map(int, input().rstrip("\n").split(" ")))
    
    costs.sort()
    volumes.sort(reverse=True)
    from heapq import heappush, heappop
    queue = []
    total_cost = 0
    for id, (cost, volume) in enumerate(zip(costs, volumes)):
        total_cost += cost
        heappush(queue, (cost * volume * -1,id, cost, volume))
    for i in range(min(total_cost, k)):
        
        duration, id, cost, volume = heappop(queue)
        cost -= 1
        if cost > 0:
            heappush(queue, (cost * volume * -1, id, cost, volume) )
        
        if not queue:
            break
    if queue:
        result = min([duration for duration, id, cost, volume in queue])
        print(result * -1)
    else:
        print(0)
    

if __name__ == '__main__':
  main()



### FIXED CODE ###

def check(limit, max_training, costs, volumes):
    from math import floor
    remain_training = max_training
    for id, (cost, volume) in enumerate(zip(costs, volumes)):
        if cost * volume <= limit:
            continue
        else:
            lowest_cost = floor(limit / volume)
            remain_training -= (cost - lowest_cost)
        if remain_training < 0:
            return False
    return True


def main():
    n, k = map(int, input().rstrip("\n").split(" "))
    costs = list(map(int, input().rstrip("\n").split(" ")))
    volumes = list(map(int, input().rstrip("\n").split(" ")))

    costs.sort()
    volumes.sort(reverse=True)
    queue = []
    total_cost = 0

    success = False

    max_cost = max([cost * volume for cost, volume in zip(costs, volumes)])
    min_cost = 0

    while (min_cost + 1) < max_cost:
        center_cost = (min_cost + max_cost) // 2
        success = check(center_cost, k, costs, volumes)
        if success:
            max_cost = center_cost
        else:
            min_cost = center_cost
    if check(min_cost, k, costs, volumes):
        print(min_cost)
    else:
        print(max_cost)


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

from decimal import *
#exp = Decimal(10**23)
#rint((Decimal(11)*exp)/Decimal(10))

## coding: UTF-8
s = input().split()
t = [int(p) for p in s]
#print(t)

a = t[0]
b = t[1]
x = t[2]

start = a
goal = b
while True:
    if(start % x == 0):
        break
    else:
        start += 1
#print(start)
while True:
    if(goal % x == 0):
        break
    else:
        goal -= 1
#start = Decimal(3)
#goal = Decimal(999999999999999999)

#print(Decimal(goal))
print(Decimal(Decimal(Decimal(goal) - Decimal(start)) / Decimal(x)) + Decimal(1)  ) 
#answer = ((goal - start) / x ) + 1
#print('{}'.format(int(answer)))

### FIXED CODE ###

from decimal import *
#exp = Decimal(10**23)
#rint((Decimal(11)*exp)/Decimal(10))

## coding: UTF-8
s = input().split()
t = [int(p) for p in s]
#print(t)

a = t[0]
b = t[1]
x = t[2]

'''
start = a
goal = b
while True:
    if(start % x == 0):
        break
    else:
        start += 1
#print(start)
while True:
    if(goal % x == 0):
        break
    else:
        goal -= 1
#start = Decimal(3)
#goal = Decimal(999999999999999999)

#print(Decimal(goal))
print(Decimal(Decimal(Decimal(goal) - Decimal(start)) / Decimal(x)) + Decimal(1)  ) 
#answer = ((goal - start) / x ) + 1
#print('{}'.format(int(answer)))
'''

def count_even(t, x):
    return int( Decimal(t)/ Decimal(x) )

if( a == 0):
    answer = count_even(b, x) + 1
else:
    answer = count_even(b, x) - count_even(a-1, x)
print(answer)
### BUGGY CODE ###

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

Bcon = [sum([1 for i in A if i < B[j]]) for j in range(N)]
Ccon = [sum([Bcon[n] for n, i in enumerate(B) if i < C[j]]) for j in range(N)]

print(sum(Ccon))

### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
C = list(map(int, input().split()))
A.sort()
B.sort()
C.sort()

Bcon = [0] * (N + 1)
res = 0
p = 0
for n in range(N):
    while p <= N - 1 and B[n] > A[p]:
        p += 1
    Bcon[n + 1] = p + Bcon[n]
    
p = 0
for n in range(N):
    while p <= N - 1 and C[n] > B[p]:
        p += 1
    res += Bcon[p]
    
print(res)
### BUGGY CODE ###

# 初期入力
N = int(input())
word = [ input() for i in range(N) ]

# 単語をキーに数を数えて辞書
from collections import Counter
kazu_word = Counter(word)

#一番多い単語を抜き出す
kazu_word_max =[i for i,v in kazu_word.items() if v == max(kazu_word.values())]
kazu_word_max_sorted = sorted(kazu_word_max)
"""
print(kazu_word)
print(kazu_word_max)
"""
#print(*kazu_word_max_sorted,sep="\n")
print("\n".join(kazu_word_max_sorted))

### FIXED CODE ###

# 初期入力
N = int(input())
word = [ input() for i in range(N) ]

# 単語をキーに数を数えて辞書
from collections import Counter
kazu_word = Counter(word)

#一番多い単語を抜き出す
kazu_word_a = max(kazu_word.values()) #　内包表記の中で毎回MAXを計算するより出したほうが１回で済む
kazu_word_max =[i for i,v in kazu_word.items() if v == kazu_word_a ]
kazu_word_max_sorted = sorted(kazu_word_max)
"""
print(kazu_word)
print(kazu_word_max)
"""
print(*kazu_word_max_sorted,sep="\n")
### BUGGY CODE ###

import fractions

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

A.sort(reverse=True)

#A[1] = A[0]

max_gcd = 1

for i in range(N):
    gcd_num = -1

    for j, a in enumerate(A):
        if i == j:
            continue

        if gcd_num == -1:
            gcd_num = a
            continue

        gcd_num = fractions.gcd(gcd_num, a)

    max_gcd = max(max_gcd, gcd_num)

print(max_gcd)


### FIXED CODE ###

import fractions

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

left = [0] * (N + 1)
right = [0] * (N + 1)

for i in range(N):
    left[i + 1] = fractions.gcd(A[i], left[i])

for i in reversed(range(N)):
    right[i] = fractions.gcd(A[i], right[i + 1])

max_gcd = 1

for i in range(N):

    l = left[i]
    r = right[i + 1]

    gcd_num = fractions.gcd(l, r)

    max_gcd = max(max_gcd, gcd_num)

print(max_gcd)
### BUGGY CODE ###

import sys
N,W=map(int,input().split())
dp=[[0 for i in range(W+1)] for j in range(N+1)]
input=sys.stdin.readline

for i in range(1,N+1):
    w,v=map(int,input().split())
    for j in range(1,W+1):
        if j-w>=0:
            dp[i][j]=max(dp[i-1][j],dp[i-1][j-w]+v)
        else:
            dp[i][j]=dp[i-1][j]
print(dp[-1][-1])

### FIXED CODE ###

N,W=map(int,input().split())
dp=[[0 for i in range(W+1)] for j in range(N+1)]

for i in range(1,N+1):
    w,v=map(int,input().split())
    for j in range(1,W+1):
        if j-w>=0:
            dp[i][j]=max(dp[i-1][j],dp[i-1][j-w]+v)
        else:
            dp[i][j]=dp[i-1][j]
print(dp[-1][-1])
### BUGGY CODE ###

def main():
    H,N = map(int,input().split())
    AB = [list(map(int,input().split())) for _ in range(N)]
    INF = float('inf')
    maxA = max(A for A,B in AB)
    dp = [INF]*(H+maxA)
    dp[0] = 0
    for i in range(1,H+maxA):
        dp[i] = min(dp[i-A]+B for A,B in AB)
    print(min(dp[H:]))


if __name__ == '__main__':
    main()

### FIXED CODE ###

def main():
    H,N = map(int,input().split())
    AB = [list(map(int,input().split())) for _ in range(N)]
    maxA = max(A for A,B in AB)
    dp = [0]*(H+maxA)
    for i in range(0,H+maxA):
        if i <= 0:
            dp[i] = 0
        else:
            dp[i] = min(dp[i-A]+B for A,B in AB)
    print(min(dp[H:]))


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

import itertools


def main():
    N = int(input())
    S = input()
    id_l = [i for i in range(N)]

    ans = 0
    for v in itertools.permutations(id_l, 3):
        if v[0] < v[1] < v[2]:
            if (v[2] - v[1]) != (v[1] - v[0]):
                if (S[v[0]] != S[v[1]]) and (S[v[1]] != S[v[2]]) and (S[v[0]] != S[v[2]]):
                    ans += 1
    print(ans)
    return 0

if __name__ == '__main__':
    main()

### FIXED CODE ###

import math
import collections

def main():
    N = int(input())
    S = input()

    c = collections.Counter(S)
    c = c['R'] * c['G'] * c['B']

    count = 0
    for i in range(N):
        for j in range(i+1, N):
            k = 2*j-i
            if k < N:
                if (S[i] != S[j]) and (S[j] != S[k]) and (S[i] != S[k]):
                    count += 1

    print(c - count)

    return 0

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

N,M = map(int,input().split())    
    
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]
    
    def same(self, x, y):
        return self.find(x) == self.find(y)

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())
    
A=[None]*M
B=[None]*M

uf = UnionFind(N)
for i in range(M):
    a,b = map(int,input().split())
    uf.union(a-1,b-1)
for i in range(N):
    c = uf.find(i)
    
root = uf.roots()
print( max(len(uf.members(r)) for r in root) )

### FIXED CODE ###

N,M = map(int,input().split())    
       
AB = [None]*M
for i in range(M):
    a,b = map(int,input().split())
    if a>b:
        a,b=b,a
    AB[i] = (a-1,b-1)

AB=set(AB)

tree=[[] for _ in range(N)]
for a,b in AB:
    tree[a].append(b)
    tree[b].append(a) #aがbの親、とかが保証されてれば不要。

from collections import deque

groups=[]
been=[0]*N
for i in range(N):
    if been[i]==0:
        group=[i]
        been[i]=1
        q = deque([(i,togo) for togo in tree[i]]) 
        while q:
            parent,x = q.popleft()
            if been[x]==1:
                continue
            been[x]=1
            group.append(x)
            for y in tree[x]:
                if y == parent:#親ノードを飛ばし
                    continue
                q.append((x,y))#子ノードを追加
        groups.append(group)

print(max( len(g) for g in groups))
### BUGGY CODE ###

N, K = map(int, input().split())
P = list(map(int, input().split()))

tmp = 0

for i in range(0, N - K + 1):
  max_value = 0
  for j in range(K):
    max_value += (P[i+j]+1)/2
  if max_value >= tmp: 
    tmp = max_value

print("{:.12f}".format(tmp))

### FIXED CODE ###

import queue

N, K = map(int, input().split())
P = list(map(int, input().split()))

q = queue.Queue()

#arr = [(n+1)/2 for n in P]
mx = 0
s = 0

for i in range(N):
  s += P[i]+1
  q.put(P[i]+1)
  if q.qsize() > K:
    s -= q.get()
  if q.qsize() == K:
    mx = max(mx, s)

ans = mx/2
print(ans)
### BUGGY CODE ###

#coding:utf-8
import sys
sys.setrecursionlimit(10**6)
write = sys.stdout.write
dbg = lambda *something : print(*something) if DEBUG else 0
DEBUG = False
def main(given = sys.stdin.readline):
    input = lambda : given().rstrip()
    LMIIS = lambda : list(map(int,input().split()))
    II = lambda : int(input())
    XLMIIS = lambda x : [LMIIS() for _ in range(x)]
    N,K =LMIIS()
    A = LMIIS()
    A.sort()
    # print(A)
    MOD = 10**9+7
    ans = 0
    import itertools
    C = itertools.combinations(A,K)
    def f(L):
        return (L[-1] - L[0])%MOD
    for i in map(f,C):
        ans += i
        ans %= MOD
    print(ans)






if __name__ == '__main__':
    main()

### FIXED CODE ###

#coding:utf-8
import sys
sys.setrecursionlimit(10**6)
write = sys.stdout.write
dbg = lambda *something : print(*something) if DEBUG else 0
DEBUG = True
class Combination:
    def __init__(self,N,P=10**9+7):
        if N > 10**7:
            self.fact = lambda x: x * self.fact(x-1) % P if x > 2 else 2
            self.perm = lambda x, r: x * self.perm(x-1,r-1) % P if r > 0 else 1
            self.cmb = lambda n,r: (self.perm(n,min(n-r,r)) * pow(self.fact(min(n-r,r)) ,P-2 ,P) % P) if r > 0 else 1
        else:
            self.__fact = [1] * (N+1)
            self.__inv = [1] * (N+1)
            self.__inv_fact = [1] * (N+1)
            for i in range(2,N+1):
                self.__fact[i] = self.__fact[i-1] * i % P
                self.__inv[i] = - self.__inv[P%i] * (P//i) % P
                self.__inv_fact[i] = self.__inv_fact[i-1] * self.__inv[i] % P
            self.fact = lambda n: self.__fact[n]
            self.perm = lambda n,r: self.__fact[n] * self.__inv_fact[n-r] % P
            self.cmb = lambda n,r: (self.__fact[n] * self.__inv_fact[n-r] * self.__inv_fact[r] % P) if n >= r > 0 else 0 if r > n else 1
def main(given = sys.stdin.readline):
    input = lambda : given().rstrip()
    LMIIS = lambda : list(map(int,input().split()))
    II = lambda : int(input())
    XLMIIS = lambda x : [LMIIS() for _ in range(x)]
    N,K =LMIIS()
    A = LMIIS()
    A.sort()
    cmb = Combination(N)
    ans = 0
    P = 10**9+7
    for i,a in enumerate(A):
        ans = (ans + cmb.cmb(i,K-1)*a - cmb.cmb(N-i-1,K-1)*a)%P
    print(ans)


    






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

#import heapq

def dice(p):
    return (1+p)/2
    #sum = 0
    #for i in range(1,p+1):
    #    sum += i/p
    #return sum

n,k = list(map(int,input().split()))
p = list(map(int,input().split()))

m = 0
l = []
for i in range(n-k+1):
    t = sum(p[i:i+k])
    if(m <= t):
        l = p[i:i+k]
        m = t
#print(l)
#l = heapq.nlargest(k, p)
#print(l)


dist = {}
res = 0
for i in l:
    if i in dist:
        ans = dist[i]
    else:
        dist[i] = dice(i)
    res += dice(i)

print(res)











### FIXED CODE ###

n, k = map(int, input().split())
p = list(map(int, input().split()))
num_li = [0]*n
for i in range(n):
    num_li[i] = (p[i]+1)/2

num = sum(num_li[:k])
ans = num
for j in range(n-k):
    num = num - num_li[j] + num_li[j+k]
    ans = max(num,ans)

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

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

x = [1]*(a[0]-a[1]+1)

for i in range(a[1]-1,len(b)):
    for j in range(0,a[1]):
        x[i-(a[1]-1)] = x[i-a[1]+1]*b[i-j]

for i in range(1, len(x)):
    if int(x[i]) > int(x[i-1]):
        print("Yes")
    else:
        print("No")

### FIXED CODE ###

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

for i in range(a[1],len(b)):
    if b[i]>b[i-a[1]]:
        print("Yes")
    else:
        print("No")
### BUGGY CODE ###

INF = float("inf")

import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline
input_int = lambda:int(input())
input_ints = lambda:map(int,input().split())
input_ints_list = lambda:list(input_ints())
input_str = lambda:input()
input_strs = lambda:input().split()
input_lines = lambda n,input_func:[input_func() for _ in range(n)]

import importlib
import_module = lambda module_name:importlib.import_module(module_name)

init_array_1dim = lambda value,n:[value]*n # 1次元配列を生成
init_array_2dim = lambda value,n,m:[init_array_1dim(value,n) for _ in range(m)] # 2次元配列を生成

gcd_base = lambda value1,value2:import_module('fractions').gcd(value1,value2) # 最大公約数（2値)
gcd = lambda lst:import_module('functools').reduce(gcd_base,lst) # 最大公約数（リスト）
lcm_base = lambda value1,value2:(value1*value2)//gcd_base(value1,value2) # 最小公倍数(2値)
lcm = lambda lst:import_module('functools').reduce(lcm_base,lst,1) # 最小公倍数(リスト)

permutations = lambda lst,n:import_module('itertools').permutations(lst,n) # 順列
combinations = lambda lst,n:import_module('itertools').combinations(lst,n) # 組み合わせ
product = lambda lst1,lst2:import_module('itertools').product(lst1,lst2) # 二つのリストの直積

round = lambda value:round(value) # 四捨五入
ceil = lambda value:import_module('math').ceil(value) # 切り上げ
floor = lambda value:import_module('math').floor(value) # 切り捨て

# キュー
init_q = lambda lst: import_module('collections').deque(lst)
q_pop = lambda q: q.popleft() # 先頭から取り出し
q_push = lambda q,value:q.appendleft(value) # 先頭に追加（値）
q_pushlist = lambda q,lst:q.extendleft(lst) # 先頭に追加（リスト）
q_append = lambda q,value:q.append(value) # 末尾に追加（値）
q_appendlist = lambda q,lst:q.extend(lst) # 末尾に追加（リスト）

# プライオリティキュー
init_heap = lambda a:import_module('heapq').heapify(a)
heap_push = lambda a,v:import_module('heapq').heappush(a,v)
heap_pop = lambda a:import_module('heapq').heappop(a) # 最小値を取り出す

def solution():
    # ここに実装
    N,K = input_ints()
    h = input_ints_list()

    dp = init_array_1dim(0,N)
    for i in range(N):
        if i == 0:
            continue
        temp = []
        for j in range(K):
            if i-j-1 < 0:continue
            temp.append(dp[i-j-1]+abs(h[i]-h[i-j-1]))
        dp[i] = min(temp)
    print(dp[N-1])
    
if __name__ == '__main__':
    solution()

### FIXED CODE ###

n, k = map(int, input().split())
h = list(map(int, input().split()))

dp = [0]*n
dp[1] = abs(h[1]-h[0])
for i in range(2, n):
    temp = []
    for j in range(0, min(k, i)):
        temp.append(abs(h[i]-h[i-j-1])+dp[i-j-1])
    dp[i] = min(temp)
print(dp[n-1])
### BUGGY CODE ###

import numpy as np

N, Q = map(int,input().split())

L = [np.array([0] * N) for _ in range(N + 1)]

C = list(map(int,input().split()))

for i in range(N):
    L[i+1] += L[i]
    L[i+1][C[i] - 1] += 1

for _ in range(Q):
    l, r = map(int,input().split())
    tmp = L[r] - L[l-1]
    print(np.count_nonzero(tmp))

### FIXED CODE ###

import sys
 
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

class BIT():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n
        self.UNITY_SUM = 0
        self.dat = [[self.UNITY_SUM for i in range(n + 1)] for j in range(2)]
    
    def sub_ADD(self, p, a, x):
        i = a
        while i < len(self.dat[p]):
            self.dat[p][i] = self.dat[p][i] + x
            i += i & -i
    
    def ADD(self, a, b, x):
        self.sub_ADD(0, a, x * -(a - 1))
        self.sub_ADD(1, a, x)
        self.sub_ADD(0, b, x * (b - 1))
        self.sub_ADD(1, b, x * (-1))
    
    def sub_SUM(self, p, a):
        res = self.UNITY_SUM
        i = a
        while i > 0:
            res += self.dat[p][i]
            i -= i & -i
        return res
    
    def SUM(self, a, b):
        return self.sub_SUM(0, b - 1) + self.sub_SUM(1, b - 1) * (b - 1) - self.sub_SUM(0, a - 1) - self.sub_SUM(1, a - 1) * (a - 1)
    
    def PRINT(self):
        for i in range(1, len(self.dat[0])):
            print(self.SUM(i, i + 1), end = "")
            print(",", end = "")
        print()

def main():
    N, Q = map(int,readline().split())
    C = list(map(int,readline().split()))  #対象のリスト
    S = sys.stdin.readlines()
    lefts = [0] * Q
    rights = [0] * Q
    ids = [0] * Q
    for i in range(Q):
        lefts[i], rights[i] = map(int,S[i].split())
        lefts[i] -= 1
        ids[i] = i
    
    ids = sorted(ids, key=lambda x: rights[x])

    bit = BIT(N+5)
    prev = [-1] * 1100000
    res = [0] * Q
    r = 0
    for i in ids:
        while r < rights[i]:
            bit.ADD(prev[C[r]]+2, r+2, 1)
            prev[C[r]] = r
            r += 1
        tmp = bit.SUM(lefts[i]+1, lefts[i]+2)
        res[i] = max(res[i], tmp)
    for i in range(Q):
        print(res[i])

main()
### BUGGY CODE ###

n = int(input())
ans = float('inf')

for i in range(1, 10**7+1):
    q, m = divmod(n, i)
    if m == 0:
        ans = min(ans, q+i)

print(ans-2)


### FIXED CODE ###

n = int(input())


def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)
    divisors.sort()
    return divisors


r = make_divisors(n)

if len(r) % 2 == 1:
    a = r[len(r)//2]
    print((a-1)+(a-1))
else:
    a = int(len(r)/2)
    print((r[a-1]-1)+(r[a]-1))
### BUGGY CODE ###

from fractions import gcd
N = int(input())
A = list(map(int,input().split()))
lcm = A[0]
for i in range(1,N):
    lcm = (lcm*A[i])//gcd(lcm,A[i])

MOD = 10**9+7
ans = 0
for a in A:
    b = lcm//a
    ans += b
print(ans%MOD)

### FIXED CODE ###

from fractions import gcd
n=int(input())
a=list(map(int,input().split()))
lcm = a[0]
for i in range(1,n):
  lcm = lcm*a[i] // gcd(lcm,a[i])
mod=pow(10,9)+7
lcm%=mod
ans=0
for x in a:
  ans+=pow(x,mod-2,mod)
  ans%=mod
print(ans*lcm%mod)
### BUGGY CODE ###

s = input()
mod = 10 ** 9 + 7
dp = []
for _ in range(len(s) + 1):
    l = []
    for __ in range(13):
        l.append(0)
    dp.append(l)
# [[0 for _ in range(13)] for __ in range(len(s) + 1)]
dp[0][0] = 1
for i in range(len(s)):
    if s[-i-1] == '?':
        for n in range(10):
            a = n * (10 ** i) % 13
            for j in range(13):
                dp[i+1][(j + a) % 13] = (dp[i+1][(j + a) % 13] + dp[i][j]) % mod
    else:
        a = int(s[-i-1]) * (10 ** i) % 13
        for j in range(13):
            dp[i+1][(j + a) % 13] = (dp[i+1][(j + a) % 13] + dp[i][j]) % mod
print(dp[len(s)][5])


### FIXED CODE ###

s = input()
mod = 10 ** 9 + 7
memo = [0] * (len(s) + 1)
memo[0] = 1
dp = [[0 for _ in range(13)] for __ in range(len(s) + 1)]
dp[0][0] = 1
for i, si in enumerate(s[::-1]):
    memo[i+1] = memo[i] * 10 % 13
    if si == '?':
        for n in range(10):
            a = n * memo[i]
            for j in range(13):
                dp[i+1][(j + a) % 13] = (dp[i+1][(j + a) % 13] + dp[i][j]) % mod
    else:
        a = int(si) * memo[i]
        for j in range(13):
            dp[i+1][(j + a) % 13] = (dp[i+1][(j + a) % 13] + dp[i][j]) % mod
print(dp[len(s)][5])
### BUGGY CODE ###

import sys
import numpy as np
from numba import jit
readline = sys.stdin.buffer.readline
sys.setrecursionlimit(10 ** 8)
INF = float('inf')
MOD = 10 ** 9 + 7



def main():
    N = int(input())
    H = np.array(input().split(), np.int64)
    A = np.arange(1,N+1)
    B = np.arange(1,N+1)
    A = A + H
    B = B - H
    ans = 0

    @jit(nopython=True)
    def aa(i):
        return N - i - np.count_nonzero(B[i:] - A[:-i])
    for i in range(1,N):
        ans += aa(i)
    print(ans)



if __name__ == '__main__':
    main()

### FIXED CODE ###

import sys
from collections import defaultdict

read = sys.stdin.read
readline = sys.stdin.buffer.readline
sys.setrecursionlimit(10 ** 8)
INF = float('inf')
MOD = 10 ** 9 + 7


def main():
    N = int(readline())
    A = list(map(int, readline().split()))
    L = defaultdict(int)
    R = defaultdict(int)
    for i in range(N):
        L[i+1+A[i]] += 1
        R[i+1-A[i]] += 1
    ans = 0
    for key, value in L.items():
        ans += value*R[key]
    print(ans)


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

n = int(input())
z = [list(map(int, input().split())) for i in range(n)]
m = 0
d = 0
for i in range(n-1):
  for j in range(i+1, n):
    d = 0
    d += max(z[i][0] - z[j][0], z[j][0] - z[i][0])
    d += max(z[i][1] - z[j][1], z[j][1] - z[i][1])
    if d>m:
      m = d
print(m)
	


### FIXED CODE ###

n = int(input())
u = [list(map(int, input().split())) for i in range(n)]
z = [u[i][0] + u[i][1] for i in range(n)]
w = [u[i][0] - u[i][1] for i in range(n)]
d = [max(z)-min(z), max(w)-min(w)]

print(max(d))
### BUGGY CODE ###

n = int(input())

s = set()

for i in range(n):

    a = {int(input())}
    s = s ^ a

print(len(s))

### FIXED CODE ###

import sys
input = sys.stdin.readline

import bisect

def main():
    n = int(input())
    s = []

    for i in range(n):
        a = int(input())
        i = bisect.bisect_left(s, a)
        if len(s) > i and s[i] == a:
            s.remove(a)
        else:
            s.insert(i, a)


    print(len(s))


main()