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

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

    ans = 0

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

    print(ans)

if __name__ == '__main__':
    main()


### FIXED CODE ###

from collections import Counter
def main():
    n = int(input())
    s = input()
    d = Counter(s)
    ans = d['R'] * d['G'] * d['B']

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

    print(ans)

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

N = int(input())
TA = [0] * N

vote = 0
t, a = 0, 0
for i in range(N):
    T, A = map(int, input().split())
    if vote == 0:
        t, a = T, A
        vote = t+A
        continue
    t1, a1 = T, A
    while not (t <= t1 and a <= a1):
        t1 += T
        a1 += A
    t, a = t1, a1
print(t+a)




### FIXED CODE ###

N = int(input())
TA = []
for i in range(N):
    T, A = map(int, input().split())
    TA.append((T, A))

T, A = TA[0]
answer = T+A
p = 1
prev = p
pT, pA = T, A
for i in range(1,N):
    # (T+A) * p >= prev
    # p >= prev/(T+A)
    T, A = TA[i]
    s = T+A
    p = (answer+s-1)//s
    p1 = (pT+T-1)//T
    p2 = (pA+A-1)//A
    p = max([p,p1,p2])
    pT, pA = p*T, p*A
    answer =  pT+pA
    #print(T, A, p, answer, sep="\t")
print(answer)
### BUGGY CODE ###

A, B, K = map(int, input().split())

for k in range(K):
    if A >= 1:
        A -= 1
        continue
    if B >= 1:
        B -= 1
        continue
        
print(A, B)

### FIXED CODE ###

import sys
A, B, K = map(int, input().split())

if A >= K:
    A -= K
    print(A, B)
    sys.exit(0)
else:
    K -= A
    if B >= K:
        B -= K
        print(0, B)
        sys.exit(0)
    else:
        print(0, 0)
### BUGGY CODE ###

n = int(input())
xl = [[int(i) for i in input().split(' ')] for j in range(n)]
import numpy as np

ls = np.array([[i-j, i+j] for i, j in xl])
ls = ls[ls[:, 0].argsort()]

i, dr = 0, 0
while i in range(len(ls)-1):
    a, b = ls[i], ls[i+1]
    if a[1]>b[0]:
        dr += 1
        ls = np.delete(ls, i+1, 0)
    else:
        i += 1
print(len(ls))

### FIXED CODE ###

n = int(input())
xl = [[int(i) for i in input().split(' ')] for j in range(n)]

ls = sorted([[i-j, i+j] for i, j in xl], key=lambda x: x[1])

i, dr = 0, 0
while True:
    if (len(ls)<=1) | (i+1 >= len(ls)):
        break
    a, b = ls[i], ls[i+1]
    if a[1]>b[0]:
        dr += 1
        ls.pop(i+1)
    else:
        i += 1

print(len(ls))
### BUGGY CODE ###

from itertools import permutations
N, M, R = map(int, input().split())
r = list(map(int, input().split()))
G = [[10**6]*(N+1) for _ in range(N+1)]
for _ in range(M):
    a, b, c = map(int, input().split())
    G[a][b] = c
    G[b][a] = c

for k in range(1, N+1):
    for i in range(1, N+1):
        for j in range(1, N+1):
            if G[i][k]+G[k][j] < G[i][j]:
                G[i][j] = G[i][k] + G[k][j]


ans = 10**10
for elem in permutations(r):
    res = 0
    for i in range(R-1):
        res += G[elem[i]][elem[i+1]]
    ans = min(ans, res)
print(ans)


### FIXED CODE ###

from itertools import permutations
N, M, R = map(int, input().split())
r = list(map(int, input().split()))
G = [[10**18]*(N+1) for _ in range(N+1)]
for _ in range(M):
    a, b, c = map(int, input().split())
    G[a][b] = c
    G[b][a] = c

for k in range(1, N+1):
    for i in range(1, N+1):
        for j in range(1, N+1):
            if G[i][k]+G[k][j] < G[i][j]:
                G[i][j] = G[i][k] + G[k][j]


