Harryxun/stf_run huggingface dataset:
ascii_letters = 'abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ'

def llcs(x, y):
    pm = dict((zip(ascii_letters, [0] * 52)))
    for c in pm:
        for i, xc in enumerate(x):
            if c == xc:
                pm[c] |= (1 << i)
    
    V = (1 << len(x)) - 1
    
    for yc in y:
        V = ((V + (V & pm[yc])) | (V & ~pm[yc]))
    
    ans = bin(V)[-len(x):].count('0')
    
    return ans

from sys import stdin

def solve():
    #file_input = stdin
    file_input = open("ALDS1_10_C_in_4", 'r')
    q = int(file_input.readline())
    for i in range(q):
        s1 = file_input.readline().rstrip()
        s2 = file_input.readline().rstrip()
        print(llcs(s1, s2))

solve()


### FIXED CODE ###

def lcs_len(x, y):
    indices = [0]
    for y_i in y:
        t_index = 0
        for i, index in enumerate(indices, 1):
            c_index = x.find(y_i, t_index) + 1
            if c_index:
                if i < len(indices):
                    t_index = indices[i]
                    indices[i] = min(c_index, t_index)
                else:
                    indices.append(c_index)
                    break
    print(len(indices) - 1)


q = int(input())

for i in range(q):
    ax = input()
    ay = input()
    lcs_len(ax, ay)
s = input()
n = len(s)
p = 10 ** 9 + 7

# i = 0, ..., nについて
# dp[i][0] = i文字目まででありうる文字列の数（ABCなら1、AB?なら3）
# dp[i][1] = i文字目までに含まれるAの数
# dp[i][2] = i文字目までに含まれるABのパターン数
# dp[i][3] = i文字目までに含まれるABCのパターン数
dp = [[0 for j in range(4)] for i in range(n + 1)]
dp[0][0] = 1 # ''空の文字列は1パターン
for j in range(1, 4):
    dp[0][j] = 0  # 空の文字列にはAもABもABCも入っていない

for i in range(1, n + 1):
    m = 3 if s[i - 1] == '?' else 1

    for j in range(4):
        dp[i][j] = dp[i - 1][j] * m

    if s[i - 1] == 'A' or s[i - 1] == '?':
        dp[i][A] =  (dp[i][A] + dp[i - 1][0]) % p
    if s[i - 1] == 'B' or s[i - 1] == '?':
        dp[i][AB] = (dp[i][AB] + dp[i - 1][A]) % p
    if s[i - 1] == 'C' or s[i - 1] == '?':
        dp[i][ABC] = (dp[i][ABC] + dp[i - 1][AB]) % p

print(dp[n][ABC])

### FIXED CODE ###

s = input()
n = len(s)
p = 10 ** 9 + 7

q = s.count('?')
l_a = [0] * n  # l_a[i] := s[i]より左にあるAの数
l_x = [0] * n  # l_x[i] := s[i]より左にある?の数
r_c = [0] * n  # r_c[i] := s[i]より右にあるCの数
r_x = [0] * n  # r_x[i] := s[i]より右にある?の数

for i in range(1, n):  # 1〜n-1
    l_a[i] = l_a[i - 1] + int(s[i - 1] == 'A')
    l_x[i] = l_x[i - 1] + int(s[i - 1] == '?')
    r_c[n - i - 1] = r_c[n - i] + int(s[n - i] == 'C')
    r_x[n - i - 1] = r_x[n - i] + int(s[n - i] == '?')

ans = 0
pow_q = []
for i in range(0, 4):
    pow_q.append(max(1, 3 ** (q - i) % p))

for i in range(n):
    if s[i] == 'B':
        ans += (l_a[i] * r_c[i] % p) * pow_q[0] % p  # ABC
        ans += (l_x[i] * r_c[i] % p) * pow_q[1] % p # ?BC
        ans += (l_a[i] * r_x[i] % p) * pow_q[1] % p # AB?
        ans += (l_x[i] * r_x[i] % p) * pow_q[2] % p # ?B?
        ans %= p
    elif s[i] == '?':
        ans += (l_a[i] * r_c[i] % p) * pow_q[1] % p # A?C
        ans += (l_x[i] * r_c[i] % p) * pow_q[2] % p # ??C
        ans += (l_a[i] * r_x[i] % p) * pow_q[2] % p # A??
        ans += (l_x[i] * r_x[i] % p) * pow_q[3] % p # ???
        ans %= p

