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

from sys import stdin


def main():
  n, k = map(int, input().split())
  a = [int(x) for x in stdin.readline().split()]
  l = []
  l_append = l.append
  for i in range(0, n):
    for j in range(i+1, n):
      l_append(a[i]*a[j])
  l.sort()
  print(l[k-1])

if __name__ == '__main__':
  main()

### FIXED CODE ###

from scipy.sparse.csgraph import shortest_path, floyd_warshall, dijkstra, bellman_ford, johnson, minimum_spanning_tree
from scipy.sparse import csr_matrix, coo_matrix, lil_matrix
import numpy as np
from functools import reduce
from collections import deque, Counter, defaultdict
from itertools import product, permutations,combinations
from operator import itemgetter
from heapq import heappop, heappush
from bisect import bisect_left, bisect_right, bisect
from fractions import gcd
from math import ceil,floor, sqrt, cos, sin, pi, factorial
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10**8)
INF = float('inf')
MOD = 10**9+7
def lcm(a, b):
  return a*b//gcd(a, b)


def main():
  n, k = map(int, input().split())
  A = np.array(input().split(), np.int64)
  
  A = np.sort(A)
  
  zero = A[A == 0]
  pos = A[A>0]
  neg = A[A<0]
  
  def F(x):
    cnt_tpl = 0
    #zero multipy ...
    if x>= 0:
      cnt_tpl += len(zero)*n
    #positive multipy ...
    cnt_tpl += np.searchsorted(A, x//pos, side='right').sum()
    cnt_tpl += (n - np.searchsorted(A, (-x-1)//(-neg), side='right')).sum()
    cnt_tpl -= np.count_nonzero(A*A<=x)
    assert cnt_tpl %2 ==0
    return cnt_tpl//2
  
  left = -10**18
  right = 10**18
  while left + 1 < right:
    mid = (left+right)//2
    if F(mid) >= k:
      right = mid
    else:
      left = mid
  print(right)
  
if __name__ == '__main__':
  main()
### BUGGY CODE ###

n = int(input())
s = input()
ans = s.count("R")*s.count("G")*s.count("B")

for j in range(2, n):
    for i in range(1, j):
        k = 2*j - i
        if k<n+1 and s[i-1]!=s[j-1] and s[i-1]!=s[k-1] and s[j-1]!=s[k-1]:
            ans -= 1
print(ans)

### FIXED CODE ###

n = int(input())
s = input()
ans = s.count("R")*s.count("G")*s.count("B")

for j in range(1, n-1):
    for i in range(j):
        k = 2*j - i
        if k<n and s[i]!=s[j] and s[i]!=s[k] and s[j]!=s[k]:
            ans -= 1
print(ans)
### BUGGY CODE ###

N = int(input())
pt = pa = 0
for _ in range(N):
    t,a = map(int,input().split())
    if pt == 0:pt,pa = t,a
    else:
        if (pt <= t) and (pa <= a):pt,pa = t,a
        else:
            i = 2
            while True:
                if (pt <= t*i) and (pa <= a*i):
                    pt,pa = t*i,a*i
                    break
                i += 1
print(pt+pa)

### FIXED CODE ###

N = int(input())
pt = pa = 0
for _ in range(N):
    t,a = map(int,input().split())
    if pt == 0:
        pt,pa = t,a
    else:
        #print(pt,pa,t,a)
        if (pt <= t) and (pa <= a):
            pt,pa = t,a
        else:
            '''
            i = 2
            while True:
                if (pt <= t*i) and (pa <= a*i):
                    pt,pa = t*i,a*i
                    break
                i += 1
            '''
            if t == a:
                #that is t = a = 1
                maxta = max(pt,pa)
                pt = pa = maxta
            else:
                w1 = -1 * ((-1 *pt) // t)
                w2 = -1 * ((-1 *pa) // a)
                w = max(w1,w2)
                pt = w * t
                pa = w * a
                #print(pt,pa)
print(pt+pa)
### BUGGY CODE ###

import sys
read = sys.stdin.read
readlines = sys.stdin.readlines
def main():
    n = int(input())
    s = input()

    rr = [i for i, c in enumerate(s) if c == 'R']
    g = [i for i, c in enumerate(s) if c == 'G']
    b = [i for i, c in enumerate(s) if c == 'B']

    r = len(rr) * len(g) * len(b)
    for rre in rr:
        for ge in g:
            for be in b:
                r -= rre * 2 == ge + be
                r -= ge * 2 == rre + be
                r -= be * 2 == ge + rre
    print(r)

if __name__ == '__main__':
    main()


### FIXED CODE ###

def main():
    n = int(input())
    s = list(input())
    sr = [0] * n
    sg = [0] * n
    sb = [0] * n
    for i1 in range(n):
        ts = s[i1]
        if ts == 'R':
            sr[i1] = 1
        elif ts == 'G':
            sg[i1] = 1
        else:
            sb[i1] = 1
    if n <= 3:
        print(0)
        exit()
    r = 0
    for ia in range(0,n-3):
        ta = s[ia]
        if ta == 'R':
            r += sum(sg[ia+1:]) * sum(sb[ia+1:])
        elif ta == 'G':
            r += sum(sr[ia+1:]) * sum(sb[ia+1:])
        else:
            r += sum(sg[ia + 1:]) * sum(sr[ia + 1:])
        for ib in range((n - ia)//2+1):
            if ia + ib * 2 < n:
                if ta != s[ia + ib] and ta != s[ia + ib + ib] and s[ia+ib]!= s[ia + ib + ib]:
                    r -= 1
    print(r)

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

'''
V, E : Vは頂点数、Eは辺数
nodes : e = [from, to, cost] を要素とする辺のリスト（有向辺）
☆負のループがあっても、それがゴールと非連結な場所にあった場合関係ない。
つまり「0→負のループ→N-1」という経路が存在するときのみ問題になる。
0→負のループ、という経路があるかどうかは0からの距離がfloat('inf')でないことで調べられる
負のループのある点→N-1という経路があるかどうかは、更新の際にnegative[i]から辺が伸びている頂点も更新することで調べられる。
'''
V, E = map(int, input().split())
nodes = []
for _ in range(E):
    e_from, e_to, e_cost = map(int, input().split())
    e_from -= 1
    e_to -= 1 #頂点を0-indexedに
    e_cost *= -1
    nodes.append([e_from, e_to, e_cost])

d = [float('inf')] * V
negative = [False] * V
d[0] = 0
for _ in range(V):
    for e in nodes:
        if d[e[0]] != float('inf') and d[e[1]] > d[e[0]] + e[2]:
            d[e[1]] = d[e[0]] + e[2]
for _ in range(V):
    for e in nodes:
        if d[e[0]] != float('inf') and d[e[1]] > d[e[0]] + e[2]:
            d[e[1]] = d[e[0]] + e[2]
            negative[e[1]] = True
        if negative[e[0]]:
            negative[e[1]] = True

if negative[V - 1]:
    print('inf')
else:
    print(- d[V - 1])

### FIXED CODE ###

'''
V, E : Vは頂点数、Eは辺数
nodes : e = [from, to, cost] を要素とする辺のリスト（有向辺）
☆負のループがあっても、それがゴールと非連結な場所にあった場合関係ない。
つまり「0→負のループ→N-1」という経路が存在するときのみ問題になる。
0→負のループ、という経路があるかどうかは0からの距離がfloat('inf')でないことで調べられる
負のループのある点→N-1という経路があるかどうかは、更新の際にnegative[i]から辺が伸びている頂点も更新することで調べられる。
'''
V, E = map(int, input().split())
nodes = []
for _ in range(E):
    e_from, e_to, e_cost = map(int, input().split())
    e_from -= 1
    e_to -= 1 #頂点を0-indexedに
    e_cost *= -1
    nodes.append([e_from, e_to, e_cost])

d = [float('inf')] * V
negative = [False] * V
d[0] = 0
for _ in range(V):
    for e in nodes:
        if d[e[0]] != float('inf') and d[e[1]] > d[e[0]] + e[2]:
            d[e[1]] = d[e[0]] + e[2]
for _ in range(V):
    for e in nodes:
        if d[e[0]] != float('inf') and d[e[1]] > d[e[0]] + e[2]:
            d[e[1]] = d[e[0]] + e[2]
            negative[e[1]] = True
        if negative[e[0]]:
            negative[e[1]] = True

if negative[V - 1]:
    print('inf')
else:
    print(- d[V - 1])
### BUGGY CODE ###

N = int(input())
A = []
for _ in range(N):
    A.append(int(input()))

for i in range(N):
    # rem = A[i]
    # A.remove(rem)
    # print(max(A))
    # A.insert(i, rem)
    ans = 0
    for j in range(N):
        if not i == j and ans < A[i]:
            ans = A[j]

    print(ans)



### FIXED CODE ###

import copy

N = int(input())
A = []
for _ in range(N):
    A.append(int(input()))

result = max(A)
ind = A.index(result)

for i in range(N):
    if i == ind:
        a = copy.deepcopy(A)
        a.remove(result)
        print(max(a))
    else:
        print(result)
### BUGGY CODE ###

x, y = map(int, input().split())
if (x + y) % 3 != 0:
    print(0)
    exit(0)
row = (x + y) // 3
mod = 10 ** 9 + 7
if x < row or x > row * 2:
    print(0)
    exit(0)
x = x - row

def pow_mod(a, x, mod):
    if x == 0:
        return 1 % mod
    if x == 1:
        return a % mod
    half = pow_mod(a, x // 2, mod)
    half = half * half % mod
    if x % 2 == 1:
        half = half * a % mod
    return half

def rev(i, mod):
    return pow_mod(i, mod - 2, mod)

def calc(n, m, mod):
    if n == m or m == 0:
        return 1
    if n - m < m:
        m = n - m
    ans = 1
    for i in range(1, m + 1):
        f1 = ans * (n-i+1) * rev(i, mod) % mod
        ans = f1
    return ans


print(calc(row, x, mod))


### FIXED CODE ###

x, y = map(int, input().split())
if (x + y) % 3 != 0:
    print(0)
    exit(0)
row = (x + y) // 3
mod = 10 ** 9 + 7
if x < row or x > row * 2:
    print(0)
    exit(0)
x = x - row

def pow_mod(a, x, mod):
    if x == 0:
        return 1 % mod
    if x == 1:
        return a % mod
    half = pow_mod(a, x // 2, mod)
    half = half * half % mod
    if x % 2 == 1:
        half = half * a % mod
    return half

def rev(i, mod):
    return pow_mod(i, mod - 2, mod)

def calc(n, m, mod):
    if n == m or m == 0:
        return 1
    if n - m < m:
        m = n - m
    ans = 1
    for i in range(1, m + 1):
        f1 = ans * (n-i+1) * rev(i, mod) % mod
        ans = f1
    return ans


print(calc(row, x, mod))
### BUGGY CODE ###

import numpy as np
N = int(input())
A = list(map(int,input().split()))
aa = np.array(A)
ans = 0
for i in aa:
  b = (i % aa == 0)
  if sum(b) == 1:
    ans += 1
print(ans)

### FIXED CODE ###

import numpy as np
N = int(input())
A = list(map(int,input().split()))
aa = sorted(A)
ans = [0 for i in range(aa[-1]+1)]
for i in aa:
  ans[i] += 1
  if ans[i] == 1:
    for j in range(i*2,aa[-1]+1,i):
      ans[j] += 2
print(ans.count(1))
### BUGGY CODE ###

n, k = input().split()
n, k = int(n), int(k)
balls = [int(x) for x in input().split()]
dic = {}
for x in balls:
	if x not in dic:
		dic[x] = 1
	else:
		dic[x] += 1
change = 0
qnt = list(dic.values())
qnt.sort()
while len(qnt) > k:
	change += qnt[0]
	qnt.pop(0)
print(change)

### FIXED CODE ###

n, k = input().split()
n, k = int(n), int(k)
balls = input().split()
dic = {}
for x in balls:
	if x not in dic:
		dic[x] = 1
	else:
		dic[x] += 1
change = 0
qnt = list(dic.values())
qnt.sort()
dif = len(qnt) - k
for x in range(0, dif):
	change += qnt[x]
print(change)
### BUGGY CODE ###

def main():
    n = int(input())
    alis = list(map(int, input().split()))
    adic = {}
    for num in alis:
        if num in adic:
            adic[num] += 1
        else:
            adic[num] = 1
    
    anslis = []

    q = int(input())
    bclis = []
    for i in range(q):
        b, c = map(int,input().split())
        if b in adic:
            kazu = adic[b]
            adic[b] = 0
            if c in adic:
                adic[c] += kazu
            else:
                adic[c] = kazu
        ans = 0
        for key in adic:
            ans += adic[key] * key
        anslis.append(ans)
    for num in anslis:
        print(num)
    



    

 
    
    
if __name__ == "__main__":
    main()

### FIXED CODE ###

def main():
    n = int(input())
    alis = sorted(map(int, input().split()))
    total = sum(alis)
    adic = {}
    for num in alis:
        if num in adic:
            adic[num] += 1
        else:
            adic[num] = 1
    
    anslis = []

    q = int(input())
    bclis = []
    for i in range(q):
        b, c = map(int,input().split())
        if b in adic:
            kazu = adic[b]
            adic[b] = 0
            total -= b * kazu
            if c in adic:
                adic[c] += kazu
            else:
                adic[c] = kazu
            total += c * kazu
        print(total)
    
    
if __name__ == "__main__":
    main()
### BUGGY CODE ###

import queue
H,W=map(int, input().split())

inmap = [input() for _ in range(H)]

q = queue.Queue(10)
q.put((0,0,1))

cood = [(1,0),(-1,0),(0,1),(0,-1)]

res = 0

visited = set([(0,0)])

while not q.empty():
    x,y,cnt=q.get(False)
    # print(x,y)
    if x+1 == W and y+1 == H:
        res = cnt
        break
    for dx, dy in cood:
        if x+dx >= 0 and x+dx < W and y+dy >= 0 and y+dy < H:
            # print(visited)
            if inmap[y+dy][x+dx] != '#' and not (x+dx, y+dy) in visited:
                q.put((x+dx, y+dy, cnt+1))
                visited.add((x+dx, y+dy))

black = 0
for i in range(H):
    for j in range(W):
        if inmap[i][j] == '#':
            black += 1

# print((W-1, H-1) in visited)
if res == 0:
    print(-1)
else:
    print(H*W - black - res)

### FIXED CODE ###

import queue
H,W=map(int, input().split())
inmap = [input() for _ in range(H)]

q = queue.Queue(2500)
q.put((0,0,1))
cood = [(1,0),(-1,0),(0,1),(0,-1)]
res = 0

visited = set((0,0))

while not q.empty():
    x,y,cnt=q.get(False)
    if x+1 == W and y+1 == H:
        res = cnt
        break
    for dx, dy in cood:
        if x+dx >= 0 and x+dx < W and y+dy >= 0 and y+dy < H:
            if inmap[y+dy][x+dx] != '#' and not (x+dx, y+dy) in visited:
                q.put((x+dx, y+dy, cnt+1))
                visited.add((x+dx, y+dy))

black = 0
for i in range(H):
    for j in range(W):
        if inmap[i][j] == '#':
            black += 1

# print((W-1, H-1) in visited)
if res == 0:
    print(-1)
else:
    print(H*W - black - res)
### BUGGY CODE ###

l, r = map(int, input().split())
x = []
y = []
 
for i in range(l, r):
  for j in range(i+1, r+1):
    m = i * j % 2019
    x.append(m) 
print(min(x))

### FIXED CODE ###

l, r = map(int, input().split())
x = []

if l <= 2019 <= r:
  print(0)
elif r - l > 2018:
  print(0)
else:
  x = []
  for i in range(l, r):
    for j in range(i+1, r+1):
      m = i * j % 2019
      x.append(m) 
  print(min(x))
### BUGGY CODE ###

def ch_min(a, b):
    if (a > b):
        a = b
    return a


if __name__ == "__main__":
    N, K = map(int, input().split())
    h = list(map(int, input().split()))
    INF = 10 ** 10
    dp = [INF] * (10 ** 5 + 10)
    dp[0] = 0
    for i in range(N):
        for k in range(1, K + 1):
            if (i - k >= 0):
                dp[i] = ch_min(dp[i], dp[i - k] + abs(h[i] - h[i - k]))
    print(dp[N - 1])


### FIXED CODE ###

import numpy as np
N, K = map(int, input().split())
H = np.array(list(map(int, input().split())) + [0] * (K + 2), np.int32)
INF = 10 ** 9
dp = np.array([INF] * (N + K + 2), np.int32)
dp[0] = 0

for i in range(N):
    dp[i + 1:i + K + 1] = np.minimum(dp[i + 1:i + K + 1],
                                     dp[i] + np.abs(H[i + 1:i + K + 1] - H[i]))
print(dp[N - 1])
### BUGGY CODE ###

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

grade_k = 1
for i in range(k):
    grade_k = grade_k * a[i]

for i in range(k, n):
    if i==k:
        grade_im1 = grade_k
    grade_i = grade_im1 / a[i-k] * a[i]
    #print(grade_im1, grade_i)
    if grade_im1 < grade_i:
        print("Yes")
    else:
        print("No")
    grade_im1 = grade_i



### FIXED CODE ###

n,k = list(map(int, input().split(" ")))
#a = list(map(int, input().split(" ")))
a = []
for i, a_i in enumerate(input().split(" ")):
    a_i = int(a_i)
    a.append(a_i)
    if i<k:
        continue
    #print(a[i-k], a_i)
    if a[i-k] < a_i:
        print("Yes")
    else:
        print("No")
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**9)
INF=10**18
def input():
    return sys.stdin.readline().rstrip()

def main():
    H,W=map(int,input().split())
    A=[[] for _ in range(H)]
    B=[[] for _ in range(H)]
    C=[[0]*W for _ in range(H)]
    for i in range(H):
        A[i]=list(map(int,input().split()))
    for i in range(H):
        B[i]=list(map(int,input().split()))
    for i in range(H):
        for j in range(W):
            C[i][j]=abs(A[i][j]-B[i][j])
    C_sum=sum([sum(C[i]) for i in range(H)])
    dp=[[[False]*(C_sum*2+1) for _ in range(W)] for _ in range(H)]
    dp[0][0][C[0][0]]=True
    dp[0][0][-C[0][0]]=True
    for i in range(1,H):
        for k in range(C_sum*2+1):
            if dp[i-1][0][k]==True:
                dp[i][0][(k+C[i][0])%(C_sum*2+1)]=True
                dp[i][0][k-C[i][0]]=True
    for j in range(1,W):
        for k in range(C_sum*2+1):
            if dp[0][j-1][k]==True:
                dp[0][j][(k+C[0][j])%(C_sum*2+1)]=True
                dp[0][j][k-C[0][j]]=True
    
    for i in range(1,H):
        for j in range(1,W):
            for k in range(C_sum*2+1):
                if dp[i-1][j][k]==True:
                    dp[i][j][(k+C[i][j])%(C_sum*2+1)]=True
                    dp[i][j][k-C[i][j]]=True
                if dp[i][j-1][k]==True:
                    dp[i][j][(k+C[i][j])%(C_sum*2+1)]=True
                    dp[i][j][k-C[i][j]]=True
    for i in range(C_sum+1):
        if dp[H-1][W-1][i]==True:
            print(i)
            exit()
    
    

if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys
sys.setrecursionlimit(10**9)
INF = 10**18


def input():
    return sys.stdin.readline().rstrip()


def main():
    H, W = map(int, input().split())
    A = [[] for _ in range(H)]
    B = [[] for _ in range(H)]
    C = [[0] * W for _ in range(H)]
    minusdigit = 80 * 80 * 2
    for i in range(H):
        A[i] = list(map(int, input().split()))
    for i in range(H):
        B[i] = list(map(int, input().split()))
    for i in range(H):
        for j in range(W):
            C[i][j] = abs(A[i][j] - B[i][j])
    dp = [[0] * W for _ in range(H)]
    dp[0][0] = ((1 << minusdigit) << C[0][0]) | ((1 << minusdigit) >> C[0][0])
    for i in range(1, H):
        dp[i][0] = (dp[i - 1][0] << C[i][0]) | (dp[i - 1][0] >> C[i][0])
    for j in range(1, W):
        dp[0][j] = (dp[0][j - 1] << C[0][j]) | (dp[0][j - 1] >> C[0][j])

    for i in range(1, H):
        for j in range(1, W):
            dp[i][j] = (dp[i - 1][j] << C[i][j]) | (dp[i - 1][j] >> C[i][j]) | (dp[i][j - 1] << C[i][j]) | (dp[i][j - 1] >> C[i][j])
    ans = dp[H - 1][W - 1]
    for i in range(len(bin(ans)) - (2 + minusdigit)):
        if (ans >> (i + minusdigit)) & 0b1 == 1 or (-i + minusdigit >= 0 and (ans >> (-i + minusdigit)) & 0b1 == 1):
            print(i)
            exit()


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

a, b = map(int, input().split())
p = 1

while a <= b:
    p *= a
    a += 1

if p > 0:
    print("Positive")
elif p == 0:
    print("Zero")
else:
    print("Negative")

### FIXED CODE ###

a, b = map(int, input().split())
if 0 < a <= b:
    print("Positive")
elif a <= b < 0:
    if (b-a+1) % 2 == 0:
        print("Positive") 
    else:
        print("Negative")
else:
    print("Zero")
### BUGGY CODE ###

mod = 10**9+7
S = list(input())
Q=0
DP=[[0]*3 for i in range(len(S))]#DP[x][y] x+1文字目までの
#y=0,1,2,3 = A,AB,ABC
if S[0] == "A" or S[0]=="?":
    DP[0] = [1,0,0]
    if S[0]=="?":
        Q=1
else:
    DP[0] = [0,0,0]
for i,s in enumerate(S):
    if i==0:continue
    a,b,c = DP[i-1]
    if s=="A":
        DP[i]=[(a+3**Q)%mod,b,c]
    elif s=="B":
        DP[i]=[a,(a+b)%mod,c]
    elif s=="C":
        DP[i]=[a,b,(b+c)%mod]
    else:
        DP[i]=[(3**Q+3*a)%mod,(a+3*b)%mod,(b+3*c)%mod]
        Q+=1
print(DP[len(S)-1][2]%mod)

### FIXED CODE ###

mod = 10**9+7
S = list(input())
Thankyou = 1
DP=[]
#DP[x][y] x+1文字目までを見たときの、
#y=0,1,2 : A,AB,ABCの登場回数
if S[0] == "A" or S[0]=="?":
    DP.append([1,0,0])
    if S[0]=="?":
        Thankyou = 3
else:
    DP.append([0,0,0])
for i,s in enumerate(S):

    if i==0:continue
    a,b,c = DP[i-1]
    if s=="A":
        DP.append([(a+Thankyou)%mod,b,c])
    elif s=="B":
        DP.append([a,(a+b)%mod,c])
    elif s=="C":
        DP.append([a,b,(b+c)%mod])
    else:
        DP.append([(Thankyou+3*a)%mod,(a+3*b)%mod,(b+3*c)%mod])
        Thankyou *= 3
        Thankyou %= mod
print(DP[len(S)-1][2]%mod)
### BUGGY CODE ###

# D - Triangles
from bisect import bisect_left
import numpy as np
N = int(input())
L = sorted(np.array(list(map(int, input().split()))))

ans = 0
for i, a in enumerate(L):
    if i == N - 2:
        break
        
    for j, b in enumerate(L[i + 1:]):
        j += i + 1
        if j == N - 1:
            break
            
        s = a + b
        ans += bisect_left(L[j + 1:], s)
                
print(ans)

### FIXED CODE ###

from bisect import bisect_left
N = int(input())
L = sorted(list(map(int, input().split())))

ans = 0
for b in range(1, N - 1):
    for a in range(b):
        ans += bisect_left(L, L[a] + L[b]) - b - 1
        
print(ans)
### BUGGY CODE ###

N, S = int(input()), str(input())
S = S.translate(str.maketrans({'E':'0', 'W':'1'}))
cost = N
for i in range(N):
    res = '0'* (i-1) + '1' * (N-1-i)
    S_test = S[:i-1]+ S[i+1:]
    bit = int(res, 2)^int(S_test, 2)
    cost = min(cost, bin(bit).count('1'))
print(cost)

### FIXED CODE ###

N, S = int(input()), str(input())
for i in range(N):
    if i == 0:
        res = S[1:].count('E')
        cost = res
    else:
        if S[i-1] == 'W': res += 1
        if S[i] == 'E': res -= 1
    cost = min(cost, res)
print(cost)
### BUGGY CODE ###

n, m, k = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
aa = a.copy()
bb = b.copy()
sa = sum(a)
sb = sum(b)
c = [10**10 for i in range(n+m+1)]
c[n+m] = sa + sb
x = sa + sb
c[0] = 0
for i in range(1,n+m):
  if len(a) == 0:
    x -= b[-1]
    b.pop(-1)
    c[n+m-i] = x
    continue
  if len(b) == 0:
    x -= a[-1]
    a.pop(-1)
    c[n+m-i] = x
    continue
  if a[-1] > b[-1]:
    x -= a[-1]
    a.pop(-1)
  else:
    x -= b[-1]
    b.pop(-1)
  c[n+m-i] = x

s = 0
d = [0 for i in range(n+m+1)]
for i in range(n+m+1):
  if i == 0:
    continue
  if len(aa) == 0:
    s += bb[0]
    bb.pop(0)
    d[i] = s
    continue
  if len(bb) == 0:
    x += aa[0]
    aa.pop(0)
    d[i] = s
    continue
  if aa[0] > bb[0]:
    s += bb[0]
    bb.pop(0)
  else:
    s += aa[0]
    aa.pop(0)
  d[i] = s
  e = min(c[i],d[i])
  if e > k:
    print (i-1)
    exit()
if e <= k:
  print (n+m)
else:
  print (0)


### FIXED CODE ###

import bisect
n, m, k = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))

sa = [0 for i in range(n+1)]
sb = [0 for i in range(m+1)]

c = 0

for i in range(n):
  c += a[i]
  sa[i+1] = c
c = 0
for i in range(m):
  c += b[i]
  sb[i+1] = c
ans = 0
# if k >= sum(a)+sum(b):
#   print (n+m)
#   exit()
for i in range(n+1):
  x = k - sa[i]
  if x < 0:
    continue
  y = bisect.bisect_right(sb,x)
  y += i
  ans = max(ans, y-1)
print (ans)
### BUGGY CODE ###

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

INF = float('inf')
dp = [INF for _ in range(N)]

dp[0] = 0
for i in range(1, min(N, K+1)):
    min_t = INF
    for j in range(1, i+1):
        min_t = min(min_t, dp[i-j] + abs(h[i-j] - h[i]))
    dp[i] = min_t

for i in range(K+1, N):
    min_t = INF
    for j in range(1, K+1):
        min_t = min(min_t, dp[i-j] + abs(h[i-j] - h[i]))
    dp[i] = min_t

print(dp[N-1])


### FIXED CODE ###

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

INF = float('inf')
dp = [0]

for i in range(1, N):
    min_t = INF
    for j in range(1, K+1):
        if i - j < 0:
            continue
        min_t = min(min_t, dp[i-j] + abs(h[i-j] - h[i]))
    dp.append(min_t)

print(dp[N-1])
### BUGGY CODE ###

N = int(input())
a = list(map(int,input().split()))
S = 0
for i in range(N):
    S ^= a[i]

Ans = ""
for i in range(N):
    Ans = Ans + str(S^a[i]) + " "

print(Ans)

### FIXED CODE ###

N = int(input())
a = list(map(int,input().split()))
S = 0
for i in range(N):
    S ^= a[i]

Ans = ""
for i in range(N):
    print(S^a[i])
### BUGGY CODE ###

S=input()
t=input()
L=len(t)
s=S
for i in range(0,L):
    s=s+S
k=0
m=0
a=0
while k<=L-1:
    if t[k] in S:
        if t[k]==s[m]:
            k+=1
            m+=1
        else:
            m+=1
    else:
        print(-1)
        a=10
        break
if a==0:
    print(m)

### FIXED CODE ###

from bisect import bisect
s=input()
t=input()
n,m=len(s),len(t)
alf=list("abcdefghijklmnopqrstuvwxyz")
data=[[] for i in range(26)]
for i in range(26):
    for j in range(n):
        if alf[i]==s[j]:
            data[i].append(j)
l=[0]*26
for i in range(26):
    l[i]=len(data[i])
ind=-1
count=0
for i in range(m):
    k=alf.index(t[i])
    if data[k]:
        p=bisect(data[k],ind)
        if p==l[k]:
            count+=1
            ind=data[k][0]
        else:
            ind=data[k][p]
    else:
        print(-1)
        break
else:
    print(n*count+ind+1)