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

import sys
input = sys.stdin.readline
INF = float('inf')

def sol():
    N, M, L = map(int, input().split())
    ABC = [tuple(map(int, input().split())) for _ in range(M)]
    Q = int(input())
    ST = [tuple(map(int, input().split())) for _ in range(Q)]

    dist = [[INF] * N for _ in range(N)]
    fuel = [[INF] * N for _ in range(N)]

    for i in range(N):
        dist[i][i] = 0
        fuel[i][i] = 0

    for fr, to, cost in ABC:
        if cost > L:
            continue
        fr -= 1
        to -= 1
        dist[fr][to] = cost
        dist[to][fr] = cost

    for k in range(N):
        for i in range(N):
            for j in range(N):
                d = dist[i][k] + dist[k][j]
                dist[i][j] = min(dist[i][j], d)
                if d <= L:
                    fuel[i][j] = 1

    for k in range(N):
        for i in range(N):
            for j in range(N):
                fuel[i][j] = min(fuel[i][j], fuel[i][k] + fuel[k][j])

    for start, end in ST:
        print(fuel[start - 1][end - 1] - 1 if fuel[start - 1][end - 1] != INF else -1)

sol()

### FIXED CODE ###

import sys
input = sys.stdin.readline
INF = float('inf')

N, M, L = map(int, input().split())
ABC = [tuple(map(int, input().split())) for _ in range(M)]
Q = int(input())
ST = [tuple(map(int, input().split())) for _ in range(Q)]

dist = [[INF] * N for _ in range(N)]
fuel = [[INF] * N for _ in range(N)]

for i in range(N):
    dist[i][i] = 0
    fuel[i][i] = 0

for fr, to, cost in ABC:
    if cost > L:
        continue
    fr -= 1
    to -= 1
    dist[fr][to] = cost
    dist[to][fr] = cost

for k in range(N):
    for i in range(N):
        for j in range(N):
            d = dist[i][k] + dist[k][j]
            if dist[i][j] > d:
                dist[i][j] = d
            if d <= L:
                fuel[i][j] = 1

for k in range(N):
    for i in range(N):
        for j in range(N):
            d = fuel[i][k] + fuel[k][j]
            if fuel[i][j] > d:
                fuel[i][j] = d

for start, end in ST:
    print(fuel[start - 1][end - 1] - 1 if fuel[start - 1][end - 1] != INF else -1)
### BUGGY CODE ###

import sys
sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))
def resolve():
    N, P = lr()
    S = sr()
    if P == 2 or P == 5:
        ans = 0
        for i in range(N):
            if int(S[i])%P == 0:
                ans += i+1
        print(ans)
        return
    lp = [0]*P
    for i in range(N):
        lp[int(S[i:])%P] += 1
    MOD = 10**9+7
    SIZE = 2*10**5+1
    inv = [0]*SIZE  # inv[j] = j^{-1} mod MOD
    fac = [0]*SIZE  # fac[j] = j! mod MOD
    finv = [0]*SIZE # finv[j] = (j!)^{-1} mod MOD
    inv[1] = 1
    fac[0] = fac[1] = 1
    finv[0] = finv[1] = 1
    for i in range(2,SIZE):
        inv[i] = MOD - (MOD//i)*inv[MOD%i]%MOD
        fac[i] = fac[i-1]*i%MOD
        finv[i]= finv[i-1]*inv[i]%MOD
    
    def choose(n,r): # nCk mod MOD の計算
        if 0 <= r <= n:
            return (fac[n]*finv[r]%MOD)*finv[n-r]%MOD
        else:
            return 0
    ans = lp[0]
    for i in range(P):
        ans += choose(lp[i], 2)
    print(ans)
resolve()

### FIXED CODE ###

import sys
sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))
def resolve():
    N, P = lr()
    S = list(map(int, list(sr())))
    if P == 2 or P == 5:
        ans = 0
        for i in range(N):
            if S[i]%P == 0:
                ans += i+1
        print(ans)
        return
    S = S[::-1]
    lp = [0]*P
    c = 0
    for i in range(N):
        d = S[i]*pow(10,i,P)
        c = (c+d)%P
        lp[c] += 1
    ans = lp[0]
    for i in range(P):
        ans += lp[i]*(lp[i]-1)//2
    print(ans)
