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

def main():
    n, k = map(int, input().split())
    results = tuple(map(int, input().split()))

    products = 1
    for result in results[:k]:
        products *= result
    for i in range(n-k):
        new_products = products * results[i+k] / results[i]
        if products < products*results[i+k]/results[i]:
            print('Yes')
        else:
            print('No')
        products = new_products


if __name__ == '__main__':
    main()


### FIXED CODE ###

def main():
    n, k = map(int, input().split())
    results = tuple(map(int, input().split()))

    for i in range(n-k):
        print('Yes' if results[i] < results[i+k] else 'No')



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

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

from collections import Counter 

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

# 各数値ごとに数を集計
num_dict = Counter(num_list)

ans = 0
while True:
    # 種類数がK以下なら終了
    if len(num_dict) <= K:
        print(ans)
        exit()

    # 一番数が少ない要素の個数分、答えに追加
    ans += num_dict.most_common()[-1][1]
    # 一番数が少ない要素を削除
    del num_dict[num_dict.most_common()[-1][0]]

### FIXED CODE ###

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

from collections import Counter 

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

# 各数値ごとに数を集計
num_dict = Counter(num_list)
# 数の少ない順でソート
num_tpl = num_dict.most_common()[::-1]

ans = 0
for i in range(len(num_tpl)):
    # 種類数がK以下なら終了
    if len(num_tpl) - i <= K:
        print(ans)
        exit()
    # 数が少ない要素から、答えに追加していく
    ans += num_tpl[i][1]
### BUGGY CODE ###

"""
problem statment url: http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_10_C
"""

from __future__ import division
from sys import stdin, maxint

def lcs(s1, s2):
	dp = [[0 for _ in range(len(s2) + 1)] for _ in range(len(s1) + 1)]

	for i in range(1, len(s1) + 1):
		for j in range(1, len(s2) + 1):
			if s1[i - 1] == s2[j - 1]:
				dp[i][j] = dp[i - 1][j - 1] + 1
			else:
				dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])

	return dp[len(s1)][len(s2)]

if __name__ == '__main__':
	tc = int(stdin.readline())
	for _ in range(tc):
		sa = stdin.readline().strip()
		sb = stdin.readline().strip()
		print(lcs(sa, sb))

### FIXED CODE ###

"""
problem statment url: http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_10_C
"""


def lcs():
	s1 = raw_input()
	s2 = raw_input()
	la, lb = len(s1), len(s2)
	dp1 = [0 for _ in range(lb + 1)]

	for i in range(la):
		dp2 = dp1 + []
		for j in range(lb):
			if s1[i] == s2[j]:
				dp1[j + 1] = dp2[j] + 1
			elif dp1[j + 1] < dp1[j]:
				dp1[j + 1] = dp1[j]

	return dp1[-1]

if __name__ == '__main__':
	tc = int(raw_input())
	for _ in range(tc):
		print(lcs())
### BUGGY CODE ###

from bisect import bisect_left as bl, bisect_right as br, insort
import sys
import heapq
#from math import *
from collections import defaultdict as dd, deque
def data(): return sys.stdin.buffer.readline().strip().decode()
def mdata(): return map(float, data().split())
out=sys.stdout.write
#sys.setrecursionlimit(100000)
INF=int(1e9)
mod=int(1e9)+7


