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

# "#"と"."だけで行き来できるエリアを"島"とする
# 島にある"#"から"."には必ず行けるので、
# "#"の数 * "."がその島の場合の数。これをすべて足し合わせる

# visitedになっていない点をすべて捜査する。
# 進めなかった（"#"もしくは"."が連続した）マスはvisitedにしない。

H,W = map(int,input().split())
grid = [None] * H
for i in range(H):
  grid[i] = input()
  
visited = [[False] * W for i in range(H)]

def get_next_unvisited(checked_y):
  for i in range(checked_y,H):
    for j in range(W):
      if not visited[i][j]:
        return i,j
  return -1,-1 # 候補なし
  
from collections import deque
ans = 0
cases = ((0,1),(0,-1),(1,0),(-1,0))
checked_y = 0
while True:
  y,x = get_next_unvisited(checked_y)
  if y == -1 and x == -1:
    print(ans)
    exit(0)
  checked_y = y
  # y,x,親,親マスの文字
  q = deque([[y,x,-1,-1,"N"]])
  black = 0
  white = 0
  
  while q:
    y,x,parent_y,parent_x,parent = q.popleft()
    if visited[y][x]:
      continue
    point = grid[y][x]
    if point == parent:
      continue
    visited[y][x] = True
    if point == "#":
      black += 1
    if point == ".":
      white += 1
    for c in cases:
      if y + c[0] == parent_y and x + c[1] == parent_x:
        continue
      if 0 <= y + c[0] < H and 0 <= x + c[1] < W:
        q.append([y + c[0],x + c[1],y,x, point])
  ans += black * white


### FIXED CODE ###

# "#"と"."だけで行き来できるエリアを"島"とする
# 島にある"#"から"."には必ず行けるので、
# "#"の数 * "."がその島の場合の数。これをすべて足し合わせる

# visitedになっていない点をすべて捜査する。
# 進めなかった（"#"もしくは"."が連続した）マスはvisitedにしない。

H,W = map(int,input().split())
grid = [None] * H
for i in range(H):
  grid[i] = input()
  
visited = [[False] * W for i in range(H)]

def get_next_unvisited(checked_y):
  for i in range(checked_y,H):
    for j in range(W):
      if not visited[i][j]:
        return i,j
  return -1,-1 # 候補なし
  
from collections import deque
ans = 0
cases = ((0,1),(0,-1),(1,0),(-1,0))
checked_y = 0
while True:
  y,x = get_next_unvisited(checked_y)
  if y == -1 and x == -1:
    print(ans)
    exit(0)
  checked_y = y
  # y,x,親,親マスの文字
  q = deque([[y,x,-1,-1,"N"]])
  black = 0
  white = 0
  
  while q:
    y,x,parent_y,parent_x,parent = q.pop()
    if visited[y][x]:
      continue
    point = grid[y][x]
    if point == parent:
      continue
    visited[y][x] = True
    if point == "#":
      black += 1
    if point == ".":
      white += 1
    for c in cases:
      if y + c[0] == parent_y and x + c[1] == parent_x:
        continue
      if 0 <= y + c[0] < H and 0 <= x + c[1] < W:
        q.append([y + c[0],x + c[1],y,x, point])
  ans += black * white
### BUGGY CODE ###

def small(a, b):
    if a > b:
        return b
    else:
        return a


def main():
    n, k = map(int, input().split())
    h = list(map(int, input().split()))
    INF = 10 ** 9
    dp = [INF] * n
    dp[0] = 0
    for i in range(n):
        for j in range(1, k + 1):
            if i + j < n:
                dp[i + j] = small(dp[i + j], dp[i] + abs(h[i] - h[i + j]))
    print(dp[-1])


if __name__ == "__main__":
    main()

### FIXED CODE ###

def main():
    n, k = map(int, input().split())
    h = tuple(map(int, input().split()))
    INF = 10 ** 9
    dp = [INF] * n
    dp[0] = 0
    for i in range(n):
        for j in range(1, k + 1):
            i_j = i + j
            if i_j < n:
                x = dp[i] + abs(h[i] - h[i_j])
                if dp[i_j] > x:
                    dp[i_j] = x
    print(dp[-1])


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