resolve()
### BUGGY CODE ###

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

ABs = []
best = (0, 0)
dp = [2**32] * (H + 1)
dp[0] = 0
for i in range(N):
    A, B = list(map(int, input().split()))
    ABs.append((A, B))


for j in range(H + 1):
    for A, B in ABs:
        next = min(H, j + A)
        dp[next] = min(dp[next], dp[j] + B)

print(dp[H])


### FIXED CODE ###

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

inf = 2**30
dp = [inf] * (H + 1)
dp[0] = 0
for i in range(N):
    A, B = list(map(int, input().split()))
    for j in range(H + 1):
        if dp[j] != inf:
            next = min(H, j + A)
            dp[next] = min(dp[next], dp[j] + B)

print(dp[H])
### BUGGY CODE ###

N = int(input())

s = []
for i in range(N):
    s.append(sorted(input()))

c = [s[i+1:].count(elm) for i, elm in enumerate(s)]
    

print(sum(c))


### FIXED CODE ###

N = int(input())

s = ["".join(sorted(input())) for i in range(N)]

count = 0
d = {}
for elm in s:
    if elm in d:
        count += d[elm]
        d[elm] += 1
    else:
        d[elm] = 1

print(count)
### BUGGY CODE ###

mod = int(1e9+7)

fac = [1]

def add(a, b):
    c = a + b
    if c >= mod:
        c -= mod
    return c

def subtract(a, b):
    return (a - b) % mod

def mul(a, b):
    return (a * b) % mod

def my_pow(a, b):
    if b == 0:
        return 1
    if b % 2 == 1:
        return mul(a, my_pow(a, b-1))
    else:
        temp = my_pow(a, b/2)
        return temp * temp
    
def my_inv(a):
    return my_pow(a, mod-2)

def nCk(n, k):
    if k > n:
        return 0
    #print(fac[n])
    #print(my_inv(mul(fac[n-k], fac[k])))
    return mul(fac[n], my_inv(mul(fac[n-k], fac[k])))

def main():
    n, k = [int(x) for x in raw_input().split()]
    
    a = [int(x) for x in raw_input().split()]
    
    for i in range(1, 2*n+1):
        fac.append(fac[-1] * i)
    
    
    a.sort()
    
    ans = 0
    
    for i in range(n-1):
        #print(a[i])
        diff = subtract(a[i+1], a[i])
        ways = nCk(n, k)
        #print(ways)
        ways = subtract(ways, nCk(i+1, k))
        ways = subtract(ways, nCk(n-i-1, k))
        ans = add(ans, mul(diff, ways))
    
    print(ans)
    

main()

### FIXED CODE ###

mod = int(1e9+7)

fac = [1]

def add(a, b):
    c = a + b
    if c >= mod:
        c -= mod
    return c

def subtract(a, b):
    return (a - b) % mod

def mul(a, b):
    return (a * b) % mod

def my_pow(a, b):
    if b == 0:
        return 1
    if b % 2 == 1:
        return mul(a, my_pow(a, b-1))
    else:
        temp = my_pow(a, b/2)
        return temp * temp
    
def my_inv(a):
    return my_pow(a, mod-2)

def nCk(n, k, fac):
    if k > n:
        return 0
    #print(fac[n])
    #print(my_inv(mul(fac[n-k], fac[k])))
    return mul(fac[n], my_inv(mul(fac[n-k], fac[k])))

