Harryxun/stf_run huggingface dataset:
import sys


def LI(): return list(map(int, sys.stdin.buffer.readline().split()))
def I(): return int(sys.stdin.buffer.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]


s = S()
ans = ''
if 'C' in s:
    ans += 'C'
if 'F' in s[s.index('C'):]:
    ans += 'F'
if ans == 'CF':
    print('Yes')
else:
    print('No')


### FIXED CODE ###

import sys


def LI(): return list(map(int, sys.stdin.buffer.readline().split()))
def I(): return int(sys.stdin.buffer.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]


s = S()
ans = ''
if 'C' in s:
    ans += 'C'
    if 'F' in s[s.index('C'):]:
        ans += 'F'
if ans == 'CF':
    print('Yes')
else:
    print('No')
#import numpy as np
#import math
import sys

read = lambda: sys.stdin.readline().rstrip()

def cmb(n,r):
    from operator import mul
    from functools import reduce
    
    r = min(n-r,r)
    if r == 0: return 1
    over = reduce(mul, range(n, n - r, -1))
    under = reduce(mul, range(1,r + 1))
    
    return over // under

class Solution(object):
    def binomial_coefficients(self, n, A):

        num_max = max(A)
        min_val = 1000000001
        num_min = 0

        for i in range(n):
            if abs(A[i]-num_max/2) < min_val:
                min_val = A[i]-num_max/2
                num_min = A[i]

        return num_max, num_min

def main():
    n0 = int(read())
    A0 = tuple(map(int, read().split()))

    res0, res1 = Solution().binomial_coefficients(n0, A0)

    print(res0, res1)
 
if __name__ == "__main__":
    main()

### FIXED CODE ###

n,m,x=map(int,input().split())
Al=list(map(int,input().split()))
A = sum(i>x for i in Al)
print(min(A, m-A))
n = int(input())
a = list(map(int, input().split()))

i, s = 0, 0
while True:
	s += a[i]
	i += 1
	if s >= sum(a) // 2:
		break

b = a[::-1]
j, t = 0, 0
while True:
	t += b[j]
	j += 1
	if t >= sum(a) // 2:
 
print(min(s-(sum(a)-s), t-(sum(a)-t)))

### FIXED CODE ###

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

total = sum(A)

s = 0
for a in A:
	s += a
	if 2 * s >= total:
		break

B = A[::-1]
t = 0
for b in B:
	t += b
	if 2 * t >= total:
		break

print(min(2*s-total, 2*t-total))
def main():
    n = int(input())
    a = [int(x) for x in input().split()]
    b = [0]*n
    for i in reversed(range(n)):
        x = n//(i+1)
        now = 0
        for j in range(1,x+1):
            now += b[k*(i+1)-1]
        if a[i] != now%2:
            b[i]=1
    print(b.count(1))
    if not m==0:
        for i in range(n):
            if b[i]==1:
                print(str(i+1),end=" ")
    
if __name__ == '__main__':
    main()

### FIXED CODE ###

def main():
    n = int(input())
    a = [int(x) for x in input().split()]
    b = [0]*n
    for i in reversed(range(n)):
        x = n//(i+1)
        now = 0
        for j in range(1,x+1):
            now += b[j*(i+1)-1]
        if a[i] != now%2:
            b[i]=1
    m = b.count(1)
    print(m)
    if not m==0:
        for i in range(n):
            if b[i]==1:
                print(str(i+1),end=" ")
    
if __name__ == '__main__':
    main()
W, H, N = map(int, input().split())
xya = []
for _ in range(N):
  xya.append( list( map(int, input().split() ) ) )
  
W_0 = H_0 = 0
  
for i in range(N):
  
  if xya[i][2] == 1
    W_0 =  xya[i][0]
    
  elif xya[i][2] == 2:
    W = xya[i][0]
    
  elif xya[i][2] == 3:
    H_0 = xya[i][1]
    
  elif xya[i][2] == 4:
    H = xya[i][1]
    
  if (W - W_0 == 0) or (H - H_0 == 0):
    break
    