import itertools
N,K = map(int,input().split())
zahyou = []
for i in range(N):
  zahyou.append(list(map(int,input().split())))
ans = float('inf')
X = []
Y = []
for i in range(N):
  X.append(zahyou[i][0])
  Y.append(zahyou[i][1])
P = list(itertools.combinations(X,2))
Q = list(itertools.combinations(Y,2))
for i in range(len(P)):
  for j in range(len(Q)):
    x1 = min(P[i][0],P[i][1])
    x2 = max(P[i][0],P[i][1])
    y1 = min(Q[j][0],Q[j][1])
    y2 = max(Q[j][0],Q[j][1])
    cnt = 0
    for k in range(N):
      if x1 <= zahyou[k][0] <= x2 and y1 <= zahyou[k][1] <= y2:
        cnt += 1
    if cnt >= K:
      if ans >= (x2-x1)*(y2-y1):
        ans = (x2-x1)*(y2-y1)
print(ans)

### FIXED CODE ###

import itertools
N,K = map(int,input().split())
zahyou = []
for i in range(N):
  zahyou.append(list(map(int,input().split())))
ans = float('inf')
X = []
Y = []
for i in range(N):
  X.append(zahyou[i][0])
  Y.append(zahyou[i][1])
P = list(itertools.combinations(X,2))
Q = list(itertools.combinations(Y,2))
for i in range(len(P)):
  for j in range(len(Q)):
    x1 = min(P[i][0],P[i][1])
    x2 = max(P[i][0],P[i][1])
    y1 = min(Q[j][0],Q[j][1])
    y2 = max(Q[j][0],Q[j][1])
    cnt = 0
    for k in range(N):
      if x1 <= zahyou[k][0] <= x2 and y1 <= zahyou[k][1] <= y2:
        cnt += 1
    if cnt >= K:
      if ans >= (x2-x1)*(y2-y1):
        ans = (x2-x1)*(y2-y1)
print(ans)
### BUGGY CODE ###

import sys
input = sys.stdin.readline
N,M=map(int,input().split())
A=[int(i) for i in input().split()]
B=[0]*M
C=[0]*M
for i in range(M):
    B[i],C[i]=[int(x) for x in input().split()]
import heapq
heap = []
for value in A:
    heapq.heappush(heap, value)
for i in range(M):
    for j in range(B[i]):
        if heap[0] < C[i]:
            heapq.heappop(heap)
            heapq.heappush(heap, C[i])
            #print(heap)
        else:
            break
print(sum(heap))

### FIXED CODE ###

import sys
import bisect
import numpy as np
#input = sys.stdin.readline
N,M=map(int,input().split())
A=[int(i) for i in input().split()]
B=[0]*M
C=[0]*M
for i in range(M):
    B[i],C[i]=[int(x) for x in input().split()]
matrix = np.vstack((np.array(B),np.array(C)))
matrix = matrix[:, np.argsort(-matrix[1])]
list2=np.zeros(N)
i=0
for b,c in zip(matrix[0],matrix[1]):
    i += b
    #print(i-b,b)
    if i < N:
        list2[i-b:i] = c
        #print(list2)
    else: 
        list2[i-b:]=c
        #print(list2)
A.extend(list(list2))
A.sort()
print(int(sum(A[N:])))
### BUGGY CODE ###

import copy,bisect

s=input()
N=len(s)
t=input()
M=len(t)

alphabetlist=['a','b','c','d','e','f','g','h','i','j','k','l','m','n','o','p','q','r','s','t','u','v','w','x','y','z']

index={moji:[] for moji in alphabetlist}
for i in range(N):
    index[s[i]].append(i)

dp=['' for i in range(0,N)]

for i in range(0,N):
    if index[t[0]]:
        if i>=index[t[0]][0]:
            dp[i]=t[0]

for i in range(1,M):
    x=t[i]
    if index[x]:
        for j in range(N-1,index[x][0]-1,-1):
            next=index[x][bisect.bisect_right(index[x],j)-1]-1
            if next>=0:
                if len(dp[j])<1+len(dp[next]):
                    dp[j]=dp[next]+t[i]
            else:
                if dp[j]=='':
                    dp[j]=t[i]