print(ans)
N, K = map(int,input().split())
cost = list(map(int, input().split()))

ans_list = [0]*N
ans_list[1] = abs(cost[0] - cost[1])
temp = 10 **10

for i in range(2,N):
    temp = 10**10
    for j in range(1,K+1):
        if i-j >=0:
            compare = ans_list[i-j] + abs(cost[i-j]-cost[i])
            temp = min(compare, temp)
        else:
            break
    ans_list[i] = temp
print(ans_list.pop())


### FIXED CODE ###

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

dp = [0] * N
dp[1] = dp[0] + abs(h[1]-h[0])

for i in range(2, N):
    compare1 = dp[i-1] + abs(h[i]-h[i-1])
    compare2 = dp[i-2] + abs(h[i]-h[i-2])
    dp[i] = min(compare1, compare2)

print(dp[-1])
import sys
input = sys.stdin.readline
import math
import operator
from functools import reduce
from itertools import accumulate

def read():
    N = int(input().strip())
    A = list(map(int, input().strip().split()))
    return N, A


def prime_factorization_preprocess(n):
    """
    エラトステネスの篩を用いて、sqrt(n)以下の素数を列挙する
    """
    m = math.floor(math.sqrt(n)) + 1
    primes = []
    is_prime = [True for i in range(m)]
    for i in range(2, m):
        if is_prime[i]:
            primes.append(i)
            for j in range(i+i, m, i):
                is_prime[j] = False
    return primes


def prime_factorization(x, primes):
    """
    試し割り法により、数値の素因数分解を求める
    """
    factors = defaultdict(int)
    for p in primes:
        if x % p == 0:
            n = 0
            while x % p == 0:
                x //= p
                n += 1
            factors[p] = n
    return factors


def solve(N, A, AMAX = 10**9, INF=10**9):
    sl = list(accumulate(A, math.gcd))
    sr = list(reversed(list(accumulate(reversed(A), math.gcd))))
    max_gcd = sl[-1]
    for i in range(N):
        # gcdの単位元は0
        v = 0
        if i > 0:
            v = math.gcd(v, sl[i-1])
        if i < N-1:
            v = math.gcd(v, sr[i+1])
        max_gcd = max(max_gcd, v)
    return max_gcd


if __name__ == '__main__':
    inputs = read()
    print(solve(*inputs))


### FIXED CODE ###

import sys
input = sys.stdin.readline
import math
from fractions import gcd
import operator
from functools import reduce
from itertools import accumulate

def read():
    N = int(input().strip())
    A = list(map(int, input().strip().split()))
    return N, A


def prime_factorization_preprocess(n):
    """
    エラトステネスの篩を用いて、sqrt(n)以下の素数を列挙する
    """
    m = math.floor(math.sqrt(n)) + 1
    primes = []
    is_prime = [True for i in range(m)]
    for i in range(2, m):
        if is_prime[i]:
            primes.append(i)
            for j in range(i+i, m, i):
                is_prime[j] = False
    return primes


def prime_factorization(x, primes):
    """
    試し割り法により、数値の素因数分解を求める
    """
    factors = defaultdict(int)
    for p in primes:
        if x % p == 0:
            n = 0
            while x % p == 0:
                x //= p
                n += 1
            factors[p] = n
    return factors


def solve(N, A, AMAX = 10**9, INF=10**9):
    sl = list(accumulate(A, gcd))
    sr = list(reversed(list(accumulate(reversed(A), gcd))))
    max_gcd = sl[-1]
    for i in range(N):
        # gcdの単位元は0
        v = 0
        if i > 0:
            v = gcd(v, sl[i-1])
        if i < N-1:
            v = gcd(v, sr[i+1])
        max_gcd = max(max_gcd, v)
    return max_gcd


if __name__ == '__main__':
    inputs = read()
    print(solve(*inputs))
from datetime import datetime,timedelta

a=[int(input()) for _ in range(5)]

t1=datetime(2000,1,1,a[0],a[1],0)
t2=datetime(2000,1,1,a[2],a[3],0)