print(max([(W - W_0)*(H - H_0), 0]))

### FIXED CODE ###

W, H, N = map(int, input().split())
xya = []
for _ in range(N):
  xya.append( list( map(int, input().split() ) ) )
  
W_0 = H_0 = 0
  
for i in range(N):
  
  if xya[i][2] == 1:
        if W_0 < xya[i][0]:
            W_0 =  xya[i][0]
    
  elif xya[i][2] == 2:
        if W > xya[i][0]:
            W = xya[i][0]
    
  elif xya[i][2] == 3:
        if H_0 < xya[i][1]:
            H_0 = xya[i][1]
    
  elif xya[i][2] == 4:
        if H > xya[i][1]:
            H = xya[i][1]
    
  if (W - W_0 <= 0) or (H - H_0 <= 0):
    break
    
print(max([(W - W_0)*(H - H_0), 0]))
def get_next_int():
    return int(input().rstrip("\n"))


def get_next_ints(delim=" "):
    return tuple([int(x) for x in input().rstrip("\n").split(delim)])


def main():
    n = get_next_int()

    a = get_next_ints()
    b = get_next_ints()

    a_offsets = []
    b_offsets = []
    for i in range(n):
        a_offsets.append(str(a[i] ^ a[i - 1]))
        b_offsets.append(str(b[i] ^ b[i - 1]))
    #print(a_offsets)
    #print(b_offsets)
    a_text = " ".join(a_offsets)
    b_text = " ".join(b_offsets)
    target_text = a_text + " " + a_text
    start_pos = 0
    if target_text.find(b_text, start_pos) >= 0:
        fisrt_pos = target_text.find(b_text, start_pos)
        fisrt_pos_diff = target_text[:fisrt_pos].count(" ")
        fisrt_xor_diff = b[0] ^ a[fisrt_pos_diff]
        print(fisrt_pos_diff, fisrt_xor_diff)
        if target_text.find(b_text, fisrt_pos+1) >= 0:
            second_pos = target_text.find(b_text, fisrt_pos+1)
            #if second_pos < len(a):
            second_pos_diff = target_text[:second_pos].count(" ")
            second_xor_diff = b[0] ^ a[second_pos_diff]
            print(second_pos_diff, second_xor_diff)
            interval = (second_pos_diff - fisrt_pos_diff)
            remain = (n - second_pos_diff - 1) // (second_pos_diff - fisrt_pos_diff)
            for i in range(remain):
                print(second_pos_diff + interval * (i + 1), [fisrt_xor_diff,second_xor_diff ][i % 2])

if __name__ == '__main__':
    main()


### FIXED CODE ###

def get_next_int():
    return int(input().rstrip("\n"))


def get_next_ints(delim=" "):
    return tuple([int(x) for x in input().rstrip("\n").split(delim)])


def main():
    n = get_next_int()

    a = get_next_ints()
    b = get_next_ints()

    a_offsets = []
    b_offsets = []
    for i in range(n):
        a_offsets.append(str(a[i] ^ a[i - 1]))
        b_offsets.append(str(b[i] ^ b[i - 1]))
    #print(a_offsets)
    #print(b_offsets)
    a_text = " ".join(a_offsets)
    b_text = " ".join(b_offsets)
    target_text = a_text + " " + a_text
    start_pos = 0
    if target_text.find(b_text, start_pos) >= 0:
        fisrt_pos = target_text.find(b_text, start_pos)
        fisrt_pos_diff = target_text[:fisrt_pos].count(" ")
        fisrt_xor_diff = b[0] ^ a[fisrt_pos_diff]
        print(fisrt_pos_diff, fisrt_xor_diff)
        if target_text.find(b_text, fisrt_pos+1) >= 0:
            second_pos = target_text.find(b_text, fisrt_pos+1)
            second_pos_diff = target_text[:second_pos].count(" ")
            if second_pos_diff < len(a):
                second_xor_diff = b[0] ^ a[second_pos_diff]
                print(second_pos_diff, second_xor_diff)
                interval = (second_pos_diff - fisrt_pos_diff)
                remain = (n - second_pos_diff - 1) // (second_pos_diff - fisrt_pos_diff)
                for i in range(remain):
                    print(second_pos_diff + interval * (i + 1), [fisrt_xor_diff,second_xor_diff ][i % 2])