n=int(data())
P=list(mdata())
dp=[0]*(n//2+2)
dp[1]=1
for i in range(n):
    dp1=dp.copy()
    for j in range(1,len(dp)):
        k=dp[j-1]*(1-P[i])+dp[j]*(P[i])
        dp1[j]=k
    dp=dp1.copy()
print(sum(dp))




### FIXED CODE ###

from bisect import bisect_left as bl, bisect_right as br, insort
import sys
import heapq
#from math import *
from collections import defaultdict as dd, deque
def data(): return sys.stdin.buffer.readline().strip().decode()
def mdata(): return map(float, data().split())
out=sys.stdout.write
#sys.setrecursionlimit(100000)
INF=int(1e9)
mod=int(1e9)+7


n=int(data())
P=list(mdata())
dp=[0]*(n//2+2)
dp[1]=1
for i in range(n):
    dp1=dp[:]
    for j in range(1,len(dp)):
        k=dp[j-1]*(1-P[i])+dp[j]*(P[i])
        dp1[j]=k
    dp=dp1[:]
print(sum(dp))
### BUGGY CODE ###

import sys
from collections import defaultdict, Counter
from itertools import product, groupby, count, permutations, combinations
from math import pi, sqrt, ceil, floor
from collections import deque
from bisect import bisect, bisect_left, bisect_right
from string import ascii_lowercase
from functools import lru_cache, reduce

INF = float("inf")
sys.setrecursionlimit(10 ** 7)

# 4近傍（右, 下, 左, 上）
dy = [0, -1, 0, 1]
dx = [1, 0, -1, 0]


def inside(y: int, x: int, H: int, W: int) -> bool: return 0 <= y < H and 0 <= x < W


def main():
    N, Ma, Mb = map(int, input().split())
    dp = [[[INF] * 401 for j in range(401)] for i in range(N + 1)]
    dp[0][0][0] = 0
    a_b_c = [map(int, input().split()) for _ in range(N)]

    for i, (a, b, c) in enumerate(a_b_c):
        for j in range(len(dp[0])):
            for k in range(len(dp[0][0])):
                # not use
                dp[i + 1][j][k] = min(dp[i + 1][j][k], dp[i][j][k])

                # use
                if j + a < len(dp[0]) and k + b < len(dp[0][0]):
                    dp[i + 1][j + a][k + b] = min(dp[i + 1][j + a][k + b], dp[i][j][k] + c)

    ans = INF
    for i in count(1):
        a, b = Ma * i, Mb * i
        if a >= len(dp[0]) or b >= len(dp[0][0]):
            break
        ans = min(ans, dp[-1][a][b])
    if ans != INF:
        print(ans)
    else:
        print(-1)

if __name__ == '__main__':
    main()


### FIXED CODE ###

from collections import defaultdict
from fractions import Fraction

INF = int(1e14)


def main():
    N, Ma, Mb = map(int, input().split())
    l = []
    for _ in range(N):
        l.append(tuple(map(int, input().split())))

    ans = INF
    dp = [[[INF] * 401 for i in range(401)] for j in range(N + 1)]
    dp[0][0][0] = 0

    max_a, max_b = 1, 1
    for i in range(N):

        for a in range(max_a, -1, -1):
            for b in range(max_b, -1, -1):
                if dp[i][a][b] != INF:
                    dp[i + 1][a + l[i][0]][b + l[i][1]] = min(dp[i + 1][a + l[i][0]][b + l[i][1]], dp[i][a][b] + l[i][2])
                    dp[i + 1][a][b] = min(dp[i + 1][a][b], dp[i][a][b])

                    max_a = max(max_a, a + l[i][0])
                    max_b = max(max_b, b + l[i][1])

    for a in range(1, len(dp[0])):
        for b in range(1, len(dp[1])):
            if a * Mb == b * Ma:
                ans = min(ans, dp[N][a][b])

    print((-1 if ans == INF else ans))

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

s=input()
l=len(s)
a=10**9+7

if s[l-1]=='?':
  n=[1,1,1,1,1,1,1,1,1,1,0,0,0]
else:
  n=[0,0,0,0,0,0,0,0,0,0,0,0,0]
  n[int(s[l-1])]=1
d=[0,0,0,0,0,0,0,0,0,0,0,0,0]

m=1
for i in range(1,len(s)):
  m=(m*10)%13
  if s[l-1-i] == '?':
    for j in range(13):
      for k in range(10):
        d[(m*k+j)%13] += n[j]
  else:
    for j in range(13):
      d[(m*int(s[l-1-i])+j)%13] += n[j]

  for j in range(13):
    n[j]=d[j]%a
    d[j]=0

print(n[5])


### FIXED CODE ###

S=input()
a=[0]*13
a[0]= 1

for c in S:
  dp=[0]*13
  for i in range(13):
    dp[(i*10)%13]=a[i]%(10**9+7)
  dp+=dp

  if c=='?':
    for i in range(13):
      a[i]=sum(dp[i+4:i+14])
  else:
    for i in range(13):
      a[i]=dp[i+13-int(c)]

print(a[5]%(10**9+7))
### BUGGY CODE ###

import math

fuga = int(input())
arr = list(map(int, input().split()))

hoge =1
for num in arr:
    hoge = hoge*num

if hoge <= 10**18:
    print(hoge)
else:
    print(-1)


### FIXED CODE ###

import math

kosuu = int(input())
arr = list(map(int, input().split()))

hoge =1

if 0 in arr:
    print(0)

else:
    for num in arr:
        hoge = hoge*num
        if hoge>1000000000000000000:
            print(-1)
            kosuu=0
            break
    if kosuu>0:
        print(hoge)
### BUGGY CODE ###

import sys,time
sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**15
mod = 10**9+7

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)


def main():
    start = time.time()
    n,m = LI()
    a = [LI() for _ in range(m)]
    e = [[] for _ in range(n)]
    for l,r,d in a:
        e[l-1].append((r-1,d))
        e[r-1].append((l-1,-d))

    b = [False] * n
    def g(i,c):
        gt = time.time() - start
        if gt > 1.7:
            return True
        if c == False:
            c = 0
        b[i] = c
        for r,d in e[i]:
            if b[r] != False:
                if b[r] != c+d:
                    return False
            else:
                if not g(r,c+d):
                    return False
        return True

    for i in range(n):
        if b[i] != False:
            continue
        if not g(i,False):
            return 'No'
    return 'Yes'


print(main())





### FIXED CODE ###

import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**15
mod = 10**9+7

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)