print(dp[N-1])


### FIXED CODE ###

s=input()
N=len(s)
t=input()
M=len(t)

alphabetlist=['a','b','c','d','e','f','g','h','i','j','k','l','m','n','o','p','q','r','s','t','u','v','w','x','y','z']
def al(str):
    return alphabetlist.index(str)+1

dp=[[0 for i in range(0,M+1)] for i in range(0,N+1)]

for i in range(0,N):
    for j in range(0,M):
        if s[i]==t[j]:
            dp[i+1][j+1]=dp[i][j]+1
        else:
            if dp[i+1][j]>dp[i][j+1]:
                dp[i+1][j+1]=dp[i+1][j]
            else:
                dp[i+1][j+1]=dp[i][j+1]

ans=[]
i=N
j=M
while i>0 and j>0:
    if dp[i][j]==dp[i-1][j]:
        i-=1
    elif dp[i][j]==dp[i][j-1]:
        j-=1
    else:
        ans.append(s[i-1])
        i-=1
        j-=1

ans=ans[::-1]
print(''.join(ans))
### BUGGY CODE ###

import sys

input = sys.stdin.readline


def dot(a, b):
    an = len(a)
    bn = len(b[0])
    c = [[0] * bn for _ in range(an)]
    for i in range(an):
        ai = a[i]
        for j in range(bn):
            ck = 0
            for ak, bk in zip(ai, [bi[j] for bi in b]):
                ck += ak * bk
                c[i][j] = ck % md
    return c


def pwr(a, k):
    c = None
    while c == None:
        if k & 1:
            c = a
        a = dot(a, a)
        k >>= 1

    while k > 0:
        if k & 1:
            c = dot(a, c)
        a = dot(a, a)
        k >>= 1
    return c


md = 10 ** 9 + 7
n, k = map(int, input().split())
a = [list(map(int, input().split())) for _ in range(n)]
e = [[1] * n]
print(sum(dot(e, pwr(a, k))[0]) % md)


### FIXED CODE ###

import sys

input = sys.stdin.readline


def dot(a, b):
    c = [[0] * n for _ in range(n)]
    for i, ai in enumerate(a):
        for j, bj in enumerate(zip(*b)):
            c[i][j] = sum(ak * bk for ak, bk in zip(ai, bj)) % md
    return c


def pwr(a, k):
    c = None
    while c == None:
        if k & 1:
            c = a
        a = dot(a, a)
        k >>= 1

    while k > 0:
        if k & 1:
            c = dot(a, c)
        a = dot(a, a)
        k >>= 1
    return c


md = 10 ** 9 + 7
n, k = map(int, input().split())
a = [list(map(int, input().split())) for _ in range(n)]
print(sum([sum(pk) % md for pk in pwr(a, k)]) % md)
### BUGGY CODE ###

import sys

stdin = sys.stdin


def ni(): return int(ns())


def na(): return list(map(int, stdin.readline().split()))


def naa(N): return [na() for _ in range(N)]


def ns(): return stdin.readline().rstrip()  # ignore trailing spaces


H, W = na()
A_array = naa(H)
B_array = naa(H)
C_array = [[abs(aa-bb) for aa, bb in zip(a, b)]
           for a, b in zip(A_array, B_array)]
# print(C_array)

ans_array = [[set() for _ in range(W)] for _ in range(H)]

ans_array[0][0].add(C_array[0][0])

for i in range(H):
    for j in range(W):
        if i != 0:
            for s in ans_array[i-1][j]:
                ans_array[i][j].add(s + C_array[i][j])
                ans_array[i][j].add(s - C_array[i][j])
        if j != 0:
            for s in ans_array[i][j-1]:
                ans_array[i][j].add(s + C_array[i][j])
                ans_array[i][j].add(s - C_array[i][j])

# print(ans_array)

ans = 10 ** 9
for s in ans_array[H-1][W-1]:
    if abs(s) < ans:
        ans = abs(s)
print(ans)


### FIXED CODE ###

import sys

stdin = sys.stdin


def ni(): return int(ns())


