Harryxun/stf_run huggingface dataset:
s=list(input())
t=list(input())

lens=len(s)
lent=len(t)

dp=[[0]*(lent+1) for _ in range(lens+1)]

for i in range(lens):
    for j in range(lent):
        if s[i]==t[j]:
            dp[i+1][j+1]=dp[i][j]+1
        else:
            dp[i+1][j+1]=max(dp[i+1][j],dp[i][j+1])
#print(dp[-1][-1])

ans=''
i=-1
tmp=dp[-1][-1]
for j in range(lent,-1,-1):
    if dp[i-1][j-1]<tmp:
        ans+=t[j-1]
        tmp=dp[i-1][j-1]
        i-=1
print(ans[::-1])

### FIXED CODE ###

s=list(input())
t=list(input())

lens=len(s)
lent=len(t)

dp=[[0]*(lent+1) for _ in range(lens+1)]

for i in range(lens):
    for j in range(lent):
        if s[i]==t[j]:
            dp[i+1][j+1]=dp[i][j]+1
        else:
            dp[i+1][j+1]=max(dp[i+1][j],dp[i][j+1])

ans=''
i,j=lens,lent

while i>=0 and j>=0:
    if dp[i-1][j]==dp[i][j]:i-=1
    elif dp[i][j-1]==dp[i][j]:j-=1
    else:
        ans=s[i-1]+ans
        i,j=i-1,j-1
print(ans)
N, W = map(int, input().split())
wv = []
for _ in range(N):
    wv.append(list(map(int, input().split())))
# print(wv)
dp = [[0] * 110 for _ in range(100100)]


for i in range(N):
    for sum_w in range(W + 1):

        if wv[i][0] <= sum_w:
            dp[i + 1][sum_w] = max(dp[i + 1][sum_w], dp[i][sum_w - wv[i][0]] + wv[i][1])

        dp[i + 1][sum_w] = max(dp[i + 1][sum_w], dp[i][sum_w])
print(dp[N][W])


### FIXED CODE ###

N, W = map(int, input().split())
wv = []
for _ in range(N):
    wv.append(list(map(int, input().split())))
# print(wv)
dp = [[0] * 100100 for _ in range(110)]


for i in range(N):
    for sum_w in range(W + 1):

        if wv[i][0] <= sum_w:
            dp[i + 1][sum_w] = max(dp[i + 1][sum_w], dp[i][sum_w - wv[i][0]] + wv[i][1])

        dp[i + 1][sum_w] = max(dp[i + 1][sum_w], dp[i][sum_w])
print(dp[N][W])
x = int(input())

if 360 % x == 0:
  print(360 // x)
else:
  import math
  gcd = mat.gcd(x, 360)
  lcm = (x * 360) // gcd
  print(lcm // x)

### FIXED CODE ###

x = int(input())
     
if 360 % x == 0:
  print(360 // x)
else:
  import math
  gcd = math.gcd(x, 360)
  lcm = (x * 360) // gcd
  print(lcm // x)
n = input()
if n<100 or n>999:
	x = len(n)
	for i in range(x):
    	if n[i] is '7':
       		print('Yes')
        	break
else:
  print('No')

### FIXED CODE ###

n = input()
x = len(n)
b = 'false'
for i in range(x):
    if n[i] is '7':
        b = 'true'
        print('Yes')
        break
if b is not 'true':
  print('No')
# ABC 044 A - 高橋君とホテルイージー / Tak and Hotels (ABC Edit)
N = int(input())
K = int(input())
X = int(input())
Y = int(input())

if K > N:
    ans = N * X
elif N > K:
    ans = K * X
    ans +=(N-K)* Y

print( ans )

### FIXED CODE ###

# ABC 044 A - 高橋君とホテルイージー / Tak and Hotels (ABC Edit)
N = int(input())
K = int(input())
X = int(input())
Y = int(input())

if K >= N:
    ans = N * X
elif N > K:
    ans = K * X
    ans +=(N-K)* Y

print( ans )
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n
        
    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]
    
    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        
        if x == y:
            return
        
        if self.parents[x] > self.parents[y]:
            x, y = y, x
        
        self.parents[x] += self.parents[y]
        self.parents[y] = x
    
    def size(self, x):
        return -self.parents[self.find(x)]
        
    def same(self, x, y):
        return self.find(x) == self.find(y)
    
    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]
    
    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]


    def group_count(self):
        return len(self.roots())
    
    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}
    
    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