def main():
    n,m = LI()
    e = [[] for _ in range(n)]
    if m > 0:
        for _ in range(m):
            l,r,d = LI()
            e[l-1].append((r-1,d))
            e[r-1].append((l-1,-d))

    b = [None] * n

    for i in range(n):
        if not b[i] is None:
            continue
        b[i] = 0
        q = [i]
        qi = 0
        nq = []
        while True:
            if len(q) == qi:
                if not nq:
                    break
                q = nq
                qi = 0
                nq = []
            j = q[qi]
            qi += 1
            c = b[j]
            for r,d in e[j]:
                if b[r] is None:
                    b[r] = c+d
                    nq.append(r)
                else:
                    if b[r] != c+d:
                        return 'No'

    return 'Yes'


print(main())
### BUGGY CODE ###

from collections import Counter
import sys
sys.setrecursionlimit(10**6)

MOD = 998244353

ABC = "abc".index
*S, = map(ABC, input())
N = len(S)

def bruteforce(S):
    used = set()
    def dfs(s):
        key = tuple(s)
        if key in used:
            return
        used.add(key)
        for i in range(len(s)-1):
            if s[i] != s[i+1]:
                a = s[i]; b = s[i+1]
                s[i] = s[i+1] = 3 - a - b
                dfs(s)
                s[i] = a; s[i+1] = b
    dfs(S)
    return len(used)

if len(S) <= 3:
    print(bruteforce(S))
else:
    c = Counter(S)
    if c[0] == N or c[1] == N or c[2] == N:
        print(1)
    else:
        r3 = range(3); r2 = range(2)
        P = [[[0,0] for i in r3] for j in r3]
        Q = [[[0,0] for i in r3] for j in r3]
        P[0][0][0] = P[1][1][0] = P[2][2][0] = 1
        for i in range(N-1):
            for p in r3:
                for q in r3:
                    for r in r2:
                        Q[p][q][r] = 0
            for p in r3:
                for q in r3:
                    for r in r2:
                        for k in r3:
                            Q[k][(q+k)%3][r | (p == k)] += P[p][q][r] % MOD
            P, Q = Q, P
        ans = 0
        r = sum(S) % 3
        for i in r3:
            ans += P[i][r][1]
        if all(S[i] != S[i+1] for i in range(N-1)):
            ans += 1
        print(ans % MOD)