delta=t2-t1
total_seconds=delta.seconds

ans=(total_seconds-a[4]*60)/60
print(int(ans))


### FIXED CODE ###

from datetime import datetime,timedelta

a=input().split()
a=[int(_) for _ in a]

t1=datetime(2000,1,1,a[0],a[1],0)
t2=datetime(2000,1,1,a[2],a[3],0)

delta=t2-t1
total_seconds=delta.seconds

ans=(total_seconds-a[4]*60)/60
print(int(ans))
n,m,l = map(int,input().split())
n_list=[] 
m_list = []
c=[[0 for i in range(n)] for j in range(l)]
for i in range(n):
    n_list.append([int(i) for i in input().split()])
for j in range(m):
    m_list.append([int(i) for i in input().split()])
for i in range(n):
    for j in range(l):
        for k in range(m):
            c[i][j]+=n_list[i][k]*m_list[k][j]

for i in range(n):
    print(' '.join(str(i) for i in c[i]))


### FIXED CODE ###

n,m,l = map(int,input().split())
n_list=[] 
m_list = []
c=[[0 for i in range(l)] for j in range(n)]
for i in range(n):
    n_list.append([int(i) for i in input().split()])
for j in range(m):
    m_list.append([int(i) for i in input().split()])
for i in range(n):
    for j in range(l):
        for k in range(m):
            c[i][j]+=n_list[i][k]*m_list[k][j]

for i in range(n):
    print(' '.join(str(i) for i in c[i]))
if __name__ == "__main__":
    print(main())


### FIXED CODE ###

class Solver():
    def __init__(self, N, W, items):
        self.N = N
        self.W = W
        self.items = items

    def solve(self):
        dp = [[0 for _ in range(self.W+1)] for _ in range(self.N+1)]
        for i in range(self.N):
            for w in range(self.W+1):
                if w - self.items[i][0] >= 0:
                    dp[i+1][w] = max(dp[i+1][w], dp[i][w - self.items[i][0]] + self.items[i][1])

                dp[i + 1][w] = max(dp[i + 1][w], dp[i][w])
        return dp[self.N][self.W]


def main():
    N, W = [int(i) for i in input().split()]
    items = [[int(i) for i in input().split()] for _ in range(N)]
    solver = Solver(N, W, items)
    print(solver.solve())


if __name__ == "__main__":
    main()
H, N = map(int, input().split())
damege = map(int, input().split())

damege.sort()

if H - (damege[-1] + damege[-2]) <= 0:
    print('Yes')
else:
    print('No')

### FIXED CODE ###

# アライグマはモンスターと戦っています。モンスターの体力はHです。
# アライグマはN種類の必殺技を使うことができ、i番目の必殺技を使うとモンスターの体力を Ai
# 減らすことができます。 必殺技を使う以外の方法でモンスターの体力を減らすことはできません。
# モンスターの体力を0以下にすればアライグマの勝ちです。
# アライグマが同じ必殺技を2度以上使うことなくモンスターに勝つことができるなら Yes を、
# できないなら No を出力してください。

H, N = map(int, input().split())
damege = map(int, input().split())

total_damege = sum(damege)

if H - total_damege <= 0:
    print('Yes')
else:
    print('No')
N = input()
d = []
for i in range(N):
    d.append(input())
