Harryxun/stf_run huggingface dataset:
#!/usr/bin/env python3

def main():
    import sys
    def I(): return int(sys.stdin.readline())
    def LI(): return list(map(int,sys.stdin.readline().split()))

    n = I()
    V = []
    W = []

    maxL = 10**5
    m = min(n, 1 << 10)
    dp = [[0]*(maxL + 1)]
    
    for i in range(n):
        v, w = LI()
        if i <= m:
            d_ = dp[(i+1)>>1][:]
            for j in range(w, maxL+1)[::-1]:
                d_[j] = max(d_[j], d_[j - w] + v)
            dp.append(d_)
        V.append(v)
        W.append(w)
    
    q = I()
    for i in range(q):
        v, L = LI()
        if v <= m:
            print(dp[v][L])
            continue
        cnt = 0
        v_ = []
        w_ = []
        while tmp > m:
            v_.append(V[v-1])
            w_.append(W[v-1])
            v >>= 1
            cnt += 1
        ret = dp[v][L]
        v_tmp = [0] * (1 << cnt)
        w_tmp = [0] * (1 << cnt)
        for b in range(1, 1 << cnt):
            lsb = b & -b
            l = lsb.bit_length()
            w_tmp[b] = w_tmp[b - lsb] + w_[l-1]
            if w_tmp[b] <= L:
                v_tmp[b] = v_tmp[b - lsb] + v_[l-1]
                ret = max(ret, v_tmp[b] + dp[v][L - w_tmp[b]])
        print(ret)
    return

if __name__ == "__main__":
    main()


### FIXED CODE ###

#!/usr/bin/env python3

def main():
    import sys
    def I(): return int(sys.stdin.readline())
    def LI(): return list(map(int,sys.stdin.readline().split()))

    n = I()
    V = []
    W = []

    maxL = 10**5
    m = min(n, 1 << 10)
    dp = [[0]*(maxL + 1)]
    
    for i in range(n):
        v, w = LI()
        if i <= m:
            d_ = dp[(i+1)>>1][:]
            for j in range(w, maxL+1)[::-1]:
                d_[j] = max(d_[j], d_[j - w] + v)
            dp.append(d_)
        V.append(v)
        W.append(w)
    
    q = I()
    for i in range(q):
        v, L = LI()
        if v <= m:
            print(dp[v][L])
            continue
        cnt = 0
        v_ = []
        w_ = []
        while v > m:
            v_.append(V[v-1])
            w_.append(W[v-1])
            v >>= 1
            cnt += 1
        ret = dp[v][L]
        v_tmp = [0] * (1 << cnt)
        w_tmp = [0] * (1 << cnt)
        for b in range(1, 1 << cnt):
            lsb = b & -b
            l = lsb.bit_length()
            w_t = w_tmp[b - lsb] + w_[l-1]
            w_tmp[b] = w_t
            if w_t <= L:
                v_t = v_tmp[b - lsb] + v_[l-1]
                v_tmp[b] = v_t
                ret = max(ret, v_t + dp[v][L - w_t])
        print(ret)
    return

if __name__ == "__main__":
    main()
A,B = (int(x) for x in input().split())
a=A//2
d=1
s=0
d=int(d)
for i in range(a): 
  if A%d==0 and B%d==0:
    s=d
  d+=1
print(int(A*(B/s)))


### FIXED CODE ###

A,B = (int(x) for x in input().split())
if A%2==0:
  a=A//2
else:
  a=(A+1)//2  

d=1
s=0
d=int(d)
for i in range(a): 
  if A%d==0 and B%d==0:
    s=d
  d+=1
if s==1 :
  print(int(A*B))
elif B%A==0:
  print(B)
elif A%B==0:
  print(A)

else:
  print(int(A*(B/s)))
import collections

N = int(input())
W = []
jud = 1

for _ in range(N):
    W.append(input())

c = collections.Counter(W)
ct = len(c)