if __name__ == '__main__':
    main()
n = int(input())
s = [list(input()) for _ in range(n)]
ans = 0
sd = dict([])

for i in s:
    key = ''.join(sorted(i))
    sd.setdefault(key, 0)
    sd[key] += 1
    
for v in s_dict.values():
    ans += v * (v - 1) // 2
print(ans)

### FIXED CODE ###

n = int(input())
s = [list(input()) for _ in range(n)]
ans = 0
sd = dict([])

for i in s:
    key = ''.join(sorted(i))
    sd.setdefault(key, 0)
    sd[key] += 1
    
for v in sd.values():
    ans += v * (v - 1) // 2
print(ans)
def calculate(s,t):
  count = 0
  for i in t:
    if i != s[j]:
      count += 1
    j += 1
  return count  


s = raw_input()
t = raw_input()
print(calculate(s,t))

### FIXED CODE ###

def calculate(s,t):
    count = 0
    j = 0
    for i in s:
        if i != t[j]:
            count += 1
        j += 1
    return count
    
s = input()
t = input()
print(calculate(s,t))
def sign(x):
  if x<0:
    return -1
  elif x>0:
    return 1
  else:
    retrun 0
n = int(input())
a = list(map(int,input().split()))
cumulative_sum = a[0]
flag = sign(cumulative_sum)
ans = 0
for i in range(1,n):
  cumulative_sum += a[i]
  if sign(cumulative_sum) == flag or sign(cumulative_sum) == 0:
    ans += abs(-flag - cumulative_sum)
  flag = sign(cumulative_sum)
print(ans)

### FIXED CODE ###

def sign(x):
  if x<0:
    return -1
  elif x>0:
    return 1
  else:
    return 0
n = int(input())
a = list(map(int,input().split()))
a_sum_pn = 0
a_sum_np = 0
ans_pn = 0
ans_np = 0
flag = 1
for i in range(n):
  a_sum_pn += a[i]
  a_sum_np += a[i]
  if sign(a_sum_pn) != flag:
    ans_pn += abs(flag-a_sum_pn)
    a_sum_pn = flag
  if sign(a_sum_np) != -flag:
    ans_np += abs(-flag-a_sum_np)
    a_sum_np = -flag
  flag *= -1
print(min(ans_pn,ans_np))
import sys
import  math
import fractions
from collections import defaultdict
from functools import reduce
stdin = sys.stdin
         
ns = lambda: stdin.readline().rstrip()
ni = lambda: int(stdin.readline().rstrip())
nm = lambda: map(int, stdin.readline().split())
nl = lambda: list(map(int, stdin.readline().split()))
     
INF=10**18
mod=10**9+7
N=int(input())
A=nl()
ans=0
min_bai=1
#for i in range(N):#最大公倍数
#    min_bai=min_bai*A[i]//fractions.gcd(min_bai,A[i])