print(len(list(set(d)))

### FIXED CODE ###

#coding : utf-8
 
n = int(input())
d = []
for i in range(n):
    d.append(int(input()))
print(len(list(set(d))))
import sys

S = list(map(int, sys.stdin.readline()))
len_S = len(S)
ans = 0
for i in range(2 ** (len_S - 1)):
  sum_ = S[len_S - 1]
  cursor = len_S - 1
  power = 0
  pattern = i
  while cursor > 0:
    cursor -= 1 
    if pattern % 2 == 1:
      power += 1
    else:
      power = 0
    sum_ += S[cursor] * (10 ** power)
    pattern = pattern // 2
  ans += sum_
print(ans)


### FIXED CODE ###

import sys

S = list(map(int, sys.stdin.readline().strip()))
len_S = len(S)
ans = 0
for i in range(2 ** (len_S - 1)):
  sum_ = S[len_S - 1]
  cursor = len_S - 1
  power = 0
  while cursor > 0:
    cursor -= 1 
    if i % 2 == 1:
      power += 1
    else:
      power = 0
    sum_ += S[cursor] * (10 ** power)
    i >>= 1
  ans += sum_
print(ans)
s = str(input())
k = str(input())
lis = []
for u in range(6):
	for i in range(len(s)):
		try:
			if s[i:i+u] == "":
				continue
			if s[i:i+u] not in lis:
				lis.append(s[i:i+u])
		except:
			continue
lis.sort()
print(lis[k-1])

### FIXED CODE ###

s = str(input())
k = int(input())
lis = []
for u in range(6):
	for i in range(len(s)):
		try:
			if s[i:i+u] == "":
				continue
			if s[i:i+u] not in lis:
				lis.append(s[i:i+u])
		except:
			continue
lis.sort()
print(lis[k-1])
# -*- coding: utf-8 -*-
l = [] 
r = []
count = 0

N, M = map(int, input().split())
l = [0] * N
r = [0] * N
for i in range(0,M):
    l[i], r[i] = map(int, input().split())



#idカードの生成
    
for i in range(1,N+1):
    if max(l) <= i and i <= min(r):
        count += 1

print(count)

### FIXED CODE ###

# -*- coding: utf-8 -*-
l = [] 
r = []
count = 0

N, M = map(int, input().split())
l = [0] * M
r = [0] * M
for i in range(0,M):
    l[i], r[i] = map(int, input().split())

#idカードの生成
    
ml = max(l)
mr = min(r)

for i in range(1,N+1):
    if  ml <= i and i <= mr:
        count += 1

print(count)
N = int( input())
A = list( map( int, input().split()))
ans = 10**15
for i in [1, -1]:
    ansi, sums = 0, 0
    for a in A:
        sums += A
        if sums*i <= 0:
            ansi += abs(sums-s)
            sums = s
        s *= -1
    ans = min( ans, ansi)
print(ans)

### FIXED CODE ###

N = int( input())
A = list( map( int, input().split()))
ans = 10**15
for i in [1, -1]:
    ansi, sums = 0, 0
    for a in A:
        sums += a
        if sums*i <= 0:
            ansi += abs(sums-i)
            sums = i
        i *= -1
    ans = min( ans, ansi)
print(ans)
# -*- coding: utf-8 -*-

def main():

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

    ans = 1

    for i in A:
        if A == 0:
            ans = 0
            break
        ans *= i
            if ans > 10 ** 18:
            ans = -1

    print(ans)


if __name__ == "__main__":
    main()

### FIXED CODE ###

# -*- coding: utf-8 -*-

def main():

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

    ans = 1

    if 0 not in A:
        for i in A:
            ans *= i
            if ans > 10 ** 18:
                ans = -1
                break

    else:
        ans = 0

    print(ans)


if __name__ == "__main__":
    main()
from math import pi
r = int(input())
print("{:.6f} {:.6f}".format(float(r*r*pi), float(2*r*pi)))

### FIXED CODE ###

from math import pi
r = float(input())
print("{0:.6f} {1:.6f}".format(float(r*r*pi), float(2*r*pi)))
n,k=map(int,input().split())
p=map(int,input().split())

p=list(p)
p.sort()

a=0

for i in range(3):
    a+=p[i]

print(a)

### FIXED CODE ###

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

p=list(p)
p.sort()

a=0

for i in range(k):
    a+=p[i]

print(a)
import sys
input = sys.stdin.readline
import numpy as np

def print_sub(A, Ones, m, c):
    A = np.array(A)
    A = A -Ones
    print(n-1 -len(np.nonzero(A)[0]))
    c +=1
    if c < m:
        return print_sub(A, Ones, m, c)
    else:
        pass

n= int(input())
A = [int(a) for a in input().split()]
Ones = np.array([1]*(n-1))
c = 0
print_sub(A, Ones, n-1, c)

print("0")


### FIXED CODE ###

import sys
input = sys.stdin.readline

n = int(input())
A = [int(a) for a in input().split()]

sub_list = [0] *n

for a in A:
  sub_list[a-1] +=1

for i in range(n):
  print(sub_list[i])
n=int,input()
k=int,input()
s=input()
S='s[0:k-1]' + 's[k-1].lower()' + 's[k:]'
print(S)


### FIXED CODE ###

n,k=map(int,input().split())
s=input()
S=s[0:k-1]+s[k-1].lower()+s[k:]
print(S)
K = input()
print('ACL'*K)

### FIXED CODE ###

K = int(input())
print('ACL'*K)
def main():
    N = int(input())
    A_list = [int(input()) for _ in range(N)]
    tmp_list = copy(A_list)
    tmp_list.sort()
    max_num = tmp_list[-1]
    second_max_num = tmp_list[-2]
    max_index = A_list.index(max_num)
    for i in range(N):
        if i is max_index:
            print(second_max_num)
            continue
        print(max_num)


if __name__ == '__main__':
    main()


### FIXED CODE ###

from copy import copy


def main():
    N = int(input())
    A_list = [int(input()) for _ in range(N)]
    tmp_list = copy(A_list)
    tmp_list.sort()
    max_num = tmp_list[-1]
    second_max_num = tmp_list[-2]
    max_index = A_list.index(max_num)
    for i in range(N):
        if i is max_index:
            print(second_max_num)
            continue
        print(max_num)


if __name__ == '__main__':
    main()
N=int(input())
X=int(input())
S=[]
T=[]
ans=0
f=False
for a in range(N):
  s,t=input().split()
  t=int(t)
  S.append(s)
  T.append(t)
for a in range(N):
  if(f):ans+=T[a]
  if(S[a]==X):f=True
print(ans)

### FIXED CODE ###

# coding: utf-8
import re
import math
import itertools
from copy import deepcopy
import fractions
import random
from heapq import heappop,heappush
import time
import os
import sys
import datetime
from functools import lru_cache
readline=sys.stdin.readline
sys.setrecursionlimit(2000)
#import numpy as np
alphabet="abcdefghijklmnopqrstuvwxyz"
mod=int(10**9+7)
inf=int(10**20)
def yn(b):
    if b:
        print("yes")
    else:
        print("no")
def Yn(b):
    if b:
        print("Yes")
    else:
        print("No")
def YN(b):
    if b:
        print("YES")
    else:
        print("NO")
class union_find():
    def __init__(self,n):
        self.n=n
        self.P=[a for a in range(N)]
        self.rank=[0]*n
 
    def find(self,x):
        if(x!=self.P[x]):self.P[x]=self.find(self.P[x])
        return self.P[x]
 
    def same(self,x,y):
        return self.find(x)==self.find(y)
 
    def link(self,x,y):
        if self.rank[x]<self.rank[y]:
            self.P[x]=y
        elif self.rank[y]<self.rank[x]:
            self.P[y]=x
        else:
            self.P[x]=y
            self.rank[y]+=1
 
    def unite(self,x,y):
        self.link(self.find(x),self.find(y))
 
    def size(self):
        S=set()
        for a in range(self.n):
            S.add(self.find(a))
        return len(S)
def bin_(num,size):
    A=[0]*size
    for a in range(size):
        if (num>>(size-a-1))&1==1:
            A[a]=1
        else:
            A[a]=0
    return A
def fac_list(n,mod_=0):
    A=[1]*(n+1)
    for a in range(2,len(A)):
        A[a]=A[a-1]*a
        if(mod>0):A[a]%=mod_
    return A
def comb(n,r,mod,fac):
    if(n-r<0):return 0
    return (fac[n]*pow(fac[n-r],mod-2,mod)*pow(fac[r],mod-2,mod))%mod
def next_comb(num,size):
    x=num&(-num)
    y=num+x
    z=num&(~y)
    z//=x
    z=z>>1
    num=(y|z)
    if(num>=(1<<size)):return False
    else:
        return num
def get_primes(n,type="int"):
    A=[True]*(n+1)
    A[0]=False
    A[1]=False
    for a in range(2,n+1):
        if A[a]:
            for b in range(a*2,n+1,a):
                A[b]=False
    if(type=="bool"):return A
    B=[]
    for a in range(n+1):
        if(A[a]):B.append(a)
    return B
def is_prime(num):
    if(num<=2):return False
    i=2
    while i*i<=num:
       if(num%i==0):return False
       i+=1
    return True
def join(A,c=" "):
    n=len(A)
    A=list(map(str,A))
    s=""
    for a in range(n):
        s+=A[a]
        if(a<n-1):s+=c
    return s
#######################################################################################################
N=int(input())

S=[]
T=[]
ans=0
f=False
for a in range(N):
  s,t=input().split()
  t=int(t)
  S.append(s)
  T.append(t)
X=input()
for a in range(N):
  if(f):ans+=T[a]
  if(S[a]==X):f=True
print(ans)
# 入力
N, K, Q = map(int, input().split())
A = list(map(int, input().split()))

INF = 10**20

# Y = A_1, .., A_N のときの X - Y の最小値を求める
# Y を決め打つと、 X - Y の最小値はO(NlogN)で求められる


def f(b):
    i = 0
    T = []
    while i < N:
        S = []
        while i < N and A[i] >= b:
            S.append(A[i])
            i += 1
        if len(S) >= K:
            T.extend(sorted(S)[:(len(S) - K + 1)])
        i += 1
    return (
        sorted(T)[Q - 1] if len(T) >= Q else
        INF
    )


ans = min(f(b) - b for b in B)

# 出力
print(ans)


### FIXED CODE ###

# 入力
N, K, Q = map(int, input().split())
A = list(map(int, input().split()))

INF = 10**20

# Y = A_1, .., A_N のときの X - Y の最小値を求める
# Y を決め打つと、 X - Y の最小値はO(NlogN)で求められる


def f(b):
    i = 0
    T = []
    while i < N:
        S = []
        while i < N and A[i] >= b:
            S.append(A[i])
            i += 1
        if len(S) >= K:
            T.extend(sorted(S)[:(len(S) - K + 1)])
        i += 1
    return (
        sorted(T)[Q - 1] if len(T) >= Q else
        INF
    )


ans = min(f(a) - a for a in sorted(A))

# 出力
print(ans)
while True:
  x, y = map(int, raw_input().split())
   if x>y:
    print('y x') 
    continue
   elif x<y:
    print('x y')
    continue
   else x and y == '0'
    break

### FIXED CODE ###

while True:
  x, y = map(int, raw_input().split())
  if x == 0 and y == 0:
    break
  elif x > y:
    print y, x 
  elif x < y or x == y:
    print x, y
k=int(input())
a=[int(i) for i in input().split()]
chk=2
if a[-1]!=2:
    print(-1)
    exit()
else:
    for i in range(n-1,0,-1):
        if a[i-1]>=a[i]*2:
            print(-1)
            exit()
    print(chk[2])

### FIXED CODE ###

k=int(input())
a=[int(i) for i in input().split()]
l=2
r=3
for i in range(k-1,-1,-1):
    l=(l+a[i]-1)//a[i]*a[i]
    r=(r+a[i]-1)//a[i]*a[i]
if l==r:
    print(-1)
else:
    print(l,r-1)
def solve():
    N, A, B = map(int, input().split())
    ans = []

    if A+B-1<=N<=A*B:
        for i in range(1, B+1)[::-1]:
            ans.append(i)
        for i in range(B+1, B+A):
            ans.append(i)
        s = A+B-1
        while 1:
            for i in range(s+1, s+B+1)[::-1]:
                ans.append(i)
                if i==N:
                    return ans
            s += B
            if s + B > N:
                s = N - B
    else:
        print(-1)

print(*solve())


### FIXED CODE ###

N, A, B = map(int, input().split())
ans = []
 
if A+B-1<=N<=A*B:
    S = N-A
    cur = N
    ans = []
    for i in range(A+1):
        num = min(B-1, S)+1
        S -= num-1
        for j in range(num):
            ans.append(cur-num+1+j)
        cur -= num
    ans = ans[::-1][1:]
    print(*ans)
else:
    print(-1)

from bisect import bisect


def LIS(L):
    INF, N = 10**12, len(L)
    seq = [INF] * N
    for i in L:
        seq[bisect(seq, i)] = i
    return N - seq.count(INF)
import sys
import math
lines = sys.stdin.readlines()

S = str(lines[0])
X = []

for i in range(len(S)):
  a = int(S[i:])
  c = a-(a//2019)*2019
  X.append(c)

X.sort()
flag =1
n = 0
for i in range(len(X)-1):
  if X[i]==0:
    n +=1
  if X[i]==X[i+1]:
    flag += 1
  else:
    n += int(flag*(flag-1)/2)
    flag = 1
 
print(n)


### FIXED CODE ###

S = str(input())

#10**nのmod計算
A = []
p =1
for i in range(len(S)):
  A.append(p)
  p = p*10%2019

#左からi文字以降の数字列のmod計算
X = []
a = 0
for i in range(len(S)):
  a = (a + int(S[len(S)-i-1])*A[i]) %2019
  X.append(a)
X.sort()
flag =1
n = 0

#modが同じになる組み合わせ、またはもともとmodが0になる数字列の個数の総和計算
for i in range(len(X)-1):
  if X[i]==0:
    n +=1
  if X[i]==X[i+1]:
    flag += 1
  else:
    n += int(flag*(flag-1)/2)
    flag = 1
n += int(flag*(flag-1)/2)
if X[len(X)-1]==0:
  n +=1
print(n)
def slove():
    import sys
    input = sys.stdin.readline
    n = int(input().rstrip('\n'))
    a = list(map(int, input().rstrip('\n').split()))
    b = []
    for i, v in enumerate(a):
        b.append(v - (i + 1))
    b.sort()
    t = b[len(b) // 2]
    s = 0
    for i, v in enumerate(a):
        s += abs(v - (t + (i + 1)))
    print(s)


if __name__ == '__main__':


### FIXED CODE ###

def slove():
    import sys
    input = sys.stdin.readline
    n = int(input().rstrip('\n'))
    a = list(map(int, input().rstrip('\n').split()))
    b = []
    for i, v in enumerate(a):
        b.append(v - (i + 1))
    b.sort()
    t = b[len(b) // 2]
    s = 0
    for i, v in enumerate(a):
        s += abs(v - (t + (i + 1)))
    print(s)


if __name__ == '__main__':
    slove()
x=int(input())
print x**3

### FIXED CODE ###

x=int(input())
print(x**3)
from copy import deepcopy
import itertools
from bisect import bisect_left
from bisect import bisect_right
import math
from collections import deque
from collections import Counter


def read():
    return int(input())


def readmap():
    return map(int, input().split())


def readlist():
    return list(map(int, input().split()))


if __name__ == "__main__":
    N = read()
    B = [math.inf]
    B.extend(readlist())
    B.append(math.inf)

    print(sum([min(B[i], B[i-1]) for i in range(1, N+1)]))



### FIXED CODE ###

from copy import deepcopy
import itertools
from bisect import bisect_left
from bisect import bisect_right
import math
from collections import deque
from collections import Counter


def read():
    return int(input())


def readmap():
    return map(int, input().split())


def readlist():
    return list(map(int, input().split()))


INT_MAX = 10 ** 10


if __name__ == "__main__":
    N = read()
    B = [INT_MAX]
    B.extend(readlist())
    B.append(INT_MAX)

    print(sum([min(B[i], B[i-1]) for i in range(1, N+1)]))
h,n = map(int,input().split())

dg = 10**5

ba = []
for _ in [0]*n:
    a,b = map(int,input().split())
    ba.append(b*dg+a)
ba.sort()

d = [0]*(h+1)

a,b = ba[0]%dg,ba[0]//dg
d[0] = 0
for i in range(1,h+1):
    if i%a == 0:
        d[i] = (i//a)*b
    else:
        d[i] = (i//a+1)*b


for i in range(1,n):
    a,b = ba[i]%dg,ba[i]//dg
    if d[a] >= b:
        for j in range(a,h+1):
            if d[j] > d[j-a]+b:
                d[j] = d[j-a]+b

print(d[-1])

### FIXED CODE ###

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

dg = 10**5

ba = []
for _ in [0]*n:
    a,b = map(int,input().split())
    if a >= h:
        a = h
    ba.append(b*dg+a)
ba.sort()

d = [10**9]*(h+1)

d[0] = 0

for i in range(1,h+1):
    for e in ba:
        a,b = e%dg,e//dg
        if i<=a:
            if d[i] > b:
                d[i] = b
        else:
            if d[i] > d[i-a]+b:
                d[i] = d[i-a]+b

print(d[-1])