for i in range(N-1):
    fst = W[i]
    fnl = W[i+1]
    if fst[-1] != fnl[1]:
        jud = 0

if ct != N:
    print("No")
elif jud == 0:
    print("No")
else: print("Yes")

### FIXED CODE ###

N = int(input())
ketu = ""
mozi = []
frag = 0
for i in range(N):
    stri = input()
    if (ketu != "" )and(ketu != stri[0]):
        frag = 1

    ketu = stri[-1]
    mozi.append(stri)

if frag == 1:
    print("No")
    exit()

if len(mozi) != len(list(set(mozi))):
    print("No")
    exit()

print("Yes")
n=input()
while 1:
	m=[raw_input().split() for i in range(n)]
	p={}
	for t in m:
		p[t[0]] = 3*int(t[1])+1*int(t[3])
	for k,v in sorted(p.items(),key=lambda x:x[1])[::-1]:
		print "%s,%d"%(k,v)
	c+=1
	n=input()
	if n==0:break
	print

### FIXED CODE ###

n=input()
while 1:
	p={}
	for i in range(n):
		t=raw_input().split()
		p[t[0]] = [3*int(t[1])+1*int(t[3]),-i]
	for k,v in sorted(p.items(),key=lambda x:x[1])[::-1]:
		print "%s,%d"%(k,v[0])
	n=input()
	if n==0:break
	print
n=int(input())

a=[]

for i in range(n):
    b=int(input())
    a.append(b)
    
a.sort()

ans=["" for i in range(n)]