def na(): return list(map(int, stdin.readline().split()))


def naa(N): return [na() for _ in range(N)]


def ns(): return stdin.readline().rstrip()  # ignore trailing spaces


H, W = na()
A_array = naa(H)
B_array = naa(H)
C_array = [[abs(aa-bb) for aa, bb in zip(a, b)]
           for a, b in zip(A_array, B_array)]
# print(C_array)

K = 6400

ans_array = [[[0] * (K+1) for _ in range(W)] for _ in range(H)]

ans_array[0][0][C_array[0][0]] = 1

for i in range(H):
    for j in range(W):
        if i != 0:
            for k in range(K+1):
                ans_array[i][j][k] = ans_array[i][j][k] | ((ans_array[i-1][j][abs(k+C_array[i][j])] if abs(
                    k+C_array[i][j]) <= K else 0) | ans_array[i-1][j][abs(k-C_array[i][j])])
        if j != 0:
            for k in range(K+1):
                ans_array[i][j][k] = ans_array[i][j][k] | ((ans_array[i][j-1][abs(k+C_array[i][j])] if abs(
                    k+C_array[i][j]) <= K else 0) | ans_array[i][j-1][abs(k-C_array[i][j])])

# print(ans_array)

for k in range(K+1):
    if ans_array[H-1][W-1][k] == 1:
        print(k)
        exit()
### BUGGY CODE ###

from copy import deepcopy
n = int(input())
s = input().rstrip()

def solve1(n, s):
    # 全探索
    cnt = 0
    for v in range(0, 1000):
        v = str(v)
        v = "0" * (3 - len(v)) + v
        idx = 0
        for i in range(len(s)):
            if s[i] == v[idx]:
                idx += 1
            if idx == 3:
                cnt += 1
                break
    print(cnt)

def solve2(n, s):
    # DP
    dp = [[[False for _ in range(1000)] for _ in range(4)] for _ in range(n+1)]
    dp[0][0][0] = True

    for i in range(n):
        for j in range(3):
            for k in range(100):
                if dp[i][j][k]:
                    num = k*10 + int(s[i])
                    dp[i+1][j+1][num] = True
        for j in range(4):
            for k in range(1000):
                dp[i+1][j][k] |= dp[i][j][k]

    cnt = 0
    for i in range(1000):
        if dp[n][3][i]:
            cnt += 1
    print(cnt)

solve2(n, s)

### FIXED CODE ###

n = int(input())
s = input().rstrip()

def solve(n, s):
    # 全探索
    cnt = 0
    for v in range(0, 1000):
        v = str(v)
        v = "0" * (3 - len(v)) + v
        idx = 0
        for i in range(len(s)):
            if s[i] == v[idx]:
                idx += 1
            if idx == 3:
                cnt += 1
                break
    print(cnt)
solve(n, s)
### BUGGY CODE ###

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

d1 = [[0]*60 for _ in range(N+1)]
mod = 10**9+7

for i, n in enumerate(A, start=1):
    for j in range(60):
        d1[i][j] = d1[i-1][j] + ((n>>j)&1)

ans = 0
for i, n in enumerate(A, start=1):
    for j in range(60):
        a = d1[N][j]-d1[i][j] # 1
        b = N-a-i # 0

        if n%2:
            ans += b*(2**j)
        else:
            ans += a*(2**j)
        ans %= mod
        n//=2

print(ans)

### FIXED CODE ###

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

d1 = [[0]*60 for _ in range(N+1)]
mod = 10**9+7

for i, n in enumerate(A, start=1):
    for j in range(60):
        d1[i][j] = d1[i-1][j] + ((n>>j)&1)

ans = 0
for i, n in enumerate(A, start=1):
    for j in range(60):
        a = d1[N][j]-d1[i][j] # 1
        if (n>>j)&1:
            a = N-a-i # 0

        ans += a*(1<<j)
    ans %= mod

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

from collections import deque
import sys
input = sys.stdin.readline

h, w = map(int, input().split())
a = [[j for j in input()] for i in range(h)]
# for i in range(h):
#     a[i] = list(input())

dx = [1, 0, -1, 0]
dy = [0, 1, 0, -1]