ans = 10**18
for elem in permutations(r):
    res = 0
    for i in range(R-1):
        res += G[elem[i]][elem[i+1]]
    ans = min(ans, res)
print(ans)
### BUGGY CODE ###

from itertools import combinations
from operator import itemgetter
N = int(input())
XY = [list(map(int, input().split())) for _ in range(N)]
X, Y = list(map(list, zip(*XY)))

P = [abs(x1 - x2) for x1, x2 in combinations(X, 2)]
P = set(P)
if 0 in P:
    P.remove(0)
P = list(P)
Q = [abs(y1 - y2) for y1, y2 in combinations(Y, 2)]
Q = set(Q)
if 0 in Q:
    Q.remove(0)
Q = list(Q)
ans = 10**10
geta = 10**10
for p in P:
    S = {(x+p)*geta+y for x, y in XY}
    la = 0
    for x, y in XY:
        if x*geta + y not in S:
            la += 1
    ans = min(ans, la)

for q in Q:
    S = {x*geta+y+q for x, y in XY}
    la = 0
    for x, y in XY:
        if x*geta + y not in S:
            la += 1
    ans = min(ans, la)
S = {x*geta+y for x, y in XY}
for p in P:
    for q in Q:
        S1 = {(x+p)*geta+y+q for x, y in XY}
        S2 = {(x+p)*geta+y-q for x, y in XY}
        ans = min(ans, N - len(S & S1), N - len(S & S2))
        
if N == 1:
    ans = 1
print(ans)

### FIXED CODE ###

from collections import Counter
from itertools import combinations
N = int(input())
XY = [list(map(int, input().split())) for _ in range(N)]
XY.sort()
A = Counter()
for (x1, y1), (x2, y2) in combinations(XY, 2):
    A[(x1-x2, y1-y2)] += 1
if N == 1:
    print(1)
else:
    print(N - max(A.values()))
### BUGGY CODE ###

n = int(input())
l = []
for i in range(n):
    l.append(int(input()))

for j in range(len(l)):
    tmp = l.pop(j)
    print(max(l))
    l.insert(j, tmp)

### FIXED CODE ###

n = int(input())
l = []
for i in range(n):
    l.append(int(input()))

l_b = sorted(l)
max_a = l_b[-1]
max_b = l_b[-2]

for j in range(len(l)):
    if max_a == l[j]:
        print(max_b)
    else:
        print(max_a)
### BUGGY CODE ###

N = int(input())
A = list(map(int, input().split()))
mod = 10**9+7
 
for i in range(N): A[i] = format(A[i], "#b") #ここで全て60ビットの二進数に変換
#print(A)

sum = 0
c0 = [0]*60
c1 = [0]*60
for i in range(N):
    for j in range(60):
        if A[i][-(j+1)] == "0": #str型であることに注意！
            c0[j] += 1
        elif A[i][-(j+1)] == "1":
            c1[j] += 1
        else:
            break
 
for i in range(60):
    if c1[i] > 0:
        c0[i] = N - c1[i] 
    sum += (c0[i] * c1[i]) << i
    sum %= mod
 
print(sum%mod)

### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
mod = 10**9+7
xorsum = 0
for i in range(60):
  c1 = sum([1 for a in A if (a >> i) & 1]) #
  xorsum += (c1*(N-c1)*(1<<i))
  xorsum = xorsum%mod
print(xorsum%mod)
### BUGGY CODE ###

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

for i in range(N)[::-1]:
    value = n[i]
    for k in range(i):
        if n[k]-n[i] >1:
            print("No")
            exit()
print("Yes")

### FIXED CODE ###

n=int(input())
h=[int(i) for i in input().split()]
f=1
h[0]-=1
for i in range(1,n):
    if h[i]-h[i-1]>=1:h[i]+=-1
    elif h[i]-h[i-1]==0:h[i]+=0
    else:
        f=0
        print("No")
        break
if f==1:print("Yes")
### BUGGY CODE ###

n, k = map(int, input().split())
a_list = [int(input()) for _ in range(n)]

dp = [1] * n

for i in range(n):
    for j in range(max(0, i-n), i):
        if abs(a_list[i] - a_list[j]) <= k:
            dp[i] = max(dp[i], dp[j] + 1)