lcm = reduce(lambda x,y: x//fractions.gcd(x,y)*y, A)
 
#for i in range(N):
#    ans+=lcm//A[i]

ans = sum(lcm//x for x in A)
print(ans%mod)
    

### FIXED CODE ###

import sys
import  math
import fractions
from collections import defaultdict
stdin = sys.stdin
     
ns = lambda: stdin.readline().rstrip()
ni = lambda: int(stdin.readline().rstrip())
nm = lambda: map(int, stdin.readline().split())
nl = lambda: list(map(int, stdin.readline().split()))

N,M=nm()
print('Yes' if N==M else 'No')
n, k = map(int, input().split())
x_list = [0]*n
y_list = [0]*n
for i in range(n):
    x_list[i], y_list[i] = map(int, input().split())

x_element = set(x_list)
y_element = set(y_list)
ans = float("inf")

for i in range(len(x_element)):
    for j in range(len(y_element)):
        for k in range(i+1, len(x_element)):
            for l in range(j+1, len(y_element)):
                num = 0
                for m in range(n):
                    x_left = x_element[i]
                    x_right = x_element[k]
                    y_bottom = y_element[j]
                    y_upper = y_element[l]
                    if x_left <= x[m] <= x_right and y_bottom <= y[m] <= y_upper:
                        num += 1
                    if num >= k:
                        ans = min((x_right - x_left) * (y_upper - y_bottom), ans)

print(ans)

### FIXED CODE ###

N, K = map(int, input().split())
x_list = [0]*N
y_list = [0]*N
for i in range(N):
    x_list[i], y_list[i] = map(int, input().split())

x_element = sorted(set(x_list))
y_element = sorted(set(y_list))
ans = float("inf")

for i in range(len(x_element)):
    for j in range(len(y_element)):
        for k in range(i+1, len(x_element)):
            for l in range(j+1, len(y_element)):
                num = 0
                for m in range(N):
                    if x_element[i] <= x_list[m] <= x_element[k] and y_element[j] <= y_list[m] <= y_element[l]:
                        num += 1
                if num >= K:
                    ans = min((x_element[k] - x_element[i]) * (y_element[l] - y_element[j]), ans)

print(ans)
import math

L, R, d = map(int, input().parse())

num = 0
start_d = int(math.ceil(L / d))
end_d = int(math.floor(R / d))

return end_d - start_d +1

### FIXED CODE ###

# -*- coding: utf-8 -*-
import math

#L, R, d = map(int, input().parse())
L, R, d = map(int, input().split())
start_d = int(math.ceil(L / d))
end_d = int(math.floor(R / d))
print(end_d - start_d +1)
from collections import Counter
def main():
    N=int(input())
    AB=[list(map(int, input().split())) for _ in range(N-1)]
    G=[[]for _ in range(N)]
    cnt=[0]*N
    for a,b in AB:
        G[a-1].append(b-1)
        G[b-1].append(a-1)
        cnt[a-1]+=1
        cnt[b-1]+=1
    CI=sorted(((c,i) for i,c in enumerate(cnt)), reverse=True)
    ans=[0]*N
    C=[0]*N
    S=[[],[],[]]
    for i in range(N+1):
        S[i%3].append(i)
    stack=[(0,-1,0)]
    while stack:
        u,p,d=stack.pop()
        for v in G[u]:
            if v!=p:
                stack.append((v,u,d^1))
                C[v]=d
    X=sum(C)
    use=[False]*N
    for j,(c,i) in enumerate(CI[:N//3],1):
        ans[i]=j*3
        for u in G[i]:
            use[u]=True
    k=[i for i in range(1,N+1,3)]
    l=[i for i in range(2,N+1,3)]
    for i,c in enumerate(C):
        if c and not use[u]:
            if not k:
                print(-1)
                return
            ans[i]=k.pop()
            k+=3
        if not c and not use[u]:
            if not l:
                print(-1)
                return
            ans[i]=l.pop()
            l+=3
    for i in range(N):
        if ans[i]==0:
            if k:
                ans[i]=k.pop()
            elif l:
                ans[i]=l.pop()
            else:
                print(-1)
                return
    print(*ans)

if __name__ == "__main__":
    main()

### FIXED CODE ###

from collections import Counter
def main():
    N=int(input())
    AB=[list(map(int, input().split())) for _ in range(N-1)]
    G=[[]for _ in range(N)]
    cnt=[0]*N
    for a,b in AB:
        G[a-1].append(b-1)
        G[b-1].append(a-1)
        cnt[a-1]+=1
        cnt[b-1]+=1
    CI=sorted(((c,i) for i,c in enumerate(cnt)), reverse=True)
    ans=[0]*N
    C=[0]*N
    stack=[(0,-1,0)]
    while stack:
        u,p,d=stack.pop()
        for v in G[u]:
            if v!=p:
                stack.append((v,u,d^1))
                C[v]=d^1
    X=sum(C)
    if X<=N//3:
        D=[[i for i in range(1,N+1,3)]+[i for i in range(2,N+1,3)],[i for i in range(3,N+1,3)]]
        for i in range(N):
            if D[C[i]]:
                ans[i]=D[C[i]].pop()
            else:
                ans[i]=D[C[i]^1].pop()
    elif N-X<=N//3:
        D=[[i for i in range(3,N+1,3)],[i for i in range(1,N+1,3)]+[i for i in range(2,N+1,3)]]
        for i in range(N):
            if D[C[i]]:
                ans[i]=D[C[i]].pop()
            else:
                ans[i]=D[C[i]^1].pop()
    else:
        D=[[i for i in range(1,N+1,3)],[i for i in range(2,N+1,3)],[i for i in range(3,N+1,3)]]
        for i in range(N):
            if D[C[i]]:
                ans[i]=D[C[i]].pop()
            else:
                ans[i]=D[2].pop()
    print(*ans)

if __name__ == "__main__":
    main()
N = int(raw_input())

A = map(int,raw_input().split())

print max(A)-min(B)

### FIXED CODE ###

N = int(raw_input())

A = map(int,raw_input().split())

print max(A)-min(A)
def solve(a,b,c,x):
    count = 0
    for i in range(a+1):
        for j in range(b+1):
            for k in range(c+1):
                if 500*i+100*j+50*k == x:
                    count += 1
    return count

A,B,C,X = map(int, input().split())
print(solve(A,B,C,X))

### FIXED CODE ###

def solve(a,b,c,x):
    count = 0
    for i in range(a+1):
        for j in range(b+1):
            for k in range(c+1):
                if 500*i+100*j+50*k == x:
                    count += 1
    return count

A = int(input())
B = int(input())
C = int(input())
X = int(input())

print(solve(A,B,C,X))
n=int(input())
t,a=map(int,input().split())
h=map(int,input().split())
t1=[]
for i in range(n):
    t1.append(abs(a-(t-h[i]*0.006)))
print(t1.index(min(t1))+1)

### FIXED CODE ###

n=int(input())
t,a=map(int,input().split())
h=list(map(int,input().split()))
t1=[]
for i in range(n):
    t1.append(abs(a-(t-h[i]*0.006)))
print(t1.index(min(t1))+1)
N = int(input())
number = input().split(" ")
if N%2 == 0:
    count = 0
    for i in range(int(N/2)):
        if number.count(str(2*i +1)) == 2:
            count += 0
        else:
            count += 1
    if count != 0:
        print(0)
    else:
        print(2**(int(N/2)))
else:
    count = 0
    if "0" not in number:
        print(0)
    else:
        for i in range(int((N-1)/2)):
            if number.count(str(2*i+2)) == 2:
                count += 0
            else:
                count += 1
        if count != 0:
            print(0)
        else:
            print(2**(int((N-1)/2)))

### FIXED CODE ###

parameter = input().split(" ")
a = int(parameter[0])
b = int(parameter[2])
if parameter[1] == "+":
    print(a+b)
else:
    print(a-b)
N = int(input())
import math
n = int(math.sqrt(N))
s = 0
for i in range(1,n):
  if N%i == 0 and i > s:
    s = i
    
p = int(s+N/s-2)
print(p)

### FIXED CODE ###

N = int(input())
s = N+1
import math
m = int(math.sqrt(N))+1
for i in range(1,m):
  if N%i==0:
    a = i
    b = N/a
    s = min(a+b, s)
print(int(s)-2)
N,R=map(int,input().split())

if N >= 10:
    R' == R
else:
    R' == R + 100 * (10 - N)

print(R')

### FIXED CODE ###

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

if N >= 10:
    X = R
else:
    X = R + 100 * (10 - N)

print(X)
a = input()
b = input()
c = input()
k = input()

if(k<a):
    print(k)
elif(k>a and k<a+b):
    print(a)
elif(k>a+b and k<a+b+c):
    print(a-(k-(a+b)))


### FIXED CODE ###

a, b, c, k = map(int, input().split())

if(k<=a):
    print(k)
elif(k>a and k<=a+b):
    print(a)
else:
    print(a-(k-(a+b)))
d,t,s = map(int, input().split())
if t <= d/s:
  print('Yes')
 else:
  print('No')

### FIXED CODE ###

d,t,s = map(int, input().split())
if d/s <= t:
  print('Yes')
else:
  print('No')
def dfs(splitted: "the list of integer", a: int, b: int, depth: int) -> int:
  if len(splitted) == depth:
    return a + b
  else:
    # 左のdfs() 呼び出し -> +を挿入しなかったとき
    # 右のdfs() 呼び出し -> +を挿入したとき
    return dfs(splitted, a, b * 10, depth + 1) + dfs(s, a + b, splitted[i], depth + 1)

s = [int(x) for x in input()]
print(dfs(s, 0, 0, 0))

### FIXED CODE ###

s = input()
result_sum = 0
plus_count = len(s) - 1

for bit in range(1 << plus_count):
  splitted_string = s[0]
  for iter_plus in range(plus_count):
    if bit & (1 << iter_plus):
      splitted_string += '+'
    splitted_string += s[iter_plus+1]
  result_sum += eval(splitted_string)

print(result_sum)
# -*- coding:utf-8 -*-
import sys
N = int(input())
s = []
for tmp in range(N):
    s.append(int(input()))
s.sort()
total = sum(s)
if total%10 != 0:
    print(total)
else:
    for tmp in s:
        total -= tmp
        if total%10 != 0:
            print(total)
            sys.exit()
        else:
            total += tmp
    print(0)

### FIXED CODE ###

# -*- coding:utf-8 -*-
a = sum(list(map(int,input().split())))
if a >= 10:
    print("error")
else:
    print(a)
n=int(input())
ans = [0 for _in range(10050)]
	for i in range(1,105):
    	for j in range(1,105):
        	for k in range(1,105):
            	v=i*i+j*j+k*k+i*j+j*k+k*i;
              	if v<10050:
                  ans[v]+=1

for i in range(n):
  print(ans[i+1])
  

### FIXED CODE ###

n=int(input())
ans = [0 for _ in range(10050)]
for i in range(1,105):
	for j in range(1,105):
		for k in range(1,105):
			v = i*i+j*j+k*k+i*j+j*k+k*i;
			if v<10050:
				ans[v]+=1

for i in range(n):
	print(ans[i+1])
class UnionFind:
    def __init__(self, length):
        self.r = [-1] * length

    def root(self, x):
        if (self.r[x]) < 0:
            return x

        return self.r[x] - self.root(self.r[x])

    def unite(self, x, y):
        x = self.root(x)
        y = self.root(y)

        if x == y:
            return False
        r = self.r

        if r[x] > r[y]:
            x, y = y, x

        r[x] += r[y]
        r[y] = x

        return True

    def size(self, x):
        return -self.r[self.root(x)]


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


relateions = UnionFind(N)
for _ in range(M):
    A, B = map(int, input().split())
    relateions.unite(A-1, B-1)

max_ = -1
for i in range(N):
    max_ = max(relateions.size(i), max_)

print(max_)


### FIXED CODE ###

class UnionFind:
    def __init__(self, length):
        self.r = [-1] * length

    def root(self, x):
        rx = self.r[x]
        if (rx) < 0:
            return x

        return self.root(rx)

    def unite(self, x, y):
        x = self.root(x)
        y = self.root(y)

        if x == y:
            return False
        r = self.r

        if r[x] > r[y]:
            x, y = y, x

        r[x] += r[y]
        r[y] = x

        return True

    def size(self, x):
        return -self.r[self.root(x)]

    def debug(self):
        print(self.r)


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


relations = UnionFind(N)
for _ in range(M):
    A, B = map(int, input().split())
    relations.unite(A-1, B-1)

max_ = -1
for i in range(N):
    max_ = max(relations.size(i), max_)

print(max_)
n,m=map(int,input().split())
A=list(map(int,input().split()))
BC=[list(map(int,input().split())) for _ in range(m)]
A.sort()
BC.sort(key=lambda x:-x[1])

B=[]
for bc in BC:
    B+=[bc[1]]*bc[0]
    if len(B)>=N:
        break
B+=[0]*(N-len(B))
print(sum([max(A[i],B[i]) for i in range(N)]))


### FIXED CODE ###

N,M=map(int,input().split())
A=list(map(int,input().split()))
BC=[list(map(int,input().split())) for _ in range(M)]
A.sort()
BC.sort(key=lambda x:-x[1])

B=[]
for bc in BC:
    B+=[bc[1]]*bc[0]
    if len(B)>=N:
        break
B+=[0]*(N-len(B))
print(sum([max(A[i],B[i]) for i in range(N)]))
# coding: utf-8
# Your code here!
import itertools
import math
from scipy.special import comb

N,K = map(int,input().split())
m = pow(10, 9) + 7
for i in range(1,K+1):
    b = comb(K-1, i-1, True)
    r = comb(N-K+1, i, True)
    print(int(b * r % m))

### FIXED CODE ###

# coding: utf-8
# Your code here!
from operator import mul
from functools import reduce

def cmb(n, r):
	if n < r:
		return 0
	r = min(n - r, r)
	if r == 0:
		return 1
	numer = reduce(mul, range(n, n - r, -1))
	denom = reduce(mul, range(1, r + 1))
	return numer // denom % INF

N,K = map(int,input().split())
INF = 10**9 + 7
for i in range(1,K+1):
    print(cmb(K-1, i-1) * cmb(N-K+1, i) % INF)
h,w = map(int,input().split())
#0が進めるところ、1は無理
lis = [[1 if l == '#' else 0 for l in list(input())] for _ in range(h)]
#ゴールは9
lis[h-1][w-1] = 9
#print(lis)
#[[0, 0, 1], [1, 0, 0], [0, 0, 9]]

#この問題ではbfsを始める前に、もともと壁だったところの数を記録しておく
wall = 0
for row in lis:
    for column in row:
        if column == 1:
            wall +=1

count = 0
#(開始x,開始y,移動回数)
pos = [[0,0,0]]
while len(pos)>0:
    x,y,depth = pos.pop(0)

    if lis[x][y] == 9:
        count = depth
        break

    #探索済みのところは、1にする
    lis[x][y] = 1

    #遷移先は0or9なので、1以外なら行ける
    if x-1>=0 and lis[x-1][y] != 1:
        pos.append([x-1,y,depth+1])
    if x+1<w and lis[x+1][y] != 1:
        pos.append([x+1,y,depth+1])
    if y-1>=0 and lis[x][y-1] != 1:
        pos.append([x,y-1,depth+1])
    if y+1<h and lis[x][y+1] != 1:
        pos.append([x,y+1,depth+1])

#(全マス) - (壁) - (移動する道順上のマスの数 ＝ 最短の移動回数＋１）
print(h*w-wall-(count+1))

### FIXED CODE ###

h,w = (int(x) for x in input().split())
ab = []
count = 0
for _ in range(h):
    a = input()
    a = a+'#'
    ab.append(list(a))
    for i in a:
        if i == '.':
            count += 1
ab.append(list('#'*w))
dp = [[0 for i in range(w)] for j in range(h)]
 
step = [[0, 0]]
dp[0][0] = 1
 
while len(step) > 0:
    y, x = step.pop(0)
    if y == h-1 and x == w-1:
        print(count-dp[y][x])
        exit()
    if ab[y+1][x] == '.' and dp[y+1][x] == 0 :
        step.append([y+1, x])
        dp[y+1][x] = dp[y][x] + 1
    if ab[y][x+1] == '.' and dp[y][x+1] == 0 :
        step.append([y, x+1])
        dp[y][x+1] = dp[y][x] + 1
    if ab[y-1][x] == '.' and dp[y-1][x] == 0 :
        step.append([y-1, x])
        dp[y-1][x] = dp[y][x] + 1
    if ab[y][x-1] == '.' and dp[y][x-1] == 0 :
        step.append([y, x-1])
        dp[y][x-1] = dp[y][x] + 1
 
 
print(-1)