que = deque()

white = h * w

# スタート地点をqueueに追加
for i in range(h):
    for j in range(w):
        if a[i][j] == "#":
            que.append([i, j])
            white -= 1

count = 0
while 1:
    if white == 0:
        break
    count += 1
    loop = len(que)
    for i in range(loop):
        p = que.popleft()
        for j in range(4):
            ny = p[0] + dy[j]
            nx = p[1] + dx[j]
            if nx < w and nx >= 0 and ny < h and ny >= 0 and a[ny][nx] == ".":
                a[ny][nx] = "#"
                white -= 1
                que.append([ny, nx])


print(count)

### FIXED CODE ###

from collections import deque
h, w = map(int, input().split())
a = [[] for i in range(h)]
for i in range(h):
    a[i] = list(input())

dx = [1, 0, -1, 0]
dy = [0, 1, 0, -1]

que = deque()

white = h * w

# スタート地点をqueueに追加
for i in range(h):
    for j in range(w):
        if a[i][j] == "#":
            que.append([i, j])
            white -= 1

count = 0
while 1:
    if white == 0:
        break
    count += 1
    loop = len(que)
    for i in range(loop):
        p = que.popleft()
        for j in range(4):
            ny = p[0] + dy[j]
            nx = p[1] + dx[j]
            if nx < w and nx >= 0 and ny < h and ny >= 0 and a[ny][nx] == ".":
                a[ny][nx] = "#"
                white -= 1
                que.append([ny, nx])


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

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

    sum = 0
    for i in range(0, N - 1):
        for j in range(i + 1, N):
            sum += (A[i] * A[j])
        sum = sum % (10 ** 9 + 7)

    print(sum)


if __name__ == "__main__":
    main()


### FIXED CODE ###

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

    B = sum(A)
    answer = 0
    for i in range(0, N):
        answer += A[i] * (B - A[i])
        B -= A[i]

    answer %= (10 ** 9 + 7)

    print(answer)


if __name__ == "__main__":
    main()

# A1*A2 + A1*A3 + ... + A1*AN = A1 * (A2 + A3 + ... + AN)
# +
# A2*A3 + A2*A4 + ... +| A2*AN = A2 * (A3 + A4 + ... + AN)
### BUGGY CODE ###

import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10 ** 7)

h, n = map(int, readline().split())
ab = [list(map(int, readline().split())) for i in range(n)]
inf = float('inf')
dp = [inf] * (2 * 10 ** 4)
dp[0] = 0
for a, b in ab:
    for n in range(h):
        if dp[n + a] > dp[n] + b:
            dp[n + a] = dp[n] + b

ans = min(dp[h:])
print(ans)


### FIXED CODE ###

import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10 ** 7)

h, n = map(int, readline().split())
ab = [list(map(int, readline().split())) for i in range(n)]
inf = float('inf')
dp = [inf] * (2 * 10 ** 4)
dp[0] = 0
for a, b in ab:
    for n in range(h):
        if dp[n + a] > dp[n] + b:
            dp[n + a] = dp[n] + b

ans = min(dp[h:])
print(ans)
### BUGGY CODE ###

def jud(a,b):
    dic = ['a','b','c','d','e','f','g','h','i','j','k','l','m','n','o','p','q','r','s','t','u','v','w','x','y','z']
    if len(a) == 0:
        return 0
    if len(b) == 0:
        return 1
    if a[0] == b[0]:
        return jud(a[1:],b[1:])
    if dic.index(a[0]) > dic.index(b[0]):
        return 1
    if dic.index(a[0]) < dic.index(b[0]):
        return 0
def listint():
    a = input().split()
    for i in range(len(a)):
        a[i] = int(a[i])
    return a
def megsort(s):
    p = len(s)
    if p == 1:
        return s
    else:
        q = int(p/2)
        left = megsort(s[q:])
        right = megsort(s[:q])
        arr = []
        while len(left)*len(right) != 0:
            if jud(left[0],right[0]) == 1:
                arr.append(right.pop(0))
                
            else:
                arr.append(left.pop(0))
        if len(left) == 0:
            arr.extend(right)
        else:
            arr.extend(left)
        return arr
        