ans = max(dp)
print(ans)

### FIXED CODE ###

n, k = map(int, input().split())
a_list = [int(input()) for _ in range(n)]

dp = [1] * n

for i in range(n):
    for j in range(max(0, i - 100), i):
        if abs(a_list[i] - a_list[j]) <= k:
            dp[i] = max(dp[i], dp[j] + 1)

ans = max(dp)
print(ans)
### BUGGY CODE ###

def main():
    from functools import lru_cache
    h, w, d = map(int, input().split())

    a = []
    for i in range(1, h + 1):
        l = map(int, input().split())
        for j, k in enumerate(l, 1):
            a.append((k, (i, j)))

    a.sort(key=lambda x: x[0])

    q = int(input())

    @lru_cache(maxsize=q)
    def Q(l, r):
        _, (x, y) = a[l - 1]

        s = 0
        for k, (i, j) in a[l - 1::d]:
            s += abs(x - i) + abs(y - j)
            if r == k:
                break
            x, y = i, j
        return s

    res = []
    for _ in range(q):
        l, r = map(int, input().split())
        s = Q(l, r)
        res.append(s)

    ans = '\n'.join(map(str, res))
    print(ans)


if __name__ == '__main__':
    main()


### FIXED CODE ###

def main():
    from itertools import accumulate
    h, w, d = map(int, input().split())

    a = [0] * (h * w + 1)
    b = [0] * (h * w + 1)
    for i in range(1, h + 1):
        l = map(int, input().split())
        for j, k in enumerate(l, 1):
            a[k] = i
            b[k] = j

    c = [0] * (h * w + 1)
    for i in range(d + 1, h * w + 1):
        c[i] = c[i - d] + abs(a[i] - a[i - d]) + abs(b[i] - b[i - d])

    q = int(input())
    res = []
    for _ in range(q):
        l, r = map(int, input().split())
        res.append(c[r] - c[l])

    ans = '\n'.join(map(str, res))
    print(ans)


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

H,W = map(int,input().split())
A = [[] for i in range(H)]
B = [[] for i in range(H)]

for i in range(H):
	a = list(map(int,input().split()))
	A[i] = a
for i in range(H):
	b = list(map(int,input().split()))
	B[i] = b