### FIXED CODE ###

from collections import Counter
import sys
sys.setrecursionlimit(10**6)

MOD = 998244353

ABC = "abc".index
*S, = map(ABC, input())
N = len(S)

def bruteforce(S):
    used = set()
    def dfs(s):
        key = tuple(s)
        if key in used:
            return
        used.add(key)
        for i in range(len(s)-1):
            if s[i] != s[i+1]:
                a = s[i]; b = s[i+1]
                s[i] = s[i+1] = 3 - a - b
                dfs(s)
                s[i] = a; s[i+1] = b
    dfs(S)
    return len(used)

if len(S) <= 3:
    print(bruteforce(S))
else:
    c = Counter(S)
    if c[0] == N or c[1] == N or c[2] == N:
        print(1)
    else:
        P = [[[0,0] for i in range(3)] for j in range(3)]
        Q = [[[0,0] for i in range(3)] for j in range(3)]
        P[0][0][0] = P[1][1][0] = P[2][2][0] = 1
        for i in range(N-1):
            for p in range(3):
                for q in range(3):
                    for r in range(2):
                        Q[p][q][r] = 0
            for p in range(3):
                for q in range(3):
                    for r in range(2):
                        for k in range(3):
                            Q[k][(q+k)%3][r | (p == k)] += P[p][q][r] % MOD
            P, Q = Q, P
        ans = 0
        r = sum(S) % 3
        for i in range(3):
            ans += P[i][r][1]
        if all(S[i] != S[i+1] for i in range(N-1)):
            ans += 1
        print(ans % MOD)
### BUGGY CODE ###

def gcd(a,b):
    for xx in range(1000001):
        a,b=b,a%b
        if b==0:
            break
    return a

def lcm_base(x, y):
    return (x * y) // gcd(x, y)

P = 10**9 + 7
N = 1000001
inv_t = [0]+[1]
for i in range(2,N):
    inv_t += [inv_t[P % i] * (P - int(P / i)) % P]

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

#kyodai=lcm_list(A)
kyodai=A[0]
for i in range(1,n):
    kyodai=lcm_base(kyodai,A[i])

ans=0

for i in range(n):
    ans+=kyodai*inv_t[A[i]]
    ans=ans%P

print(ans)


### FIXED CODE ###

def gcd(a,b):
    for xx in range(1000001):
        a,b=b,a%b
        if b==0:
            break
    return a

def lcm_base(x, y):
    return (x * y) // gcd(x, y)

P = 10**9 + 7
N = 1000001
inv_t = [0]+[1]
for i in range(2,N):
    inv_t += [inv_t[P % i] * (P - int(P / i)) % P]

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

#kyodai=lcm_list(A)
kyodai=A[0]
for i in range(1,n):
    kyodai=lcm_base(kyodai,A[i])

ans=0

for i in range(n):
    ans+=inv_t[A[i]]
    ans=ans%P
ans=ans*kyodai
ans=ans%P

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

import sys
from collections import defaultdict
from queue import deque
readline = sys.stdin.buffer.readline
#sys.setrecursionlimit(10**8)


def geta(fn=lambda s: s.decode()):
    return map(fn, readline().split())


def gete(fn=lambda s: s.decode()):
    return fn(readline().rstrip())


import numpy as np