n,m=map(int,input().split())
uf=UnionFind(n)
for i in range (m):
    a,b=map(int,input().split())
    uf.union(a,b)


print(uf.group_count()-1)




### FIXED CODE ###

class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n
        
    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]
    
    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        
        if x == y:
            return
        
        if self.parents[x] > self.parents[y]:
            x, y = y, x
        
        self.parents[x] += self.parents[y]
        self.parents[y] = x
    
    def size(self, x):
        return -self.parents[self.find(x)]
        
    def same(self, x, y):
        return self.find(x) == self.find(y)
    
    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]
    
    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]


    def group_count(self):
        return len(self.roots())
    
    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}
    
    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

n,m=map(int,input().split())
uf=UnionFind(n)
for i in range (m):
    a,b=map(int,input().split())
    uf.union(a-1,b-1)


print(uf.group_count()-1)
import sys

sys.setrecursionlimit(3000)

def dfs(G, v, cur):
    color[v] = cur;

    for next_v in G[v] :
        if not(color[next_v] == -1) :
            if color[next_v] == cur :
                return 0;
            continue;
        if not(dfs(G,next_v,1-cur)):
            return 0;
    return 1;

n,m = list(map(int,input().split()));

G = [[] for i in range(n)];
for i in range(m) :
    a,b = list(map(int,input().split()));
    G[a-1].append(b-1);
    G[b-1].append(a-1);

color = [-1]*n;

if dfs(G,0,0) :
    print(sum(color)*(n-sum(color))-m);