def main():
    n, k = [int(x) for x in raw_input().split()]
    
    a = [int(x) for x in raw_input().split()]
    
    fac = [0] * (n+5)
    
    #print(fac)
    
    fac[0] = 1
    
    for i in range(1, n+5):
        fac[i] = mul(fac[i-1], i)
    
    a.sort()
    
    ans = 0
    
    for i in range(n-1):
        #print(a[i])
        diff = subtract(a[i+1], a[i])
        ways = nCk(n, k, fac)
        #print(ways)
        ways = subtract(ways, nCk(i+1, k, fac))
        ways = subtract(ways, nCk(n-i-1, k, fac))
        ans = add(ans, mul(diff, ways))
    
    print(ans)
    

main()
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**6)
input = sys.stdin.readline

n = int(input())

A = [0]*n
for i in range(n):
    a = list(map(int, input().split()))
    a = [a_-1 for a_ in a]
    A[i] = a

g = [[] for i in range(n*(n-1)//2)]
id = [[[-1] for i in range(n)] for j in range(n)]

temp = 0
for i in range(n-1):
    for j in range(i+1, n):
        id[i][j] = temp
        id[j][i] = temp
        temp += 1

for i in range(n):
    for j in range(n-2):
        g[id[i][A[i][j]]].append(id[i][A[i][j+1]])

visit = [-1]*(n*(n-1)*2)
clc = [-1]*(n*(n-1)*2)
dp = [1]*(n*(n-1)*2)
def dfs(v):
    if visit[v] != -1:
        if clc[v] == -1:
            return -1
        return dp[v]
    visit[v] = 0
    for u in g[v]:
        res = dfs(u)
        if res == -1:
            return -1
        dp[v] = max(dp[v], res+1)
    clc[v] = 0
    return dp[v]

ans = 0
for i in range(n*(n-1)//2):
    res = dfs(i)
    if res == -1:
        print(-1)
        exit()
    ans = max(ans, res)
print(ans)

### FIXED CODE ###

import sys
sys.setrecursionlimit(10**6)
input = sys.stdin.readline

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

    A = [0]*n
    for i in range(n):
        a = list(map(int, input().split()))
        a = [a_-1 for a_ in a]
        A[i] = a

    g = [[] for i in range(n*(n-1)//2)]
    id = [[[-1] for i in range(n)] for j in range(n)]

    temp = 0
    for i in range(n-1):
        for j in range(i+1, n):
            id[i][j] = temp
            id[j][i] = temp
            temp += 1

    for i in range(n):
        for j in range(n-2):
            g[id[i][A[i][j]]].append(id[i][A[i][j+1]])

    visit = [-1]*(n*(n-1)*2)
    clc = [-1]*(n*(n-1)*2)
    dp = [1]*(n*(n-1)*2)
    def dfs(v):
        if visit[v] != -1:
            if clc[v] == -1:
                return -1
            return dp[v]
        visit[v] = 0
        for u in g[v]:
            res = dfs(u)
            if res == -1:
                return -1
            dp[v] = max(dp[v], res+1)
        clc[v] = 0
        return dp[v]

    ans = 0
    for i in range(n*(n-1)//2):
        res = dfs(i)
        if res == -1:
            print(-1)
            exit()
        ans = max(ans, res)
    print(ans)

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

import numpy as np

def receive_shopping_plan():
    num_commodity, num_coupon = input().split(' ')
    num_commodity, num_coupon = int(num_commodity), int(num_coupon)
    return num_commodity, num_coupon

def calc_minimized_sum(num_commodity, num_coupon):
    prices = np.array(input().split(' '), dtype='i')
        # for _ in range(num_coupon):
        #     prices[prices.argmax()] //= 2
    [np.put(prices, prices.argmax(), prices.max()//2) for _ in range(num_coupon)]
    print(prices.sum())

if __name__ == '__main__':
    num_commodity, num_coupon = receive_shopping_plan()
    calc_minimized_sum(num_commodity, num_coupon)


### FIXED CODE ###

import heapq

def receive_shopping_plan():
    num_commodity, num_coupon = input().split(' ')
    num_commodity, num_coupon = int(num_commodity), int(num_coupon)
    return num_commodity, num_coupon

def calc_minimized_sum(num_commodity, num_coupon):
    prices = list(map(lambda x: int(x) * -1 , input().split(' ')))
    heapq.heapify(prices)
    for _ in range(num_coupon):
        max_price = heapq.heappop(prices) // (2*-1)
        heapq.heappush(prices, max_price*-1)

    print(sum(prices)*-1)

if __name__ == '__main__':
    num_commodity, num_coupon = receive_shopping_plan()
    calc_minimized_sum(num_commodity, num_coupon)
### BUGGY CODE ###

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

ans = [0] * n

for i in range(1, n):
    l = min(i, k)
    hs = h[i]
    ans[i] = min([abs(hs - h[i - j])+ans[i-j] for j in range(1, l+1)])
    # j : 戻り幅
#print(ans)
print(ans[-1])

### FIXED CODE ###

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

ans = [0] * n

for i in range(1, n):
    l = min(i, k)
    hs = h[i]
    ans[i] = min([abs(hs - h[i - j])+ans[i-j] for j in range(1, l+1)])
    # j : 戻り幅
#print(ans)
print(ans[-1])
### BUGGY CODE ###

N = int(input())
word = [input() for i in range(N)]
sorted_word = tuple(tuple(sorted(list(word[i]))) for i in range(N))
dict_word = {sorted_word[i]:0 for i in range(N)}
ans = 0


for i in range(N):
  if sorted_word[i] in sorted_word[i+1:]:
    dict_word[sorted_word[i]] += 1
    
for value in dict_word.values():
  ans += int((1+value) * value / 2)
  
print(ans)


### FIXED CODE ###

N = int(input())
ans = 0
dict_word = {}
for i in range(N):
  sorted_word = str(''.join(sorted(list(input()))))
  try:
    ans += dict_word[sorted_word]
    dict_word[sorted_word] += 1
  except:
    dict_word[sorted_word] = 1
print(ans)
### BUGGY CODE ###

s=list(map(int,list(input())[::-1]))
n=len(s)
cnt=[0]*(n+1)
cnt[0]=s[0]%2019
c=s[0]
for i in range(1,n):
  c+=s[i]*(10**i)%2019
  cnt[i]=c%2019
d={}
for i in cnt:
  if i in d:
    d[i]+=1
  else:
    d[i]=1
ans=0
for i in d.values():
  ans+=i*(i-1)//2
print(ans)

### FIXED CODE ###

s=list(map(int,list(input())[::-1]))
n=len(s)
cnt=[0]*2019
cnt[0]+=1
c=0
for i in range(n):
  c+=s[i]*pow(10,i,2019)%2019
  cnt[c%2019]+=1
ans=0
for i in cnt:
  if i<=1:
    pass
  else:
    ans+=i*(i-1)//2
print(ans)
### BUGGY CODE ###

import numpy as np

N = int(input())
nums = np.array([int(input()) for _ in range(N)])


for i in range(N):
    indices = np.ones(N, dtype=bool)
    indices[i] = False
    print(np.amax(nums[indices]))

### FIXED CODE ###

import numpy as np

N = int(input())
nums = np.array([int(input()) for _ in range(N)])

# 最も大きな値を調べる
sorted_nums = sorted(nums, reverse=True)
max_num = sorted_nums[0]
# 2番目に大きな値を調べる
second_max_num = sorted_nums[1]

for i in range(N):
    # 除外する値を取得する
    exclude_num = nums[i]
    # 除外する値が最大値なら2番目の値を表示する
    if exclude_num == max_num:
        print(second_max_num)
    # それ以外なら最大値を表示する
    else:
        print(max_num)
### BUGGY CODE ###

R,G,B,N = map(int,input().split())
ans = 0
for r in range(N+1):
  if r*R>N:
    break
  for g in range(N+1):
    if r*R+g*G>N:
      break
    if (N-r*R-g*G)%B==0:
      ans+=1
print(ans)

### FIXED CODE ###

R,G,B,N = map(int,input().split())
ans = 0
for r in range(N+1):
  if r*R>N:
    break
  for g in range(N+1):
    S = N-r*R-g*G
    if S<0:
      break
    elif S%B==0:
      ans+=1
print(ans)
### BUGGY CODE ###

import sys
H,W,M=map(int, input().split())
h=[]
w=[]
Hcount=[0 for _ in range(H)]
Wcount=[0 for _ in range(W)]
B = [[0 for i in range(W)] for j in range(H)] ##掛け算で書いてはいけない

for i in range(M):
    hi,wi=map(int, input().split())
    h.append(hi)
    w.append(wi)
    Hcount[hi-1]+=1
    Wcount[wi-1]+=1
    B[hi-1][wi-1]=1
h_max=[i for i, v in enumerate(Hcount) if v == max(Hcount)]
w_max=[i for i, v in enumerate(Wcount) if v == max(Wcount)]
#print(h_max,w_max)
for ii in range(len(h_max)):
    for jj in range(len(w_max)):
        if B[h_max[ii]][w_max[jj]]==0:
            print(max(Hcount)+max(Wcount))
            sys.exit()
print(max(Hcount)+max(Wcount)-1)
'''for ii in range(len(h_max)):
    for jj in range(len(w_max)):
        h_cand=[k for k, v in enumerate(h) if v == h_max[ii]+1]
        w_cand=[l for l, v in enumerate(w) if v == w_max[jj]+1]
        h_set = set(h_cand)
        w_set = set(w_cand)
        matched_list = list(h_set & w_set)
        #print(h_cand,w_cand)
        #print(matched_list)
        if len(matched_list)==0:
            print(max(Hcount)+max(Wcount))
            sys.exit()
print(max(Hcount)+max(Wcount)-1)
'''


### FIXED CODE ###

import sys
 
input = sys.stdin.readline
 
 
def main():
    H, W, M = map(int, input().split())
    row = [0] * (H)
    col = [0] * (W)
    bomb = set()
    for _ in range(M):
        h, w = map(int, input().split())
        bomb.add((h, w))
        row[h-1] += 1
        col[w-1] += 1
    row_max = max(row)
    row_index_list = [i for i, v in enumerate(row) if v == row_max]
    col_max = max(col)
    col_index_list = [i for i, v in enumerate(col) if v == col_max]
    ans = row_max + col_max - 1
    c = False
    for x in row_index_list:
        for y in col_index_list:
            if not (x + 1, y + 1) in bomb:
                c = True
                break
        if c:
            break
    if c:
        ans += 1
    print(ans)
 
 
if __name__ == '__main__':
    main()
### BUGGY CODE ###

import math
 
d,g = [int(i) for i in input().split()]
P = []
C = []
for i in range(d):
    p,c = [int(i) for i in input().split()]
    P.append(p)
    C.append(c)
 
m = 10**9
def score(point = 0, n = 0, now=-1, done=[]):
    global m
    if point >= g:
        if m > n: m = n
    elif point+100*(now+1)*P[now] >= g:
        n += math.ceil((g-point)/(100*(now+1)))
        if m > n: m = n
    else:
        done.append(now)
        if now == -1:
            for i in range(d):
                score(point, n, i, done[:])
        else:
            for i in range(d):
                if not i in done:
                    score(point+P[now]*100*(now+1) + C[now], n + P[now], i, done[:])

score()
print(m)

### FIXED CODE ###

import math
 
d,g = [int(i) for i in input().split()]
P = []
C = []
for i in range(d):
    p,c = [int(i) for i in input().split()]
    P.append(p)
    C.append(c)

# cnt = 0
# def count():
#     global cnt
#     cnt+=1
#     print(cnt)

def flag(point,P,now):
    if point+100*(now+1)*(P-1) >= g: return 1
    elif point+100*(now+1)*P + C[now] >= g: return 2
    else: return 0

m = 10**9
def score(point = 0, n = 0, now=-1, remain = list(range(d))):
    global m
    if m <= n: return
    elif now == -1:
        for i in remain:
            score(point, n, i, remain)
    elif point >= g: m = n
    elif flag(point,P[now],now) == 1:
        n += math.ceil((g-point)/(100*(now+1)))
        if m > n: m = n
    elif flag(point,P[now],now) == 2:
        n += P[now]
        if m > n: m = n
    else:
        if m <= n+P[now]: return
        else:
            remain = remain[:]
            remain.remove(now)
            nxtp = point + P[now]*100*(now+1) + C[now]
            for i in remain:
                score(nxtp, n + P[now], i, remain)

score()
print(m)
### BUGGY CODE ###

from itertools import combinations

N = int(input())
A = [int(height) for height in input().split()]

res = 0

for i in range(N - 1):
    a1_height = A[i]
    j = a1_height + i + 1
    for a2_height in A[j:]:
        if abs((i + 1) - (j + 1)) == (a1_height + a2_height):
            res += 1
        j += 1

print(res)


### FIXED CODE ###

from collections import Counter

N = int(input())
A = [int(height) for height in input().split()]

m = Counter(i - elem for i, elem in enumerate(A))
res = 0
for i, elem in enumerate(A):
    res += m[i + elem]

print(res)
### BUGGY CODE ###

K, S = [int(num) for num in input().split()]

count = 0

for x in range(K+1):
    for y in range(K+1):
        for z in range(K+1):

            if x + y + z == S:
                count += 1

print(count)


### FIXED CODE ###

K, S = [int(num) for num in input().split()]

count = 0

for x in range(K+1):
    for y in range(K+1):
        z = S - x - y
        if 0 <= z <= K:
            count += 1

print(count)
### BUGGY CODE ###

N = int(input())
for i in range(1,10000000000):
    if i%2 == 0 and i%N == 0:
        print(i)
        break

### FIXED CODE ###

N = int(input())
 
if N % 2 == 0:
  print(N)
else:
  print(2 * N)
### BUGGY CODE ###

import math


def pattern(x, y, z):
    if x == y == z:
        return 1
    elif x != y and y != z and x != z:
        return 6
    else:
        return 3


def check(ans):
    cnt = 0
    for x in range(1, ans):
        if pow(x, 2) > ans:
            break
        for y in range(x, ans):
            if pow(x+y, 2) > ans:
                break
            for z in range(y, ans):
                tmp = x*(x+y+z) + y*(y+z) + z*z
                if tmp == ans:
                    cnt += pattern(x, y, z)
                elif tmp > ans:
                    break
    print(cnt)


N = int(input())
# x^2 + y^2 + z^2 + x*y + y*z + z*x = n

for i in range(1, N+1):
    #upper_value = int(math.sqrt(i))
    check(i)


### FIXED CODE ###

import math


def pattern(x, y, z):
    if x == y == z:
        return 1
    elif x != y and y != z and x != z:
        return 6
    else:
        return 3


def check(ans):
    cnt = 0
    upper = int(math.sqrt(ans))
    for x in range(1, upper):
        if pow(x, 2) > ans:
            break
        for y in range(x, upper):
            if pow(x+y, 2) > ans:
                break
            for z in range(y, upper):
                tmp = x*(x+y+z) + y*(y+z) + z*z
                # tmp = pow(x+y+z, 2) - x*(y+z) - y*z
                if tmp == ans:
                    cnt += pattern(x, y, z)
                    if x == y and y == z and z == x:
                        print(cnt)
                        return
                elif tmp > ans:
                    break
    print(cnt)


N = int(input())
# x^2 + y^2 + z^2 + x*y + y*z + z*x = n

for i in range(1, N+1):
    # upper_value = int(math.sqrt(i))
    check(i)
### BUGGY CODE ###

D, G = map(int, input().split())
p = [list(map(int, input().split())) for _ in range(D)]
plst = [0] * D
ans = 0
for i in range(D):
    ans += p[i][0]

def dfs(n):
    global ans
    if n == D:
        cnt = 0
        total = 0
        for i in range(D):
            if plst[i] == 0:
                continue
            elif plst[i] == 1:
                cnt += p[i][0]
                total += (100 * (i + 1) * p[i][0]) + p[i][1]
        for j in range(D):
            if plst[j] == 2:
                for k in range(p[j][0] - 1):
                    total += (100 * (j + 1))
                    cnt += 1
                    if total >= G:
                        ans = min(ans, cnt)
        if total >= G:
            ans = min(ans, cnt)
        return

    for i in range(3):
        plst[n] = i
        dfs(n + 1)
    return

dfs(0)
print(ans)

### FIXED CODE ###

D, G = map(int, input().split())
p = [list(map(int, input().split())) for _ in range(D)]
plst = [0] * D
ans = 0
for i in range(D):
    ans += p[i][0]

def dfs(n):
    global ans
    if n == D:
        cnt = 0
        total = 0
        for i in range(D):
            if plst[i] == 0:
                continue
            elif plst[i] == 1:
                cnt += p[i][0]
                total += (100 * (i + 1) * p[i][0]) + p[i][1]
        for j in range(D):
            if plst[j] == 2:
                for k in range(p[j][0] - 1):
                    total += (100 * (j + 1))
                    cnt += 1
                    if total >= G:
                        ans = min(ans, cnt)
        if total >= G:
            ans = min(ans, cnt)
        return

    for i in range(3):
        plst[n] = i
        dfs(n + 1)
    return

dfs(0)
print(ans)
### BUGGY CODE ###

# -*- coding: utf-8

n, x = map(int, input().split())
a = list(map(int, input().split()))
count = 0

if a[0] > x:
    count += a[0] - x
    a[0] = x


for i in range(len(a) - 1):

    while a[i] + a[i + 1] > x:
        a[i + 1] -= 1
        count += 1
print(count)


### FIXED CODE ###

# -*- coding: utf-8

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

count = max(0, a[0] - x)
a[0] = min(a[0], x)

for i in range(len(a) - 1):
    if a[i] + a[i + 1] > x:
        tmp_num = max(0, a[i] + a[i + 1] - x)
        count += tmp_num
        a[i + 1] -= tmp_num
print(count)
### BUGGY CODE ###

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


def Cum(X):
    temp = 0
    Cum = [0]*len(X)
    for i in range(len(X)):
        temp += X[i]
        Cum[i] += temp
    return Cum

a = Cum(A)
a.insert(0,0)
b = Cum(B)
b.insert(0,0)


def f(X,x,target):
    return X[x]-target

def nibutan(X):
    num = list(range(len(X)))
    lo = 0
    hi = len(X)
    while hi-lo>=2:
        mid = (lo+hi)//2
        if f(X,mid,Y)<=0:
            lo = mid
        else:
            hi = mid
    return lo

ans = 0
for i in range(N+1):
    if K-a[i]>=0:
        Y = K-a[i]
        ans = max(nibutan(b)+i,ans)
    else:
        break
print(ans)

### FIXED CODE ###

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


def Cum(X):
    temp = 0
    Cum = [0]*len(X)
    for i in range(len(X)):
        temp += X[i]
        Cum[i] += temp
    return Cum

a = Cum(A)
a.insert(0,0)
b = Cum(B)
b.insert(0,0)

na = 0
for i in range(N+1):
    if i == N and a[i]<=K:
        na = N
    elif a[i]<=K and a[i+1]>K:
        na = i

ans = na

nb = 0
for i in range(na,-1,-1):
    temp = K-a[i]
    for j in range(nb,M+1):
        if j == M and b[j] <= temp:
            nb = M
            ans = max(ans,i+nb)
        elif b[j]<=temp and b[j+1]>temp:
            nb = j
            ans = max(ans,i+nb)
            break
        
print(ans)