ans[n//2]=a[-1]
a.remove(a[-1])
l=(n//2)-1
r=(n//2)+1
num=0
for i in range(n-1):
    if i%4==0:
        ans[l]=a[0]
        a.remove(a[0])
        num+=abs(ans[l+1]-ans[l])
        l-=1
    elif i%4==1:
        ans[r]=a[0]
        a.remove(a[0])
        num+=abs(ans[r]-ans[r-1])
        r+=1
    elif i%4==2:
        ans[l]=a[-1]
        a.remove(a[-1])
        num+=abs(ans[l+1]-ans[l])
        l-=1
    elif i%4==3:
        ans[r]=a[-1]
        a.remove(a[-1])
        num+=abs(ans[r]-ans[r-1])
        r-=1

ans.append(ans[0]) 
num+=abs(ans[-1]-ans[-2])    

num-=min(abs(ans[0]-ans[1]),abs(ans[-1]-ans[-2]),abs(ans[-2]-ans[-3]))
        
print(num)




### FIXED CODE ###

n=int(input())
l=[]
for i in range(n):
    l.append(int(input()))
l.sort()
if n%2==0:
    ln=l[:n//2]
    lx=l[n//2:]
    print(2*(sum(lx)-sum(ln))-lx[0]+ln[-1])
else:
    ln=l[:n//2]
    lm=l[n//2]
    lx=l[n//2+1:]
    p=sum(lx)
    q=sum(ln)
    print(max(2*(p-q)+ln[-1]-lm,2*(p-q)-lx[0]+lm))
r, c = map(int, input().split())
table = []
for i in range(r):
    table.append(list(map(int, input().split())))
for i in table:
    i.append(sum(i))
b = []
for i in range(c):
    b.append(sum(list(table[i for i in range(r)])))
b.append(sum(b))
for i in table:
    print(" ".join(map(str, i)))
print(" ".join(map(str, b)))


### FIXED CODE ###

r, c = map(int, input().split())
table = []
for i in range(r):
    table.append(list(map(int, input().split())))
for i in table:
    i.append(sum(i))
b = []
for i in range(c):
    x = 0
    for k in range(r):
        x += table[k][i]
    b.append(x)
b.append(sum(b))
for i in table:
    print(" ".join(map(str, i)))
print(" ".join(map(str, b)))
n,k = map(int,input().split())
p = list(input().split())
p.sort()
print(sum(p[0:n]))

### FIXED CODE ###

n,k = map(int,input().split())
p = list(map(int,input().split()))
p.sort()
print(sum(p[0:k]))
def main():
    H, W = map(int, input().split())
    A = [input().split() for h in range(H)]
    cnt = 0
    out = []
    for h in range(H):
        for w in range(W):
            if A[h][w]%2 == 1:
                cnt += 1
                if w < W-1:
                    A[h][w+1] += 1
                    out.append(list(map(str, [h+1, w+1, h+1, w+2])))
                elif h < H-1:
                    A[h+1][w] += 1
                    out.append(list(map(str, [h+1, w+1, h+2, w+1])))
                else:
                    cnt -= 1
    print(cnt)
    for posi in out:
        print(" ".join(posi))


if __name__ == '__main__':
    main()


### FIXED CODE ###

H, W = map(int, input().split())
a = [list(map(int, input().split())) for _ in range(H)]
ans = []

for h in range(H-1):
	for w in range(W-1):
		if a[h][w] % 2 == 1:
			ans.append([h+1, w+1, h+1, w+2])
			a[h][w+1] += 1
	if a[h][-1] % 2 == 1:
		ans.append([h+1, W, h+2, W])
		a[h+1][-1] += 1

for w in range(W-1):
	if a[H-1][w] % 2 == 1:
		ans.append([H, w+1, H, w+2])
		a[H-1][w+1] += 1

print(len(ans))
for an in ans:
	print(*an)
n=int(input())
list=filter(lambda x:x%2==1,range(1,n+1))
print(list.count())

### FIXED CODE ###

n=int(input())
if n<10:
  print(n)
elif n<100:
  print(9)
elif n<1000:
  print(n-90)
elif n<10000:
  print(909)
elif n<100000:
  print(n-9999+909)
else:
  print(90909)
N = input()
h = map(int,input().split())
h = list(h)

dp = [99999999 for i in range(100)]
dp[0]=0

for i in range(int(N)):
    for j in range(i+1,i+2):
        if j<int(N) :
            dp[j]=min(dp[j],dp[i]+abs(h[i]-h[j]))

print(dp[int(N)-1])

### FIXED CODE ###

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

dp = [sys.maxsize]*n
dp[0]=0

for i in range(n):
    for j in range(i+1,i+2+1):
        if j<n :
            dp[j]=min(dp[j],dp[i]+abs(h[i]-h[j]))

print(dp[n-1])
# 0:a, b, c, a-b
# 1:b+c, a+c, a+b, b-a
# 2:2a+b+c, a+2b+c, a+b+2c, a-b
# 3:2a+3b+3c, 3a+2b+3c, 3a+3b+2c, b-a
# 4:6a+5b+5c, 5a+6b+5c, 5a+5b+6c, a-b
A, B, C, K = [int(x) for x in input().strip().split()]
ans = (a-b)*-1**(K%2)
if ans > 10 ** 18:
  print('Unfair')
else:
  print(ans)
  

### FIXED CODE ###

# 0:a, b, c, a-b
# 1:b+c, a+c, a+b, b-a
# 2:2a+b+c, a+2b+c, a+b+2c, a-b
# 3:2a+3b+3c, 3a+2b+3c, 3a+3b+2c, b-a
# 4:6a+5b+5c, 5a+6b+5c, 5a+5b+6c, a-b
A, B, C, K = [int(x) for x in input().strip().split()]
ans = (A-B)*(-1)**(K%2)
if ans > 10 ** 18:
  print('Unfair')
else:
  print(ans)
N, K = map(int, input().split())
price = [input() for _ in range(N)]
price.sort()
print(sum(price[:3]))

### FIXED CODE ###

N, K = map(int, input().split())
price = list(map(int, input().split()))
price.sort()
print(sum(price[:K]))
import math
I = input().split()
A = int(I[0])
B = int(I[1])
N = int(I[2])
def fl(x):
    return math.floor((A*x)/B) - A*math.floor(x/B)

An = fl(N)

if A == 1 and B == 1 :
    An = int(0)

if B < N :
    for i in range(B,N) :
        if i >= B+1 and fl(i) <= fl(i-1) :
            An = fl(i-1)
            break
elif B == N :
    An = fl(N-1)

print(str(An))

### FIXED CODE ###

I = [input() for i in range(2)]
K = int(I[0])
S = I[1].split()
A = int(S[0])
B = int(S[1])

na = A//K
nb = B//K

la = A%K
lb = B%K

#print(na)
#print(nb)

if na < nb or la == 0 or lb == 0 :
    ans = 'OK'
else:
    ans = 'NG'

print(ans)
N,M,S=map(int,input().split())

ways=[[] for _ in range(N)]
CD=[[0]*2 for _ in range(N)]

class Way:
  def __init__(self,t,f,ti):
    self.to=t
    self.fare=f
    self.time=ti 

for i in range(M):
  U,V,A,B=map(int,input().split())
  U-=1
  V-=1
  ways[U].append(Way(V,A,B))
  ways[V].append(Way(U,A,B))

for i in range(N):
  C,D=map(int,input().split())
  CD[i][0]=C
  CD[i][1]=D
  
#dp[i][j]:駅iにおいて銀貨をj枚所持するための最短時間
dp=[[float("inf")]*(50*N+1) for _ in range(N)]
dp[0][S]=0
import heapq

#data型は(時間、駅、お金)
#q=heapq.heapify([(0,0,S)])
#q=heapq.heapify([])
q=[]
heapq.heappush(q,(0,0,S))
#print(q)
def Push(time,station,money):
  #print("called")
  global q,dp
  if money<0:
    return
  money=min(money,50*N)
  if dp[station][money] <= time:
    return
  dp[station][money] = time
  heapq.heappush(q,(time,station,money))

while q:
  #print("called!")
  dat = heapq.heappop(q)
  time,station,money=dat[0],dat[1],dat[2]
  
  if dp[station][money]!=time:
    continue
  #まず、両替。
  Push(time+CD[station][1],station,money+CD[station][0])
  #次に、各道について移動
  for w in ways[station]:
    Push(time+w.time,w.to,money-w.fare)

for i in range(1,N):
  ans=float("inf")
  for j in range(50*N+1):
    ans=min(ans,dp[i][j])
  print(ans)
    

  
  

### FIXED CODE ###

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

ways=[[] for _ in range(N)]
CD=[[0]*2 for _ in range(N)]

class Way:
  def __init__(self,t,f,ti):
    self.to=t
    self.fare=f
    self.time=ti 

for i in range(M):
  U,V,A,B=map(int,input().split())
  U-=1
  V-=1
  ways[U].append(Way(V,A,B))
  ways[V].append(Way(U,A,B))

for i in range(N):
  C,D=map(int,input().split())
  CD[i][0]=C
  CD[i][1]=D
  
#dp[i][j]:駅iにおいて銀貨をj枚所持するための最短時間
dp=[[float("inf")]*(50*N+1) for _ in range(N)]
S=min(S,50*N)
dp[0][S]=0
import heapq

#data型は(時間、駅、お金)
#q=heapq.heapify([(0,0,S)])
#q=heapq.heapify([])
q=[]
heapq.heappush(q,(0,0,S))
#print(q)
def Push(time,station,money):
  #print("called")
  global q,dp
  if money<0:
    return
  money=min(money,50*N)
  if dp[station][money] <= time:
    return
  dp[station][money] = time
  heapq.heappush(q,(time,station,money))

while q:
  #print("called!")
  dat = heapq.heappop(q)
  time,station,money=dat[0],dat[1],dat[2]
  
  if dp[station][money]!=time:
    continue
  #まず、両替。
  Push(time+CD[station][1],station,money+CD[station][0])
  #次に、各道について移動
  for w in ways[station]:
    Push(time+w.time,w.to,money-w.fare)

for i in range(1,N):
  ans=float("inf")
  for j in range(50*N+1):
    ans=min(ans,dp[i][j])
  print(ans)
N = int(input())
if N[len(N)-1] == 2 or 4 or 5 or 7 or 9 :
    print('hon')
elif N[len(N)-1] == 0 or 1 or 6 or 8 :
    print('pon')
else :
    print('bon')

### FIXED CODE ###

N = input()
n = int(N[len(N)-1] )
if n == 0 or n == 1 or n ==  6 or n == 8   :
    print('pon')
elif n == 2 or n == 4 or n == 5 or n == 7 or n == 9 :
    print('hon')
elif n == 3 :
    print('bon')
m=int(input())
h=list(map(int,input().split()))
ans1=[]
ans=0
for x in range(m-1):
  if h[x]<h[x+1]:
    ans1.append(ans)
    ans=0
  else:
    ans+=1
    ans1.append(ans)
    
  
    
print(max(ans1))

### FIXED CODE ###

m=int(input())
h=list(map(int,input().split()))
ans1=[]
ans=0
if m>1:
  
  for x in range(m-1):
    if h[x]<h[x+1]:
      ans1.append(ans)
      ans=0
    else:
      ans+=1
      ans1.append(ans)
    
  
    
  print(max(ans1))

else:
  print(0)
import sys

input = sys.stdin.readline

def hantei(i, oya=-1):
    if ans[i] != -1:
        return ans[i]
    for u, w in pea[i]:
        if u == oya: continue
        if hantei(u, i):
            re = ans[i] = (hantei(u, i) + w) % 2
            return re

n = int(input())
pea = [[] for _ in range(n + 1)]
for _ in range(n - 1):
    u, v, w = map(int, input().split())
    w %= 2
    pea[u].append([v, w])
    pea[v].append([u, w])
ans = [-1] * (n + 1)
ans[1] = 1
for i in range(1, n + 1):
    print(hantei(i))


### FIXED CODE ###

n = int(input())
pea = [[] for _ in range(n + 1)]
for _ in range(n - 1):
    u, v, w = map(int, input().split())
    w %= 2
    pea[u].append([v, w])
    pea[v].append([u, w])
ans = [-1] * (n + 1)
ans[1]=1
nodes=[1]
used=set()
used.add(1)
ansi=1
while nodes:
    nn=[]
    for i in nodes:
        ansi=ans[i]
        for u,w in pea[i]:
            if u in used:continue
            ans[u]=(ansi+w)%2
            used.add(u)
            nn+=[u]
    nodes=nn
for x in ans[1:]:
    print(x)
H, W = map(int, input().split())
graph = []
for _ in range(H):
    graph.append([0 if e == '.' else 1 for e in list(input())])

xx = [-1, 0, 1, 0]
yy = [0, -1, 0, 1]


def isValidTransition(x, y, H, W):
    return 0 <= x and x < W and 0 <= y and y < H

res = True

for i in range(W):
    for j in range(i, H):
        if graph[i][j] == 1:
            flag = False
            for idx in range(4):
                nx, ny = i + xx[idx], j + yy[idx]
                if isValidTransition(nx, ny, H, W) and graph[nx][ny] == 1:
                    flag = True
            if not flag:
                res = False
                break
    if not res:
        break

print('Yes' if res else 'No')


### FIXED CODE ###

H, W = map(int, input().split())
graph = []
for _ in range(H):
    graph.append(list(input()))

res = True

for j in range(1, W-1):
    for i in range(1, H-1):
        if graph[i][j] == '#' and graph[i + 1][j] == '.' and graph[i - 1][j] == '.' and graph[i][j + 1] == '.' and graph[i][j - 1] == '.':
            print('No')
            exit()
print('Yes')
args = map(int, input().split())
N = args[0]
A = [a for (i,a) in enumerate(args[1:]) if i%2==1]
B = [b for (i,b) in enumerate(args[1:]) if i%2==0]

A = sorted(A)
B = sorted(B)

if N%2==1:
	print(B[N//2] - A[N//2] + 1)
else:
	print( (B[N//2-1]+B[N//2]) - (A[N//2-1]+A[N//2]) + 1 )

### FIXED CODE ###

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

A = sorted(A)
B = sorted(B)
 
if N%2==1:
  print(B[N//2] - A[N//2] + 1)
else:
  print( (B[N//2-1]+B[N//2]) - (A[N//2-1]+A[N//2]) + 1 )
N=int(input())
li = list(map(int,input().split()))

for i in li:
  if i%2 ==0:
    if i%3 == 0 or i%5 == 0:
      a
    else:
      print('DENIED')
      break
  print('APPROVED')

### FIXED CODE ###

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

if A==B and B==C:
  print('No')
elif A != B and B != C and C != A:
  print('No')
else:
  print('Yes')
W,H,x,y,r=map(int,input().split())
if 0 < x + r <= W and r < x:
  if 0 < y + r <= H:
    print("Yes")
  else:
    Print("No")
else:
  print("No")

### FIXED CODE ###

W,H,x,y,r=map(int,input().split())
if r <= x and r <= y and x+r <= W and y+r <= H:
  print("Yes")
else:
  print("No")
H, N = map(int, input().split())
A = list(map(int, input().split()))
if H <= sum(A):
  print ('Yse')
else:
  print ('No')

### FIXED CODE ###

#a,b = map(int, input().split())
import math
if __name__ == "__main__":
    H,A = map(int,input().split())
    print(math.ceil(H / A))
x = input().split()
S = list(x[0])
T = list(x[1])
n = 0
n = len(S) - len(T) + 1
min = t
 
for a in range(n):
  count = 0 
	for b in range(len(T)):
      if S[a+b] != T[b]:
        count += 1
  if count < min:
    min = count
print(min)


### FIXED CODE ###

x = [input() for i in range(2)]
S = x[0]
T = x[1]
moji = len(T)

for a in range(len(S) - len(T) + 1):
  count = 0
  for b in range(len(T)):
    
    if S[a+b] != T[b]:
      count += 1
  if count < moji:
    moji = count

print(moji)
from heapq import heappush, heappop

N = int(input())
A = [int(input()) for i in range(N)]
hq = []
for i in range(N):
    heappush(hq, -A[i])
max1 = -heappop(hq)
while True:
    max2 = -heappop(hq)
    if max2 != max1:
        break
ans = [0] * N
for i in range(N):
    if A[i] == max1:
        ans[i] = max2
    else:
        ans[i] = max1
print(*ans, sep="\n")


### FIXED CODE ###

from heapq import heappush, heappop

N = int(input())
A = [int(input()) for i in range(N)]
hq = []
for i in range(N):
    heappush(hq, -A[i])
max1 = -heappop(hq)
max2 = -heappop(hq)
ans = [0] * N
for i in range(N):
    if A[i] == max1:
        ans[i] = max2
    else:
        ans[i] = max1
print(*ans, sep="\n")
n=int(input())
List = [int(i) for i in input().split()]
List2=sorted(List)
ans = 0

for i in range(1,n-1): #aにたいし
  for j in range(i,n):
    tmp1 = List[i]
    tmp2 = List[j]
    
    ans += 4- bisect.bisect_right(List2,tmp1+tmp2)
    
print(ans)


### FIXED CODE ###

import bisect
n=int(input())
List = [int(i) for i in input().split()]
List2=sorted(List)
ans = 0

for i in range(0,n-1): #aにたいし
  for j in range(i+1,n):
    #print(i,j)
    tmp1 = List2[i]
    tmp2 = List2[j]
    
    a=bisect.bisect_left(List2,tmp1+tmp2)
    ans += a -j-1
    #print(a,List2,tmp1,tmp2,j,ans)
print(ans)
x = input()
inputs = x.split()
a, b, c = int(inputs[0]), int(inputs[1]), int(inputs[2])
if a == b and b == c:
  return 'Yes'
else:
  return 'No'

### FIXED CODE ###

x = input()
inputs = x.split()
a, b, c = int(inputs[0]), int(inputs[1]), int(inputs[2])

if a == b and b == c:
    print('Yes')
else:
    print('No')
n = int(input())
v = map(int,input().split())
c = map(int,input().split())
cnt = 0
for i in range(n):
    if v[i] > c[i]:
        cnt += (v[i] - c[i])
    else:
        cnt += 0    
print(cnt)

### FIXED CODE ###

n = int(input())
v = list(map(int,input().split()))
c = list(map(int,input().split()))
cnt = 0
for i in range(n):
    if v[i] > c[i]:
        cnt += (v[i] - c[i])
print(cnt)
N,M = map(int,input().split())
one = []
nnn = []
for i in range(M):
    ai,bi = map(int,input().split())
    if ai == 1:
        one.append(bi)
    if bi == N:
        nnn.append(ai)
def bs_left(l, target): # l=sorted, target以上の値をもつ要素のうち一番左のindexを返す
    low, high = 0, len(l)
    while low < high:
        mid = (low+high)//2
        if l[mid] < target:
            low = mid+1
        else:
            high = mid
    return low
flag = False
if len(one) == 0 or len(nnn) == 0:
    pass
else:
    nnn.sort()
    for i in range(len(one)):
        if nnn[bs_left(nnn,one[i])] == one[i]:
            flag = True
            break

if flag:
    print('POSSIBLE')
else:
    print('IMPOSSIBLE')

### FIXED CODE ###

N,M = map(int,input().split())
one = []
nnn = []
for i in range(M):
    ai,bi = map(int,input().split())
    if ai == 1:
        one.append(bi)
    if bi == N:
        nnn.append(ai)
def bs_left(l, target): # l=sorted, target以上の値をもつ要素のうち一番左のindexを返す
    low, high = 0, len(l)
    while low < high:
        mid = (low+high)//2
        if l[mid] < target:
            low = mid+1
        else:
            high = mid
    if low == len(l):
        return -1
    return low
flag = False
if len(one) == 0 or len(nnn) == 0:
    pass
else:
    nnn.sort()
    for i in range(len(one)):
        if nnn[bs_left(nnn,one[i])] == one[i]:
            flag = True
            break

if flag:
    print('POSSIBLE')
else:
    print('IMPOSSIBLE')
if __name__ == '__main__':
	input_a = input()
	input_b = input()
	a = 2*input_a+2*input_b
	b = input_a*input_b
	print b, a

### FIXED CODE ###

n, m = map(int, raw_input().split())
print n*m, 2*n+2*m
s = list(int(input()))
print(s.count(1))

### FIXED CODE ###

s = list(input())
print(s.count('1'))
#154
N = int(input())
A = [int(input()) for i in range(N)]
A_set = set(A)
if(len(A)==len(A_set)):
    print('YES')
else:
    print('NO')

### FIXED CODE ###

#154
N = int(input())
A = list(map(int,input().split()))
A_set = set(A)
if(len(A)==len(A_set)):
    print('YES')
else:
    print('NO')
import math
n = int(input())
c = []
s = []
f = []
for i in range(n):
  x,y,z = map(int, input().split())
  c += [x]
  s += [y]
  f += [z]
  
for i in range(n):
  ans = s[i]+c[i]
  for j in range(i+1, n):
    ans = (ans//f[j]) * math.ceil(ans/f[j]) + c[j]
  print(ans)

### FIXED CODE ###

import math

n = int(input())
c = []
s = []
f = []
for i in range(n - 1):
    x, y, z = map(int, input().split())
    c += [x]
    s += [y]
    f += [z]

for i in range(n - 1):
    ans = s[i] + c[i]
    for j in range(i + 1, n-1):
        if ans < s[j]:
            ans = s[j] + c[j]
        else:
            ans = f[j] * math.ceil(ans / f[j]) + c[j]
    print(ans)
print(0)
1<=X<=9
X=input("age")
if X=3 or X=5 or X=7:
  print("Yes")
else:
  print("No")

### FIXED CODE ###

x = int(input())

if x==7 or x==5 or x==3 :
    print("YES")

else :
    print("NO")
S = list(input())
S = set(S)
for i in range(26):
  if not(chr(97+i) in S):
    ans = chr(97+i)
    break
print(ans)


### FIXED CODE ###

S = list(input())
S = set(S)
ans = "None"
for i in range(26):
  if not(chr(97+i) in S):
    ans = chr(97+i)
    break
print(ans)
import re
import math

def fib(n):
    if n == 1:
        return 0
    elif n == 2:
        return 1
    else:
        return fib(n-1)+fib(n-2)

n,m = map(int, input().split())
step = ['0']*(n+1)
for i in range(m):
    a = int(input())
    step[a] = '1'
steps = ''.join(step)

a = re.findall('0+', steps)
b = len(re.findall('11', steps))
# print(steps)
count = 1
for i in a:
    count *= fib(len(i)+1) % 1000000007

if b != 0:
    print(0)
else:
    print(round(count % 1000000007))


### FIXED CODE ###

import re
import math

def fib(n):
    a, b = 0, 1
    if n == 1:
        return a
    elif n == 2:
        return b
    else:
        for i in range(n-2):
            a, b = b, a + b
        return b

n,m = map(int, input().split())
step = ['0']*(n+1)
for i in range(m):
    a = int(input())
    step[a] = '1'
steps = ''.join(step)

a = re.findall('000*', steps)
b = len(re.findall('11', steps))
# print(steps)
count = 1
for i in a:
    count *= fib(len(i)+1) % 1000000007

if b != 0:
    print(0)
else:
    print(count % 1000000007)
N,K = map(int,input().split())
import math
s = 0
for i in range(1,N+1):
    if i >= K:
        s += 1
    else:
        n = math.ceil(log((K/i),2))
        s += 2**(-n)
ans = s/N
print(ans)

### FIXED CODE ###

N,K = map(int,input().split())
import math
s = 0
for i in range(1,N+1):
    if i >= K:
        s += 1
    else:
        n = math.ceil(math.log((K/i),2))
        s += 2**(-n)
ans = s/N
print(ans)
a = list(map(int,input().split()))
x = int(x[1])

print(x[0]x[1]x[2])

### FIXED CODE ###

a,o,b=input().split()
a=int(a)
b=int(b)
print(a+b if o=="+" else a-b)
import copy
input()
a=[int(i) for i in input().split()]
sa=copy.copy(a)
for i in range(len(a)):
    sa[i]=sa[i]-(i+1)
sa.sort()
msa=sa[int(len(sa)/2)]
sb=0
for i in range(len(a)):
    sb=sb+abs(a[i]-(sma+i+1))
print(sb)

### FIXED CODE ###

N=int(input())
if N/2==N//2:
    print(N)
else:
    print(N*2)
n, k = map(int, input().split())
check = 0
ans = []
for i in range(n):
  a, b = map(int, input().split())
  check += b
  ans.append(str(a)*b)
  if check <= k:
    ans = "".join(ans)
    print(ans[k-1])
    break 


### FIXED CODE ###

N, K = map(int, input().split())
ans = 0
memory = [0]*(10**5+1)

for i in range(N):
    a, b = map(int, input().split())
    memory[a] += b

for i in range(10**5+1):
    ans += memory[i]
    if ans >= K:
        print(i)
        break