def main():

    n = gete(int)
    l = list(geta(int))
    l.sort()

    l_max = 2000
    # p[k]: number of sticks with length >= k
    p = np.zeros((l_max + 1), dtype=np.int64)

    for li in l:
        p[:li + 1] += 1

    ans = 0
    for i, a in enumerate(l):
        for b in l[i + 1:]:
            ans += p[abs(a - b) + 1] - p[a + b]

            if abs(a - b) < a:
                ans -= 1

            if abs(a - b) < b:
                ans -= 1
    print(ans // 3)


if __name__ == "__main__":
    main()

### FIXED CODE ###

import sys
from collections import defaultdict
from queue import deque
readline = sys.stdin.buffer.readline
#sys.setrecursionlimit(10**8)


def geta(fn=lambda s: s.decode()):
    return map(fn, readline().split())


def gete(fn=lambda s: s.decode()):
    return fn(readline().rstrip())


def main():

    n = gete(int)
    l = list(geta(int))
    l.sort()

    l_max = 2000
    # p[k]: number of sticks with length >= k
    p = [0] * (l_max + 1)

    cur = 0
    acc = n
    for i in range(l_max + 1):
        p[i] = acc

        if cur < n and i == l[cur]:
            while cur < n and l[cur] == i:
                acc -= 1
                cur += 1

    ans = 0
    for i, a in enumerate(l):
        for b in l[i + 1:]:
            ans += p[abs(a - b) + 1] - p[a + b]

            if abs(a - b) < a:
                ans -= 1

            if abs(a - b) < b:
                ans -= 1
    print(ans // 3)


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

S0 = input()
S = S0[::-1]
cands = ["dream"[::-1],"dreamer"[::-1],"erase"[::-1],"eraser"[::-1]]
i = 0
while i < len(S):
  for word in cands:
    #print(S[i:],word)
    if S[i:].startswith(word):
    	i += len(word)
    	continue
#print(i)
if i == len(S):
  print("YES")
else:
  print("NO")


### FIXED CODE ###

S0 = input()
S = S0[::-1]
cands = ["dream"[::-1],"dreamer"[::-1],"erase"[::-1],"eraser"[::-1]]
i = 0
while i < len(S):
  f = False
  for word in cands:
    #print(S[i:],word)
    if S[i:].startswith(word):
        f = True
        i += len(word)
        break
  if f == False:
    print("NO")
    exit(0)
#print(i)
if i == len(S):
  print("YES")
else:
  print("NO")
### BUGGY CODE ###

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

for i in range(N):
    print(A.count(i+1))

### FIXED CODE ###

N = int(input())
boss = {i+1: 0 for i in range(N)}
A = map(int, input().split())

for i in A:
    boss[i] += 1

for i in range(N):
    print(boss[i+1])
### BUGGY CODE ###

from heapq import heapify, heappush, heappop
N,M = map(int,input().split())
AB = []
for i in range(N):
    a,b = map(int,input().split())
    AB.append((-b,a))
heapify(AB)
ans = 0
for i in range(1,M+1):
    rem = []
    while True:
        if AB:
            ab = heappop(AB)
            if ab[1] <= i:
                ans -= ab[0]
                for j in rem:
                    heappush(AB,j)
                break
            else:
                rem.append(ab)
        else:
            for j in rem:
                heappush(AB,j)
            break
print(ans)

### FIXED CODE ###

import heapq
from collections import defaultdict
N,M = map(int,input().split())
AB = defaultdict(list)
for i in range(N):
    a,b = list(map(int,input().split()))
    if a not in AB:
        AB[a] = [-b]
    else:
        AB[a] += [-b]
work = 0
AB2 = []
heapq.heapify(AB2)
for i in range(1,M+1):
    for j in AB[i]:
        heapq.heappush(AB2,j)
    if not AB2:
        continue
    b = heapq.heappop(AB2)
    work += -b
print(work)
### BUGGY CODE ###

import sys
input=sys.stdin.readline
Xs,Ys,Xg,Yg=map(int,input().split())

N=int(input())

L=[(Xs,Ys,0)]
for i in range(N):
    x,y,r=map(int,input().split())
    L.append((x,y,r))
L.append((Xg,Yg,0))

C=[-1 for i in range(len(L))]
C[0]=0

X=Xs
Y=Ys
R=0
Q=[]
import heapq
heapq.heapify(Q)
Z=[]
for i in range(1,len(L)):
    if C[i]==-1:
        heapq.heappush(Q,(max(0,((X-L[i][0])**2+(Y-L[i][1])**2)**0.5-(R+L[i][2])),i,0))
        #Z.append([max(0,((X-L[i][0])**2+(Y-L[i][1])**2)**0.5-(R+L[i][2])),i,0])
#print(Z)
        
for j in range(10**7):
    if len(Q)==0:
        break
    else:
        if C[Q[0][1]]!=-1:
            qq=heapq.heappop(Q)
            
        else:
            q=heapq.heappop(Q)
            C[q[1]]=q[0]
            X=L[q[1]][0]
            Y=L[q[1]][1]
            R=L[q[1]][2]
            for i in range(1,len(L)):
                if C[i]==-1:
                    heapq.heappush(Q,(max(0,((X-L[i][0])**2+(Y-L[i][1])**2)**0.5-(R+L[i][2]))+C[q[1]],i,q[1]))
                    #Z.append([max(0,((X-L[i][0])**2+(Y-L[i][1])**2)**0.5-(R+L[i][2])),i,q[1]])
    if C[-1]!=-1:
        break
    #print(C)
    #print(Z)
print(C[-1])
#print(C)

### FIXED CODE ###

import sys
input=sys.stdin.readline

Xs,Ys,Xg,Yg=map(int,input().split())
N=int(input())
L=[]
L.append([Xs,Ys,0])
for i in range(N):
    x,y,r=map(int,input().split())
    L.append([x,y,r])
L.append([Xg,Yg,0])
cost=[[-1 for i in range(N+2)]for j in range(N+2)]
for i in range(N+2):
    for j in range(i,N+2):
        cost[i][j]=max(0,((L[i][0]-L[j][0])**2+(L[i][1]-L[j][1])**2)**0.5-L[i][2]-L[j][2])
        cost[j][i]=cost[i][j]
#print(cost)


def jdijkstra(s,n,w,cost):
    #始点sから各頂点への最短距離
    #n:頂点数,　w:辺の数, cost[u][v] : 辺uvのコスト(存在しないときはinf)
    d = [float("inf")] * n
    used = [False] * n
    d[s] = 0
    
    while True:
        v = -1
        #まだ使われてない頂点の中から最小の距離のものを探す
        for i in range(n):
            if (not used[i]) and (v == -1):
               v = i
            elif (not used[i]) and d[i] < d[v]:
                v = i
        if v == -1:
               break
        used[v] = True
               
        for j in range(n):
               d[j] = min(d[j],d[v]+cost[v][j])
    return d

#print(jdijkstra(0,N+2,(N+2)**2,cost))
ans=jdijkstra(0,N+2,(N+2)**2,cost)
print(ans[-1])
### BUGGY CODE ###

N = int(input())
A =  []
l1 = input().split()
for i in l1:
    A.append(int(i))
B = []
l2 = input().split()
for i in l2:
    B.append(int(i))
if sum(A) < sum(B):
    print(-1)
else:
    z = 0
    ar1 = []
    ar2 = []
    for i in range(N):
        if A[i] < B[i] :
            ar1.append(B[i] - A[i])
        if A[i] > B[i]:
            ar2.append(A[i] - B[i])
    if len(ar1) == 0:
        print(0)
    else:
        ar2.sort(reverse = True)
        temp = 0
        b = 0
        for  i in range(len(ar2)):
            temp += ar2[i]
            if temp >= sum(ar1):
                b = i+1
                break
        print(len(ar1)+b)


### FIXED CODE ###

N = int(input())
A =  []
l1 = input().split()
for i in l1:
    A.append(int(i))
B = []
l2 = input().split()
for i in l2:
    B.append(int(i))
if sum(A) < sum(B):
    print(-1)
else:
    z = 0
    ar1 = []
    ar2 = []
    for i in range(N):
        if A[i] < B[i] :
            ar1.append(B[i] - A[i])
        if A[i] > B[i]:
            ar2.append(A[i] - B[i])
    if len(ar1) == 0:
        print(0)
    else:
        s = sum(ar1)
        ar2.sort(reverse = True)
        temp = 0
        b = 0
        for  i in range(len(ar2)):
            temp += ar2[i]
            if temp >= s:
                b = i+1
                break
        print(len(ar1)+b)
### BUGGY CODE ###

S = input()
cnt = 0
for ri in reversed(range(len(S))):
    for li in reversed(range(ri + 1)):
        s = S[li : ri + 1]
        #print("li = {}, ri = {}, s = {}".format(li, ri, s))
        if int(s) % 2019 == 0:
            #print("count ++ ")
            cnt += 1
print(cnt)


### FIXED CODE ###

# 後で１の位から処理するためにひっくり返しておく
S = list(map(int, reversed(input())))
#print("S = ", S)
"""
「2019の倍数か」は「mod 2019 が 0 になるか」と同意。
しかし、普通に切り出して、１つずつチェックすると計算工数がかかるので、累積和を使う。
各桁の値を （桁の数値a_k）× 10^k と表現し、mod 2019 の値を予め計算し、累積和を作っておく。
ここで、10^k の部分は、2019と互いに疎（公約数がない）なので、
含めて計算しても mod 2019 の周期を乱さない。（勿論オフセットは変わる）
「(i, j) が2019で割り切るか」は、「i～j の累積和が同じ値になる（2019周期）か」と同意。
累積和が同じ値になる個数を数えて、組み合わせを計算すればよい。
"""
# a　：　各桁の mod 2019 値（桁の数値 a_k × 10^k mod 2019）
a = [0] * len(S)
# sums ：　累積和
sums = [0] * (len(S) + 1)
# d : 10^k
d = 1
# cnt : 累積和 mod 2019 の出現度数表
cnt = [0] * 2019
cnt[0] = 1  # sums[0] = 0 の分
for i in range(len(S)):
    a[i] = (S[i] * d) % 2019
    sums[i + 1] = (sums[i] + a[i]) % 2019
    d = (d * 10) % 2019 
    cnt[sums[i + 1]] += 1
#print("sums = ", sums)
#print("cnt = ", cnt)
ans = 0
for i in cnt:
    ans += i * (i - 1) // 2
print(ans)
### BUGGY CODE ###

n = int(input())
A = tuple(map(int, input().split()))
Q = int(input())
Bs = [tuple(tuple(map(int, input().split()))) for i in range(Q)]
X = [0]
for i in range(1, 100001):
  X.append(A.count(i))
S = sum(A)
for B in Bs:
  S += X[B[0]]*(B[1]-B[0])
  X[B[1]] += X[B[0]]
  X[B[0]] = 0
  print(S)

### FIXED CODE ###

n = int(input())
A = list(map(int, input().split()))
S = sum(A)
D = {c:0 for c in range(1, 10**5+1)}
for a in A:
  D[a] += 1
for _ in range(int(input())):
  B, C = map(int, input().split())
  S += (C-B)*D[B]
  D[C] += D[B]
  D[B] = 0
  print(S)
### BUGGY CODE ###

n, w = map(int, input().split())
dp = [-1 for _ in range(w + 1)]
dp[0] = 0
ans = 0
for w, v in (map(int, input().split()) for _ in range(n)):
    for i in range(len(dp) - 1, w - 1, -1):
        if dp[i - w] >= 0:
            dp[i] = max(dp[i - w] + v, v, dp[i])
            ans = max(ans, dp[i])
print(ans)

### FIXED CODE ###

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

IN = list(list(map(int, input().split())) for _ in range(N))
sumw = 0
sumv = 0
for w, v in IN:
    sumw += w
    sumv += v

DP = dict()
DP[sumv] = sumw

def minv(i, v):
    if not DP.get(i):
        DP[i] = v
    else:
        if v < DP[i]:
            DP[i] = v

for w, v in IN:
    DPpre = DP.copy()
    for i in DPpre:
        minv(i-v, DPpre[i]-w)

for v in sorted(DP, reverse=True):
    if DP[v] <= W:
        print(v)
        break