D = [[abs(A[i][j]) - abs(B[i][j]) for j in range(W)] for i in range(H)]
R = 160*160
dp = [[[False for k in range(R)] for j in range(W)] for i in range(H)]
dp[0][0][R//2 - D[0][0]] = True
dp[0][0][R//2 + D[0][0]] = True
for i in range(H):
	for j in range(W):
		for n in range(R):
			if not dp[i][j][n]:
				continue
			if j != W-1:
				d = D[i][j+1]
				dp[i][j+1][n+d] = True
				dp[i][j+1][n-d] = True
			if i != H-1:
				d = D[i+1][j]
				dp[i+1][j][n+d] = True
				dp[i+1][j][n-d] = True

h,w = H-1, W-1
M = R // 2
for i in range(160*80):
	if dp[h][w][M - i] or dp[h][w][M - i]:
		print(i)
		exit()

### FIXED CODE ###

H,W = map(int,input().split())
A = [[] for i in range(H)]
B = [[] for i in range(H)]

for i in range(H):
	a = list(map(int,input().split()))
	A[i] = a
for i in range(H):
	b = list(map(int,input().split()))
	B[i] = b

D = [[abs(A[i][j] - B[i][j]) for j in range(W)] for i in range(H)]
R = 160*80
"""
dp = [[[False for k in range(R)] for j in range(W)] for i in range(H)]
dp[0][0][D[0][0]] = True
for i in range(H):
	for j in range(W):
		r = 80 * (i+j+2)
		for n in range(r):
			if not dp[i][j][n]:
				continue
			if j != W-1:
				d = D[i][j+1]
				dp[i][j+1][n+d] = True
				dp[i][j+1][abs(n-d)] = True
			if i != H-1:
				d = D[i+1][j]
				dp[i+1][j][n+d] = True
				dp[i+1][j][abs(n-d)] = True

"""
dp = [[0 for j in range(W)] for i in range(H)]
dp[0][0] = 2**(R + D[0][0]) | 2**(R - D[0][0])
for i in range(H):
	for j in range(W):
		if j != W-1:
			d = D[i][j+1]
			dp[i][j+1] |= (dp[i][j] << d | dp[i][j] >> d)
		if i != H-1:
			d = D[i+1][j]
			dp[i+1][j] |= (dp[i][j] << d | dp[i][j] >> d)
h,w = H-1, W-1
for i in range(R):
	mask = 2 ** (R+i) | 2 ** (R-i)
	if dp[h][w] & mask > 0:
		print(i)
		exit()
### BUGGY CODE ###

import collections
import bisect
import sys
input = sys.stdin.readline

N, M, Q = map(int, input().split())
LR = [tuple(map(int, input().split())) for i in range(M)]
LR.sort(key=lambda x: x[1])
table = collections.defaultdict(list)
for l, r in LR:
    table[l].append(r)
for i in range(Q):
    p, q = map(int, input().split())
    ret = 0
    for j in range(p, q+1):
        ret += bisect.bisect_right(table[j], q)
    print(ret)


### FIXED CODE ###

import collections
import bisect
import sys
input = sys.stdin.readline
N, M, Q = map(int, input().split())
LR = [tuple(map(int, input().split())) for i in range(M)]
dp = [[0]*(N+1) for i in range(N+1)]

for L, R in LR:
    dp[L][R] += 1
for i in reversed(range(1, N)):
    for j in range(1, N+1):
        dp[i][j] += dp[i+1][j]

for i in range(1, N+1):
    for j in range(1, N+1):
        dp[i][j] += dp[i][j-1]


for _ in range(Q):
    p, q = map(int, input().split())
    print(dp[p][q])
### BUGGY CODE ###

from fractions import gcd
from functools import reduce

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

def f(n,l):
    return sum([n % x for x in l])

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

def lcm_m(l):
    return int(reduce(lcm, l, 1))

num = lcm_m(a) - 1
print(f(num, a))


### FIXED CODE ###

from fractions import gcd
from functools import reduce

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

def f(n,l):
    return sum([n % x for x in l])

m = 1
for x in a:
    m *= x
print(f(m-1, a))
### BUGGY CODE ###

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

ans = 0

while len(A) == N:
  A = [a for a in A if a % 2 == 0]
  if len(A) == N:
    ans += 1
    
print(ans)
    

### FIXED CODE ###

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

ans = 0

while True:
  exist_odd = False
  for a in A:
    if a % 2 != 0:
      exist_odd = True
  if exist_odd:
    break
  for i in range(N):
    A[i] /= 2
  ans += 1
  
print(ans)
### BUGGY CODE ###

import numpy as np
a = np.zeros(2,dtype = "int64")

N = int(input())
a[0] = N
a[1] = 0
for i in range (1,a[0]):
  a[1] = a[1] + i
print(a[1])

### FIXED CODE ###

n = int(input())
ans = n * (n - 1) // 2
print(int(ans))
### BUGGY CODE ###

N, Q = map(int, input().split())
S = input()
lr = [list(map(int, input().split())) for _ in range(Q)]
 
for lr_ in lr:
    l, r = lr_[0], lr_[1]
    
    print(S[l - 1: r].count('AC'))

### FIXED CODE ###

n, q = map(int, input().split())
s = input()
dp = [0 for _ in range(len(s))]

for i in range(1, len(s)):
    if(s[i-1: i+1] == 'AC'): dp[i] = dp[i-1] + 1
    else: dp[i] = dp[i-1]

for _ in range(q):
    l, r = map(int, input().split())
    print(dp[r-1] - dp[l-1])
### BUGGY CODE ###

from _collections import defaultdict

N = int(input())
S = input()

counted_dict = defaultdict(list)
for i in range(N):
    char = S[i]
    if char == "R":
        counted_dict["R"].append(i)
    elif char == "G":
        counted_dict["G"].append(i)
    else:
        counted_dict["B"].append(i)

count = 0
for x in range(len(counted_dict["R"])):
    r_pos = counted_dict["R"][x]
    for y in range(len(counted_dict["G"])):
        g_pos = counted_dict["G"][y]
        for z in range(len(counted_dict["B"])):
            b_pos = counted_dict["B"][z]
            colors_pos_list = [r_pos, g_pos, b_pos]
            colors_pos_list.sort()
            if not colors_pos_list[2] + colors_pos_list[0] == 2 * colors_pos_list[1]:
                count += 1

print(count)


### FIXED CODE ###

N = int(input())
S = input()

total_comb = S.count('R')*S.count('G')*S.count('B')

minus = 0
for i in range(N-2):
    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[k] != S[i]):
                minus += 1

print(total_comb - minus)
### BUGGY CODE ###

import sys
N,K=map(int, input().split())
p=[]
for i in range (0,N):
  r=list(map(int, input().split() )) 
  p.append(r)
p.sort()
q=[]
for i in range(0,N):
  q+=[p[i][0]]*p[i][1]
  if len(q)>K:
    print(q[K-1])
    sys.exit()

### FIXED CODE ###

import sys
N,K=map(int, input().split())
p=[]
for i in range (0,N):
  r=list(map(int, input().split() )) 
  p.append(r)
p.sort()
k=0
for i in range(0,N):
  k+=p[i][1]
  if k>=K:
    print(p[i][0])
    sys.exit()
### BUGGY CODE ###

import sys
input = sys.stdin.readline
import collections
def bfs(sy, sx, gy, gx):
    q = collections.deque()
    q.append((sy, sx))
    dist = [[-1] * W for _ in range(H)]
    dist[sy][sx] = 0
    dx = [(-1, 0), (1, 0), (0, -1), (0, 1)]
    dx2 = [(-2, -2), (-2, -1), (-2, 0), (-2, 1), (-2, 2), (-1, -2), (-1, -1),(-1, 1), (-1, 2), (0, -2), (0, 2), (1, -2), (1, -1), (1, 1), (1, 2), (2, -2), (2, -1), (2, 0), (2, 1), (2, 2)]
    while len(q) != 0:
        h, w = q.popleft()
        d = dist[h][w]
        for x, y in dx:
            h2 = h + y
            w2 = w + x
            if h2 >= 0 and h2 < H and w2 >= 0 and w2 < W:
                if grid[h2][w2] == ".":
                    if dist[h2][w2] == -1:
                        dist[h2][w2] = d
                        q.append((h2, w2))
                    elif d < dist[h2][w2]:
                        dist[h2][w2] = d
                        q.append((h2, w2))
        for x, y in dx2:
            h2 = h + y
            w2 = w + x
            if h2 >= 0 and h2 < H and w2 >= 0 and w2 < W:
                if grid[h2][w2] == "." and (dist[h2][w2] == -1 or d + 1 < dist[h2][w2]):
                    dist[h2][w2] = d + 1
                    q.append((h2, w2))
    return dist[gy][gx]

H, W = map(int, input().split())
Ch, Cw = map(int, input().split())
Dh, Dw = map(int, input().split())
grid = [input() for _ in range(H)]
print(bfs(Ch-1, Cw-1, Dh-1, Dw-1))

### FIXED CODE ###

import sys
input = sys.stdin.readline
import collections
def bfs(sy, sx, gy, gx):
    q = collections.deque()
    q.append((sy, sx))
    dist = [[-1] * W for _ in range(H)]
    dist[sy][sx] = 0
    dx = [(-1, 0), (1, 0), (0, -1), (0, 1)]
    dx2 = [(-2, -2), (-2, -1), (-2, 0), (-2, 1), (-2, 2), (-1, -2), (-1, -1),(-1, 1), (-1, 2), (0, -2), (0, 2), (1, -2), (1, -1), (1, 1), (1, 2), (2, -2), (2, -1), (2, 0), (2, 1), (2, 2)]
    while len(q) != 0:
        h, w = q.popleft()
        d = dist[h][w]
        for x, y in dx:
            h2 = h + y
            w2 = w + x
            if h2 >= 0 and h2 < H and w2 >= 0 and w2 < W:
                if grid[h2][w2] == ".":
                    if dist[h2][w2] == -1:
                        dist[h2][w2] = d
                        q.appendleft((h2, w2))
                    elif d < dist[h2][w2]:
                        dist[h2][w2] = d
                        q.appendleft((h2, w2))
        for x, y in dx2:
            h2 = h + y
            w2 = w + x
            if h2 >= 0 and h2 < H and w2 >= 0 and w2 < W:
                if grid[h2][w2] == "." and (dist[h2][w2] == -1 or d + 1 < dist[h2][w2]):
                    dist[h2][w2] = d + 1
                    q.append((h2, w2))
    return dist[gy][gx]

H, W = map(int, input().split())
Ch, Cw = map(int, input().split())
Dh, Dw = map(int, input().split())
grid = [input() for _ in range(H)]
print(bfs(Ch-1, Cw-1, Dh-1, Dw-1))
### BUGGY CODE ###

# APC001C - Vacant Seat
def main():
    # if no vacant seat in [0, i)
    # -> seat[0] == seat[i] if i % 2 else seat[0] != seat[i]
    N = int(input())
    print(0, flush=1)
    seat_zero = input().rstrip()
    if seat_zero == "Vacant":
        return
    left, right = 0, N
    while True:
        mid = (left + right) // 2
        print(mid, flush=1)
        this_seat = input().rstrip()
        if this_seat = "Vacant":
            return
        if mid % 2 == (seat_zero != this_seat):
            left = mid
        else:
            right = mid


if __name__ == "__main__":
    main()

### FIXED CODE ###

# APC001C - Vacant Seat
def main():
    # if no vacant seat in [0, i)
    # -> seat[0] == seat[i] if i % 2 else seat[0] != seat[i]
    N = int(input())
    print(0, flush=1)
    seat_zero = input().rstrip()
    if seat_zero == "Vacant":
        return
    left, right = 0, N
    for _ in range(19):
        mid = (left + right) // 2
        print(mid, flush=1)
        this_seat = input().rstrip()
        if this_seat == "Vacant":
            return
        if mid % 2 == (seat_zero != this_seat):
            left = mid
        else:
            right = mid


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

# coding: utf-8
# Your code here!
import sys
readline = sys.stdin.readline
read = sys.stdin.read

n,m,*pqc = map(int, read().split())

g = [[] for _ in range(n)]
M = iter(pqc)

#s = [set() for _ in range(n)]
s = set()
for p,q,c in zip(M,M,M):
    p -= 1
    q -= 1
    g[p].append((q,c))
    g[q].append((p,c))
    if p==0 or q==0: s.add(c)
    #s[p].add(c)
    #s[q].add(c)
    


from collections import deque
def bfs01(g,s):
    n = len(g)
    #checked = [0]*n
    #checked[0] = 1

    q = deque((0,ci,1) for ci in s)
    res = {(0,ci):1 for ci in s}
    #print(res)
    while q:
        v,l,dv = q.popleft()
        for to,line in g[v]:
            tl = (to,line)
            ndv = dv+(not l==line)
            if tl not in res or res[tl] > ndv:
                res[tl] = ndv
                if l==line: q.appendleft((to,line,ndv))
                else: q.append((to,line,ndv))
                
                #print(tl,ndv,(v,l,dv),l==line)
                
        #print(q)

    return res



res = bfs01(g,s)

INF = 1<<30
ans = INF
for (v,l),val in res.items():
    if v==n-1:
        ans = min(ans,val)
        #print(v,l,val)

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

#print(res)




### FIXED CODE ###

# coding: utf-8
# Your code here!
import sys
readline = sys.stdin.readline
read = sys.stdin.read

n,m,*pqc = map(int, read().split())

g = {}
M = iter(pqc)

for p,q,c in zip(M,M,M):
    pc = ((p-1)<<20)+c
    qc = ((q-1)<<20)+c
    pp = (p-1)<<20
    qq = (q-1)<<20
    
    if pc not in g: g[pc] = []
    if qc not in g: g[qc] = []
    if pp not in g: g[pp] = []
    if qq not in g: g[qq] = []
    
    g[pc].append(qc)
    g[pc].append(pp)

    g[qc].append(pc)
    g[qc].append(qq)

    g[pp].append(pc)
    g[qq].append(qc)

if 0 not in g: g[0] = []

from collections import deque
q = deque([(0,0)])
res = {0:0}

mask = (1<<20)-1
while q:
    vl,dv = q.popleft()
    if res[vl] < dv: continue
    if (vl>>20) == n-1:
        res[(n-1)<<20] = dv+1
        break
    for tl in g[vl]:
        ndv = dv + (vl&mask==0 or tl&mask==0)
        if tl not in res or res[tl] > ndv:
            res[tl] = ndv
            if vl&mask==0 or tl&mask==0:
                q.append((tl,ndv))
            else:
                q.appendleft((tl,ndv))

if (n-1)<<20 in res:
    print(res[(n-1)<<20]//2)
else:
    print(-1)
### BUGGY CODE ###

S = input()

from collections import deque

q = deque()
if len(S) > 5: #4文字以下ならそもそもバツ→入れない
  q.append((len(S), S))
#ここに、次にチェックする文字列を入れていく
#今回はque(fi-fo)として使うので、popleftを使う

flag = False
while(q):
  nowlen, nows = q.popleft()
  nows5 = nows[0:5]
  nowsfrom5 = nows[5:]
  if nows5 == 'dream':
    if nowlen == 5:
      flag = True
      break
    else:
      if nowlen>=10: q.append((nowlen-5, nowsfrom5))
    if nows[0:7] == 'dreamer':
      if nowlen == 7:
        flag = True
        break
      else:
        if nowlen>=12: q.append((nowlen-7, nows[7:]))
  elif nows5 == 'erase':
    if nowlen == 5:
        flag = True
        break
    else:
      if nowlen>=10: q.append((nowlen-5, nowsfrom5))
    if nows[0:6] == 'eraser':
      if nowlen == 6:
        flag = True
        break
      else: 
        if nowlen>=11: q.append((nowlen-6, nows[6:]))

print('YES' if flag else 'NO')

### FIXED CODE ###

S = input()

from collections import deque

q = deque()
if len(S) > 5: #4文字以下ならそもそもバツ→入れない
  q.append((len(S), S))
#ここに、次にチェックする文字列を入れていく
#今回はque(fi-fo)として使うので、popleftを使う

flag = False
while(q):
  nowlen, nows = q.popleft()
  nows5 = nows[0:5]
  nowsfrom5 = nows[5:]
  if nows5 == 'dream':
    if nowlen == 5:
      flag = True
      break
    else:
      if nowlen>=10: q.append((nowlen-5, nowsfrom5))
    if nows[0:7] == 'dreamer':
      if nowlen == 7:
        flag = True
        break
      else:
        if nowlen>=12: q.append((nowlen-7, nows[7:]))
  elif nows5 == 'erase':
    if nowlen == 5:
        flag = True
        break
    else:
      if nowlen>=10: q.append((nowlen-5, nowsfrom5))
    if nows[0:6] == 'eraser':
      if nowlen == 6:
        flag = True
        break
      else: 
        if nowlen>=11: q.append((nowlen-6, nows[6:]))

print('YES' if flag else 'NO')
### BUGGY CODE ###

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

AL = [0]
for i in range(N):
    AL.append(AL[-1] + A[i])

BL = [0]
for i in range(M):
    BL.append(BL[-1] + B[i])

ans = 0
for i in range(N+1):
    for j in range(M+1):
        if AL[i] + BL[j] <= K:
            ans = max(ans, i+j)

print(ans)

### FIXED CODE ###

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

AL = [0]
for i in range(N):
    AL.append(AL[-1] + A[i])
BL = [0]
for i in range(M):
    BL.append(BL[-1] + B[i])

ans = 0
from bisect import bisect_right
for i in range(N+1):
    zan = K - AL[i]
    if zan < 0:
        break
    ind = bisect_right(BL, zan) - 1
    ans = max(ans, i + ind)

print(ans)