n = int(input())
s = []
for i in range(n):
    s.append(input())
s = megsort(s)
ans = 1
ansar = [s[0]]
now = 1
for i in range(len(s)-1):
    if s[i] == s[i+1]:
        now = now +1
    else:
        now = 1
    if now == ans:
        ansar.append(s[i+1])
    if now > ans:
        ans = now
        ansar = [s[i+1]]
for i in range(len(ansar)):
    print(ansar[i])

### FIXED CODE ###

n = int(input())
s = []
for i in range(n):
    s.append(input())
s.sort()
ans = 1
ansar = [s[0]]
now = 1
for i in range(len(s)-1):
    if s[i] == s[i+1]:
        now = now +1
    else:
        now = 1
    if now == ans:
        ansar.append(s[i+1])
    if now > ans:
        ans = now
        ansar = [s[i+1]]
for i in range(len(ansar)):
    print(ansar[i])
### BUGGY CODE ###

N = int(input())
S = list(input().strip())
Q = int(input())

for i in range(Q):
    q, a, b = map(str, input().split())
    if int(q) == 1:
        a = int(a) - 1
        S[a] = b
    if int(q) == 2:
        a = int(a) - 1
        b = int(b) - 1
        _set = set(S[a: b+1])
        print(len(_set))


### FIXED CODE ###

class SegmentTree:
    def __init__(self, data):
        # 単位元
        self.ide_ele = 0
        # num: n以上の最小の2のべき乗
        self.num = 2 ** (N - 1).bit_length()
        self.seg = [self.ide_ele] * 2 * self.num
        for i in range(N):
            self.seg[i + self.num - 1] = 1 << (ord(data[i]) - 97)
        for i in range(self.num - 2, -1, -1):
            self.seg[i] = self.seg[2 * i + 1] | self.seg[2 * i + 2]

    def update(self, k, x):
        k += self.num - 1
        self.seg[k] = 1 << (ord(x) - 97)
        while k:
            k = (k - 1) // 2
            self.seg[k] = self.seg[k * 2 + 1] | self.seg[k * 2 + 2]

    def query(self, left, right):
        if right <= left:
            return self.ide_ele
        left += self.num - 1
        right += self.num - 2
        res = self.ide_ele
        while right - left > 1:
            if left & 1 == 0:
                res = res | self.seg[left]
            if right & 1 == 1:
                res = res | self.seg[right]
                right -= 1
            left = left // 2
            right = (right - 1) // 2
        if left == right:
            res = res | self.seg[left]
        else:
            res = (res | self.seg[left]) | self.seg[right]
        return res


N = int(input())
S = list(input().strip())
Q = int(input())
MAX_DIGIT = 26
st = SegmentTree(S)


for i in range(Q):
    q, a, b = map(str, input().split())
    if int(q) == 1:
        a = int(a) - 1
        st.update(a, b)
    if int(q) == 2:
        a = int(a) - 1
        b = int(b)
        res = st.query(a, b)
        print(str(bin(res)).count('1'))
### BUGGY CODE ###

#!/usr/bin/env python
# coding: utf-8

# In[1]:


import numpy as np


# In[71]:


N,M = map(int, input().split())
data = []
for i in range(N):
    data.append(list(map(int, input().split())))


# In[72]:


data = np.array(data)


# In[84]:


sorted_data = data[np.argsort(data[:, 0])]


# In[87]:


ans = 0
for i in range(N):
    if sum(sorted_data[:, 1][:i + 1]) <= M:
        ans += sorted_data[i, 0] * sorted_data[i, 1]
        #print(i, sorted_data[i, 0], sum(sorted_data[:, 1][:i + 1]), ans)
    else:
        ans += sorted_data[i, 0] * (M - sum(sorted_data[:, 1][:i]))
        #print(i, sorted_data[i, 0], (M - sum(sorted_data[:, 1][:i])), ans)
        break

print(ans)


# In[ ]:






### FIXED CODE ###

#!/usr/bin/env python
# coding: utf-8

# In[14]:


N,M = map(int, input().split())
AB = []
for _ in range(N):
    AB.append(list(map(int, input().split())))