else :
    print(n*(n-1)//2-m);

### FIXED CODE ###

import sys

sys.setrecursionlimit(10**6)

def dfs(G, v, cur):
    color[v] = cur;

    for next_v in G[v] :
        if not(color[next_v] == -1) :
            if color[next_v] == cur :
                return 0;
            continue;
        if not(dfs(G,next_v,1-cur)):
            return 0;
    return 1;

n,m = list(map(int,input().split()));

G = [[] for i in range(n)];
for i in range(m) :
    a,b = list(map(int,input().split()));
    G[a-1].append(b-1);
    G[b-1].append(a-1);

color = [-1]*n;

if dfs(G,0,0) :
    print(sum(color)*(n-sum(color))-m);
else :
    print(n*(n-1)//2-m);
#d
N = int(input())
A = list(map(int, input().split()))
Q = int(input())
B = [0] * Q
C = [0] * Q
for i in range(Q):
    B[i], C[i] = map(int, input().split())
D = [0] * (10**5)
ans=sum(A)
for i in A:
    D[i]+=1
for x in range(Q):
    D[C[x]]+=D[B[x]]
    tmp=D[B[x]]
    ans=ans+tmp*(C[x]-B[x])
    print(ans)
    D[B[x]]=0

### FIXED CODE ###

#d
N = int(input())
A = list(map(int, input().split()))
Q = int(input())
B = [0] * Q
C = [0] * Q
for i in range(Q):
    B[i], C[i] = map(int, input().split())
D = [0] * (10**5+1)
ans=sum(A)
for i in A:
    D[i]+=1
for x in range(Q):
    ans+=D[B[x]]*int(C[x]-B[x])
    print(ans)
    D[C[x]]+=D[B[x]]
    D[B[x]]=0
n=int(input())
temp=list(n)
if n%sum(temp)==0:
  print("Yes")
else:
  print("No")

### FIXED CODE ###

n=int(input())
temp=list(str(n))
a=0
for i in range(0,len(temp)):
  a=a+int(temp[i])
if n%a==0:
  print("Yes")
else:
  print("No")
while True:
    e = int(input())
    if e == 0:
        break
    else:
        ans = float('inf')
        for z in range(e+1):
            z3 = z ** 3
            rest1 = e - z3
            if rest1 >= 0:
                for y in range(rest1+1):
                    y2 = y ** 2
                    rest2 = rest1 - y2
                    if rest2 >= 0:
                        s = rest2 + y + z
                        if s < ans:
                            ans = s
                    else:
                        break
            else:
                break
        print(ans)


### FIXED CODE ###

while True:
    e = int(input())
    if e == 0:
        break
    z, ans = 0, float('inf')
    while z ** 3 <= e:
        r = e - z ** 3
        y = int(r ** 0.5)
        x = r - y ** 2
        ans = min(ans, x + y + z)
        z += 1
    print(ans)
from typing import List


L = 40

def get_binary_str(n: int) -> str:
    binary = bin(n)[2:]
    padding_length = L - len(binary)
    return '0' * padding_length + binary

def get_first_one_pos(s: str) -> int:
    i = 0
    while i < len(s) and s[i] == '0':
        i += 1
    return i

def xor(x: int, y: int) -> int:
    if x == y:
        return 0
    else:
        return 1

def calc_xor(i: int, x: int, binary_As: List[List[str]]) -> int:
    ret = 0
    for binary_A in binary_As:
        ret += xor(x, int(binary_A[i]))
    return ret


def main():
    N, K = list(map(int, input().split(' ')))
    As = list(map(int, input().split(' ')))

    binary_As = [get_binary_str(A) for A in As]
    binary_K = get_binary_str(K)
    one_pos = get_first_one_pos(binary_K)

    i = 0
    ret = 0
    while i < one_pos:
        ret += calc_xor(i, 0, binary_As) * 2**(L-i-1)
        i += 1

    while i < L:
        a = calc_xor(i, 0, binary_As)
        b = calc_xor(i, 1, binary_As)
        ret += a * 2**(L-i-1) if a > b else b * 2**(L-i-1)
        i += 1

    print(ret)

if __name__ == '__main__':
    main()

### FIXED CODE ###

L = 50

def get_binary_str(n: int) -> str:
    binary = bin(n)[2:]
    padding_length = L - len(binary)
    return '0' * padding_length + binary

def get_first_one_pos(s: str) -> int:
    i = 0
    while i < len(s) and s[i] == '0':
        i += 1
    return i

def xor(x: int, y: int) -> int:
    if x == y:
        return 0
    else:
        return 1

def calc_xor(i: int, x: int, binary_As) -> int:
    ret = 0
    for binary_A in binary_As:
        ret += xor(x, int(binary_A[i]))
    return ret


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

binary_As = [get_binary_str(A) for A in As]
binary_K = get_binary_str(K)
one_pos = get_first_one_pos(binary_K)

i = 0
ret = 0
while i < one_pos:
    ret += calc_xor(i, 0, binary_As) * 2**(L-i-1)
    i += 1

flag = False
while i < L:
    a = calc_xor(i, 0, binary_As)
    b = N - a
    if flag:
        ret += a * 2**(L-i-1) if a > b else b * 2**(L-i-1)
    else:
        if binary_K[i] == '1':
            if a > b:
                flag = True
            ret += a * 2**(L-i-1) if a > b else b * 2**(L-i-1)
        else:
            ret += a * 2**(L-i-1)

    i += 1

print(ret)
ans = -1

for n in range(1001):##最大値を間違えていた
        if math.floor(n*0.08) == A and math.floor(n*0.1) == B:
            ans = n
            break

print(ans)

### FIXED CODE ###

#input
A, B = map(int,input().split())
#消費税0.08 0.1
import math

ans = -1

for n in range(1001):##最大値を間違えていた
        if math.floor(n*0.08) == A and math.floor(n*0.1) == B:
            ans = int(n)
            break

print(ans)
n, m = map(int, input().split())

if m == 0:
    print(0, 0)
else:
    check_list = [0]*20000
    wa = 0
    ac = 0
    for i in range(m):
        p, s = input().split()
        p = int(p)
        if check_list[p] == 1:
            continue
        elif check_list[p] == 0 and s == 'AC':
            check_list[p] = 1
            ac += 1
        elif check_list[p] ==0 and s == 'WA':
            wa += 1
    print(ac, wa)

### FIXED CODE ###

n, m = map(int, input().split())

ac_list = [0]*(n+1)
wa_list = [0]*(n+1)
wa = 0
ac = 0
if m == 0:
    pass
else:
    for i in range(m):
        p, s = input().split()
        p = int(p)
        if ac_list[p] == 1:
            continue
        if ac_list[p] == 0 and s == 'AC':
            ac_list[p] = 1
        #elif check_list[p] == 0 and s == 'WA':                                          
        else:
            wa_list[p] += 1
    for t_ac, t_wa in zip(ac_list, wa_list):
        if t_ac == 1:
            wa += t_wa
            ac += t_ac
print(ac, wa)
a,b = map(float, input().split())
bb = b*100
c = a*bb/100
print(floor(c))

### FIXED CODE ###

from math import floor
from decimal import Decimal
a,b = map(Decimal, input().split())
c = a*b
print(floor(c))
a,b,c = map(int(input()))
print(a*b//2)

### FIXED CODE ###

a,b,c = map(int,input().split())
print(a*b//2)
def culc_expected_value(num):
  output = 0
  if num != 1:
    for i in range(1, num+1):
      output += i/num
  else:
    output = 1
  return output
 
n, k = map(int, input().split())
p_list = list(map(int, input().split()))
max_nums = 0
max_targets = []
for j in range(0, len(p_list)-k-1):
  targets = [p_list[j+m] for m in range(k)]
  t_sum = sum(targets)
  if t_sum >= max_nums:
    max_nums = t_sum
    max_targets = targets
# print(max_targets)

ans = 0
for t in max_targets:
  ans += culc_expected_value(t)
  # print(ans)

print(ans)

### FIXED CODE ###

n, k = map(int, input().split())
p_list = list(map(int, input().split()))
tmp = sum(p_list[:k])
max_num = sum(p_list[:k])
for i in range(len(p_list)-k):
  tmp = tmp - p_list[i] + p_list[i+k]
  if tmp >= max_num:
    max_num = tmp
print((max_num+k)/2)
p=raw_input()
if len(p)<6 or islower(p) or isupper(p) or isdigit(p):
	print "INVARID"
else:
	print "VARID"

### FIXED CODE ###

p=raw_input()
print "INVALID" if len(p)<6 or p.isalpha() or p.isdigit() or p.islower() or p.isupper() else "VALID"
n, k = map(int, input().split())
cnt = 1
while True:
  if n <= k**cnt + 1:
    cnt++
print(cnt)

### FIXED CODE ###

n, k = map(int, input().split())
cnt = 1
while True:
  if n <= k**cnt - 1:
    break
  cnt += 1
print(cnt)
import sys
read = sys.stdin.read
readlines = sys.stdin.readlines
def main():
    x = int(input())
    p1 = 1
    while True:
        p15 = p1 ** 5
        rt1 = ((x + p15) ** 0.2) % 1
        if (x - p15) < 0:
            rt2 = ((-1*(x - p15)) ** 0.2) % 1
        else:
            rt2 = ((x - p15) ** 0.2) % 1
        if rt1 == 0:
            r = (int((x + p15) ** 0.2), p15)
            break
        elif rt2 == 0:
            r = (int((-1*(x - p15)) ** 0.2), -p15)
            break
        else:
            p1 += 1
    print(*r, sep=' ')
if __name__ == '__main__':
    main()

### FIXED CODE ###

import sys
from math import pow
def main():
    x = int(input())
    for a in range(-1000,1001):
        for b in range(-1000,1001):
            if pow(a, 5) - pow(b, 5) == x:
                print(a, b)
                sys.exit()

if __name__ == '__main__':
    main()
import sys
s=[]
dic={"A":["11","11"],"B":["1","1","1","1"],"C":["1111"],"D":["01","11","10"],
		"E":["110","011"],"F":["10","11","01"],"G":["011","110"]}
cnt=0
for line in sys.stdin:
	cnt+=1
	if line=="":
		continue
	if cnt<8:
		s.append(line)
	else:
		cnt=0
		while s[0]=="00000000":
			del s[0]
		while s[len(s)-1]=="00000000":
			del s[len(s)-1]
		i=0
		while i<len(s[0]):
			for l in s:
				if l[i]=="1":
					break
			else:
				for l in range(len(s)):
					s[l]=s[l][0:i]+s[l][i+1:len(s[l])]
				i-=1
			i+=1
		for d in dic.keys():
			if dic[d]==s:
				print d
				break
		while len(s)>0:
			del(s[0])

### FIXED CODE ###

import sys
dic={"A":["11","11"],"B":["1","1","1","1"],"C":["1111"],"D":["01","11","10"],
		"E":["110","011"],"F":["10","11","01"],"G":["011","110"]}
s=[]
linecnt=0
for line in sys.stdin:
	if line=="\n" or line=="":
		continue
	linecnt+=1
	if linecnt<8:
		s.append(line.rstrip("\n"))
	else:
		s.append(line.rstrip("\n"))
		while s[0]=="00000000":
			del(s[0])
		while s[len(s)-1]=="00000000":
			del(s[len(s)-1])
		i=len(s[0])-1
		while i>=0:
			for l in xrange(len(s)):
				if s[l][i]=="1":
					break
			else:
				for l in xrange(len(s)):
					s[l]=s[l][0:i]+s[l][i+1:len(s[l])]
			i-=1
		for d in dic.keys():
			if dic[d]==s:
				print d
				break
		while len(s)>0:
			del(s[0])
		linecnt=0
a, b, c = map(int, input().split())
s = a*b
if s <= c:
    print("{}".format(s))
   else:
       print("{}".format(c))

### FIXED CODE ###

a,b,c = map(int, input().split())
if a*b <= c:
    print(a*b)
else:
    print(c)
N=int(input())
a=[int(i) for i in input().split()]
 
count=0
ans=0
for i in range(N):
    if a[i]<0:
        c+=1        
    a[i]=abs(a[i])

if c%2==0:
    ans=sum(a)
else:
    a.sort()
    ans=sum(a)-a[0]

### FIXED CODE ###

N = int(input())

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

count=0
ans=0

for i in range(N):
    if a[i]<0:
        count+=1
    a[i]=abs(a[i])

if count%2==0:
    ans=sum(a)

else:
    a.sort()
    ans=sum(a)-a[0]*2

print(ans)
N = int(input())
print(int(2*N / math.gcd(2, N)))

### FIXED CODE ###

N = int(input())
if N%2==0:
    print(N)
else:
    print(N*2)
# input()
# int(input())
# map(int, input().split())
# list(map(int, input().split()))

import numpy as np
inf = 10**9+7
mod = 10**9+7
n, k = map(int, input().split())
g_val = [list(map(int, input().split())) for i in range(n)]
netalist = [False for i in range(n+1)]
netanum = [0 for i in range(n+1)]
g_val.sort(key=lambda x: x[1])
used_list = []
ans = [0 for i in range(k+1)] # i種類食べた時の最大値
preans = 0
for j in range(k):
    if g_val:
        g,v = g_val.pop()
        netalist[g] = True
        netanum[g]+=1
        used_list.append((v,g))
        preans+=v

kind = sum(list(map(int, netalist)))
ans[kind] = preans+(kind*kind)

import heapq # 優先度付きキュー(最小値取り出し)
heapq.heapify(used_list)   # ヒープ化


while used_list:
    v,g = heapq.heappop(used_list) # 最小値の取り出し
    if netanum[g] > 1:
        while g_val:
            gnew,vnew = g_val.pop()
            if netanum[gnew] == 0:
                ans[kind+1] = ans[kind]-v-(kind*kind)+vnew+((kind+1)*(kind+1))
                kind+=1
                netanum[g] -= 1
                netanum[gnew] += 1
                break
    if not g_val:
        break
print(max(ans))

### FIXED CODE ###

# input()
# int(input())
# map(int, input().split())
# list(map(int, input().split()))

inf = 10**9+7
mod = 10**9+7
n, k = map(int, input().split())
g_val = [list(map(int, input().split())) for i in range(n)]
netalist = [False for i in range(n+1)]
netanum = [0 for i in range(n+1)]
g_val.sort(key=lambda x: x[1])
used_list = []
ans = [0 for i in range(k+1)] # i種類食べた時の最大値
preans = 0
for j in range(k):
    if g_val:
        g,v = g_val.pop()
        netalist[g] = True
        netanum[g]+=1
        used_list.append((v,g))
        preans+=v

kind = sum(list(map(int, netalist)))
ans[kind] = preans+(kind*kind)

import heapq # 優先度付きキュー(最小値取り出し)
heapq.heapify(used_list)   # ヒープ化


while used_list:
    v,g = heapq.heappop(used_list) # 最小値の取り出し
    if netanum[g] > 1:
        while g_val:
            gnew,vnew = g_val.pop()
            if netanum[gnew] == 0:
                ans[kind+1] = ans[kind]-v-(kind*kind)+vnew+((kind+1)*(kind+1))
                kind+=1
                netanum[g] -= 1
                netanum[gnew] += 1
                break
    if not g_val:
        break
print(max(ans))
import math
import sys
input = sys.stdin.readline

def main():
    n = int(input())
    xy = [tuple(map(int, input().split())) for _ in range(n)]
    checked = [[None for _ in range(n)] for _ in range(n)]
    sum_v = 0
    p = 1
    for i in range(n):
        p *= i + 1
        for j in range(n):
            if i == j or dis[i][j] is not None:
                continue
            checked[i][j] = 1
            checked[j][i] = 1
            sum_v += math.sqrt((xy[i][0] - xy[j][0]) ** 2 + (xy[i][1] - xy[j][1]) ** 2)
    print(sum_v * 2 / n)

if __name__ == '__main__':
    main()


### FIXED CODE ###

import math
import sys
input = sys.stdin.readline

def main():
    n = int(input())
    xy = [tuple(map(int, input().split())) for _ in range(n)]
    dis = [[None for _ in range(n)] for _ in range(n)]
    sum_v = 0
    p = 1
    for i in range(n):
        p *= i + 1
        for j in range(n):
            if i == j or dis[i][j] is not None:
                continue
            d = math.sqrt((xy[i][0] - xy[j][0]) ** 2 + (xy[i][1] - xy[j][1]) ** 2)
            dis[i][j] = d
            dis[j][i] = d
            sum_v += d
    print(sum_v * 2 / n)

if __name__ == '__main__':
    main()
S = input()

if S == 'Sunny':
    answer =('cloudy')

elif S == 'cloudy':
    answer =('Rainy')

elif S == 'Rainy':
    answer =('Sunny')

print=answer


### FIXED CODE ###

S = input()

if S == 'Sunny':
    print('Cloudy')

elif S == 'Cloudy':
    print('Rainy')

elif S =='Rainy':
    print('Sunny')
h, w = [int(n) for n in input().split()]
i = min(h, w)
j = max(h, w)
area = i * j
if i % 3 == 0 or j % 3 == 0:
    print(0)
else:
    p = j // 3 + 1
    q = j // 3 - 1
    a = i * p
    b = i // 2 * (j - p)
    c = i * q - (i // 2 * (j - q))

    print(min(abs(a - b), abs(c))

### FIXED CODE ###

h, w = [int(n) for n in input().split()]
i = min(h, w)
j = max(h, w)
area = i * j
if i % 3 == 0 or j % 3 == 0:
    print(0)
else:
    lst = []
    for r, s in [(i, j), (j, i)]:
        
        p = s // 3 + 1
        q = s // 3 
        a1 = r * p
        a2 = r * q
        b1 = r // 2 * (s - p)
        bb1 = (r // 2 - 1) * (s - p)
        b2 = r // 2 * (s - q)
        bb2 = (r // 2 - 1) * (s - q)
        c1 = (s - p) // 2 * r
        cc1 = ((s - p) // 2- 1) * r
        c2 = (s - q) // 2 * r
        cc2 = ((s - q) // 2 - 1) * r
        tup = [(a1, b1), (a2, b2), (a1, c1), (a2, c2),
               (a1, bb1), (a2, bb2), (a1, cc1), (a2, cc2)]
        lst.extend([abs(max(a, b, area - a - b) - min(a, b, area - a - b))
                    for a, b in tup])
    print(min(lst))
import math
N,H = map(int,input().split())

aList = []
bList = []
for count in range(0,N):
    a,b = map(int, input().split())
    aList.append(a)
    bList.append(b)

bList.sort()
bList.reverse()

maxA = max(aList)

count = 0
damage = 0
for b in bList:
    if maxA < b:
        damage+=b
        count+=1
    if damage > H:
        break

if damage < H:
    remainingHP = H - damage
    count = count + math.ceil(remainingHP / maxA)

print(count)

### FIXED CODE ###

import math

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

mean = (a+b)/2
print(math.ceil(mean))
#%%
import sys
def input():
    return sys.stdin.readline().rstrip()

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

    g = [[] for _ in range(N-1)]
    for i in range(N-1):
        a, b = map(int, input().split())
        g[a-1].append((b-1, i))

    ans = [[None] for _ in range(N-1)]

    def dfs(v0, c0):
        c = 1
        for v1, e in g[v0]:
            if c==c0:
                c += 1
            ans[e] = c
            if v1 < N-1:
                dfs(v1, c)
            c += 1

    dfs(0, 0)

    print(max(ans))
    for c in ans:
        print(c)



# %%
if __name__ == '__main__':
    main()

# %%
# from atcoder_test import doTest
# doTest("abc146","d",main)


### FIXED CODE ###


#%%
import sys
sys.setrecursionlimit(100000)

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

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

    g = [[] for _ in range(N-1)]
    for i in range(N-1):
        a, b = map(int, input().split())
        g[a-1].append((b-1, i))

    ans = [[None] for _ in range(N-1)]

    def dfs(v0, c0):
        c = 1
        for v1, e in g[v0]:
            if c==c0:
                c += 1
            ans[e] = c
            if v1 < N-1:
                dfs(v1, c)
            c += 1

    dfs(0, 0)

    print(max(ans))
    for c in ans:
        print(c)



# %%
if __name__ == '__main__':
    main()

# %%
# from atcoder_test import doTest
# doTest("abc146","d",main)
s = str(input())
s_ = list(s)
for i in range(len(s)):
  if i==0 and len(s)==1 and s_[i]=='?':
    s_[i]='D'
  elif i==0 and s_[i]=='?' and s_[i+1]=='D':
      s_[i]='P'
  elif i==0 and s_[i]=='?' and s_[i+1]=='P':
      s_[i]='D'
  elif s_[i]=='?' and s[i-1]=='P':
    s_[i]='D'
  elif s_[i]=='?' and s[i-1]=='D':
    if s_[i+1]=='D':
      s_[i]='P'
    elif s_[i+1]=='?':
      s_[i]='P'
      s_[i+1]='D'
    else:
      s_[i]='D'
    
S = "".join(s_)
print(S)

### FIXED CODE ###

s = str(input())
s_ = list(s)
for i in range(len(s)):
  if s_[i]=='?':
    s_[i]='D'
S = "".join(s_)
print(S)
print('Odd')if (int(input())*int(input())%2)==1 else print('Even')


### FIXED CODE ###

a,b=map(int,input().split())
print('Odd')if a*b%2==1else print('Even')