# In[15]:


AB_s = sorted(AB, key=lambda x: x[0])

cnt = 0
ans = 0
for idx,lst in enumerate(AB_s):
#     print(lst)
    c = lst[0]
    n = lst[1]
    if n <= M-cnt:
        ans += c*n
        cnt += n
#         print(cnt)
    else:
        ans += c*(M-cnt)
        cnt += (M-cnt)
#         print(cnt)
        break
print(ans)


# In[ ]:
### BUGGY CODE ###

from sys import stdin
n,m,k = map(int, stdin.readline().rstrip().split())
a = list(map(int, stdin.readline().rstrip().split()))
b = list(map(int, stdin.readline().rstrip().split()))

A = [0]
B = [0]

for i in range(0, n):
    A.append(A[i]+a[i])
for i in range(0, m):
    B.append(B[i]+b[i])


ans= 0
for i in range(0, n + 1):
    j = m
    if A[i] > k:
        break
    while A[i] + B[j] > k:
        j -= 1
    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()))


a_pre,b_pre=[0],[0]

for i in range(n):
	a_pre.append(a_pre[i]+a[i])

for i in range(m):
	b_pre.append(b_pre[i]+b[i])

ans,j=0,m
for i in range(n+1):
	if a_pre[i]>k:
		break
	while b_pre[j]>k-a_pre[i]:
		j-=1

	ans=max(ans,i+j)

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

import sys
input = sys.stdin.buffer.readline

mod = 10**9+7
N = int(input())
adj = [[] for _ in range(N+1)]
for _ in range(N-1):
    a, b = map(int, input().split())
    adj[a].append(b)
    adj[b].append(a)

st = [1]
seen = [0] * (N+1)
seen[1] = 1
child = [[] for _ in range(N+1)]
seq = []
while st:
    v = st.pop()
    seq.append(v)
    for u in adj[v]:
        if not seen[u]:
            seen[u] = 1
            st.append(u)
            child[v].append(u)
seq.reverse()

ans = 0
half = pow(2, mod-2, mod)
half_n = pow(half, N-1, mod)
dp = [1] * (N+1)
for v in seq:
    tmp = (1 - half_n)%mod
    tmp2 = 0
    for u in child[v]:
        dp[v] += dp[u]
        tmp2 = (tmp2 + ((1 - pow(half, dp[u], mod))%mod * pow(half, N-dp[u]-1, mod)) % mod) % mod
    if dp[v] < N:
        tmp2 = (tmp2 + ((1 - pow(half, N-dp[v], mod)) % mod * pow(half, dp[v]-1, mod)) % mod) % mod
    if child[v]:
        tmp = (tmp - tmp2) % mod
        ans = (ans + tmp) % mod

print((ans * half)%mod)


### FIXED CODE ###

import sys
input = sys.stdin.buffer.readline

mod = 10**9+7
N = int(input())
adj = [[] for _ in range(N+1)]
for _ in range(N-1):
    a, b = map(int, input().split())
    adj[a].append(b)
    adj[b].append(a)

st = [1]
seen = [0] * (N+1)
seen[1] = 1
child = [[] for _ in range(N+1)]
seq = []
while st:
    v = st.pop()
    seq.append(v)
    for u in adj[v]:
        if not seen[u]:
            seen[u] = 1
            st.append(u)
            child[v].append(u)
seq.reverse()

ans = 0
half = pow(2, mod-2, mod)
half_n = pow(half, N-1, mod)
dp = [1] * (N+1)
for v in seq:
    tmp = (1 - half_n)%mod
    tmp2 = 0
    for u in child[v]:
        dp[v] += dp[u]
        tmp2 = (tmp2 + ((1 - pow(half, dp[u], mod))%mod * pow(half, N-dp[u]-1, mod)) % mod) % mod
    if dp[v] < N:
        tmp2 = (tmp2 + ((1 - pow(half, N-dp[v], mod)) % mod * pow(half, dp[v]-1, mod)) % mod) % mod
    if child[v]:
        tmp = (tmp - tmp2) % mod
        ans = (ans + tmp) % mod

print((ans * half)%mod)