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

import sys, math, itertools, collections, bisect 
input = lambda: sys.stdin.buffer.readline().rstrip().decode('utf-8') 
inf = float('inf') ;mod = 10**9+7 
mans = inf ;ans = 0 ;count = 0 ;pro = 1

import sys, math, itertools, collections, bisect 
input = lambda: sys.stdin.buffer.readline().rstrip().decode('utf-8') 
inf = float('inf') ;mod = 10**9+7 
mans = inf ;ans = 0 ;count = 0 ;pro = 1
 
n, k = map(int, input().split())
A = list(map(int, input().split()))
now = 1
for i in range(k):
    now *= A[k-1-i]
for i in range(k-1, n):
    #print(A[i])
    if i == k-1:
        before = now
    else:
        now = now//A[i-k]
        now *= A[i]
        #print(A[i-k], A[i], now, before)
        if before < now:
            print("Yes")
        else:
            print("No")
        before = now

### FIXED CODE ###

import sys, math, itertools, collections, bisect 
input = lambda: sys.stdin.buffer.readline().rstrip().decode('utf-8') 
inf = float('inf') ;mod = 10**9+7 
mans = inf ;ans = 0 ;count = 0 ;pro = 1

import sys, math, itertools, collections, bisect 
input = lambda: sys.stdin.buffer.readline().rstrip().decode('utf-8') 
inf = float('inf') ;mod = 10**9+7 
mans = inf ;ans = 0 ;count = 0 ;pro = 1
 
n, k = map(int, input().split())
A = list(map(int, input().split()))
for i in range(k-1, n):
    if i == k-1:
        continue
    else:
        if A[i] > A[i-k]:
            print("Yes")
        else:
            print("No")
        #print(A[i], A[i-k])
### BUGGY CODE ###

n = input()
data = input()

w = []
r = []
for i in range(len(data)):
  if data[i] == "W":
    w.append(i)
  else:
    r.append(i)

ans = 0
if len(w) == 0:
  print(ans)
elif len(r) == 0:
  print(ans)
else:
  r = r[::-1]
  for i in range(len(data)):
    tmp_w = w.pop(0)
    tmp_r = r.pop(0)
    if tmp_w <= tmp_r:
      r.append(tmp_w)
      w.append(tmp_r)
      ans += 1
    else:
      print(ans)
      break

### FIXED CODE ###

n = input()
data = input()

w = []
r = []
for i in range(len(data)):
  if data[i] == "W":
    w.append(i)
  else:
    r.append(i)

ans = 0
if len(w) == 0:
  print(ans)
elif len(r) == 0:
  print(ans)
else:
  r = r[::-1]
  for i in range(min(len(w), len(r))):
    tmp_w = w[i]
    tmp_r = r[i]
    if tmp_w <= tmp_r:
      r.append(tmp_w)
      w.append(tmp_r)
      ans += 1
    else:
      break
  print(ans)
### BUGGY CODE ###

n = int(input())
a = list(map(int,input().split()))
b = []
for i in range(n):
    b.append(a.index(i+1)+1)

print(*b)

### FIXED CODE ###

n = int(input())
a = list(map(int,input().split()))
d = dict()
for i in range(n):
    d[a[i]] = i+1

ans = []

for j in range(n):
    ans.append(d.get(j+1))

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

n = int(input())
a = [int(input()) for i in range(n)]
cnt=0
while len(a)>0:
  cnt+=1
  nokori=[]
  tmp = a[0]
  for i in range(1,len(a)):
    if tmp<a[i]:
      tmp=a[i]
    else:
      nokori.append(a[i])
  a = nokori
print(cnt)

### FIXED CODE ###

import bisect
n = int(input())
a = [- int(input()) for i in range(n)]
tmp = [a[0]]
for i in range(1,n):
  idx=bisect.bisect_right(tmp,a[i])
  if idx==len(tmp):
    tmp.append(a[i])
  else:
    tmp[idx] =a[i]
print(len(tmp))
### BUGGY CODE ###

import numpy as np
from sys import stdin
input = stdin.readline

n = int(input().rstrip())
a_row = list(map(int, input().rstrip().split()))

a = np.array(a_row)
MOD = 1000000007
ans = 0

for i in range(n-1):
    ans += (a[i] % MOD) * (np.sum(a[i+1:n]) % MOD)
    ans = ans % MOD

print(ans)

### FIXED CODE ###

from sys import stdin
input = stdin.readline

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

MOD = 1000000007
ans = 0

k = 0
s = [0] * n
for i in range(n-1, 0, -1):
    k += a[i] % MOD
    s[i] = k

for i in range(n-1):
    ans += a[i] * s[i+1]

ans = ans % MOD

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

import heapq

n, m = map(int, input().split())
a = sorted(list(map(int, input().split())))
bc = sorted([list(map(int, input().split())) for _ in range(m)], key=lambda x: x[1])

for b, c in bc:
    for i in range(b):
        d = heapq.heappop(a)
        if d < c:
            heapq.heappush(a, c)
        else:
            heapq.heappush(a, d)
            break
print(sum(a))

### FIXED CODE ###

import numpy as np

n, m = map(int, input().split())
a = np.array(sorted(list(map(int, input().split()))), dtype=np.int64)
bc = sorted([list(map(int, input().split())) for _ in range(m)], key=lambda x: -x[1])

p = 0
for b, c  in bc:
    a[p:p+b] = np.maximum(a[p:p+b], c)
    p += b
print(np.sum(a))
### BUGGY CODE ###

def main():
    import numpy as np
    import sys
    from collections import deque

    n,m = map(int,input().split())
    ab = [[int(i) for i in input().split()] for i in range(m)]
    abl=[[] for i in range(n)]
    for i in range(len(ab)):
        abl[ab[i][0]-1].append(ab[i][1])
        abl[ab[i][1]-1].append(ab[i][0])

    an=[0]*(n-1)
    i=1
    wk=deque([i])
    wwk=deque([])
    il=deque(abl[0])

    while any(wk):
        i=wk.pop()
        il=deque(abl[i-1])
        while any(il):
            iwk=il.pop()
            if an[iwk-2]==0 and iwk>1:
                wwk.append(iwk)
                an[iwk-2]=i
                if all(an):
                    print('Yes')
                    for i in an:
                        print(i)
                    sys.exit()
        if not(any(wk)):
            wk=deque(wwk)
            wwk=deque([])
    print('No')

main()

### FIXED CODE ###

def main():
    from collections import deque
 
    n,m =map(int,input().split())
    abl=[[] for i in range(n+1)]
    for i in range(m):
        a,b = map(int,input().split())
        abl[a].append(b)
        abl[b].append(a)
 
    an=[0]*(n+1)
    an[0]=1
    tg = deque([1])
    while len(tg):
        itg = tg.popleft()
        for j in abl[itg]:
            if an[j]==0:
                an[j]=itg
                tg.append(j)

    if all(an):
        print('Yes')
        for j in an[2:]:
            print(j)
    else:
        print('No')
 
main()
### BUGGY CODE ###

def searchstar(i,j):
    global vector
    global star
    global n
    flag = False
    for k in range(n):
        if star[i][0] + vector[j][0] == star[k][0] and star[i][1] + vector[j][1] == star[k][1]:
            flag = True
            break
    return flag

while True:
    m = int(input())
    if m==0: break

    vector = []

    x1,y1 = map(int, input().split())
    for i in range(m-1):
        x2,y2 = map(int, input().split())
        vector.append([x2-x1,y2-y1])

    star = []
    n = int(input())
    for i in range(n):
        a,b = map(int, input().split())
        star.append([a,b])

    for i in range(n):
        for j in range(m-1):
            if not searchstar(i, j):
                break
        else:
            print(star[i][0] - x1, star[i][1] - y1)
            break

### FIXED CODE ###

def searchstar(i,j):
    global vector
    global star
    global n
    flag = False
    for k in range(n):
        if star[i][0] + vector[j][0] == star[k][0] and star[i][1] + vector[j][1] == star[k][1]:
            flag = True
            break
    return flag

while True:
    m = int(input())
    if m==0: break

    vector = []

    x1,y1 = map(int, input().split())
    for i in range(m-1):
        x2,y2 = map(int, input().split())
        vector.append([x2-x1,y2-y1])

    star = []
    n = int(input())
    for i in range(n):
        a,b = map(int, input().split())
        star.append([a,b])

    for i in range(n-1,-1,-1):
        for j in range(m-1):
            if not searchstar(i, j):
                break
        else:
            print(star[i][0] - x1, star[i][1] - y1)
            break
### BUGGY CODE ###

N=int(input())
X=input()
f={}
for i in range(N):
    x=''
    for j in range(N):
        if i == j:
            x+='1'
        else:
            x+='0'
    y=int(X,2) ^ int(x,2)
    if y in f:
        print(f[y])
    else:
        ans = 0
        while y!=0:
            y = y % bin(y).count('1')
            ans += 1
        print(ans)
        f[y]=ans

### FIXED CODE ###

N=int(input())
X=input()
popcount=X.count('1')
bi1=[]
bi0=[]
Xnum1 = 0
Xnum0 = 0
if popcount != 1:
    for i in range(N):
        if i==0: bi1.append(1)
        else: bi1.append(bi1[i-1]*2%(popcount-1))
        Xnum1 = (Xnum1 + int(X[N-i-1])*bi1[i])%(popcount-1)
for i in range(N):
    if i==0: bi0.append(1)
    else: bi0.append(bi0[i-1]*2%(popcount+1))
    Xnum0 = (Xnum0 + int(X[N-i-1])*bi0[i])%(popcount+1)
for i in range(N):
    if popcount==1 and X[i]=='1':
        print(0)
        continue
    if X[i]=='1':
        Xi = (Xnum1 - bi1[N-i-1])%(popcount-1)
    else:
        Xi = (Xnum0 + bi0[N-i-1])%(popcount+1)
    ans = 1
    while Xi!=0:
        Xi = Xi % bin(Xi).count('1')
        ans += 1
    print(ans)
### BUGGY CODE ###

from collections import deque

h, w = map(int, input().split())
cx, cy = map(lambda x: int(x) - 1, input().split())
dx, dy = map(lambda x: int(x) - 1, input().split())
s = [input() for _ in range(h)]
c = [[10**6] * w for _ in range(h)]


def bfs():
    d = ((1, 0), (-1, 0), (0, 1), (0, -1))
    q = deque([(cx, cy)])

    c[cx][cy] = 0

    while q:
        x, y = q.popleft()
        cp = c[x][y]
        if (x, y) == (dx, dy):
            c[x][y] = cp
            break
        for i, j in d:
            nx = x + i
            ny = y + j
            if 0 <= nx < h and 0 <= ny < w and s[nx][ny] != "#" and c[nx][
                    ny] > cp:
                q.appendleft((nx, ny))
                c[nx][ny] = cp
        cp += 1
        for i in range(-2, 3):
            for j in range(-2, 3):
                nx = x + i
                ny = y + j
                if 0 <= nx < h and 0 <= ny < w and s[nx][ny] != "#" and c[nx][
                        ny] > cp:
                    c[nx][ny] = cp
                    q.append((nx, ny))

    return -1 * (c[dx][dy] == 10**6) or c[dx][dy]


print(bfs())


### FIXED CODE ###

#!/usr/bin/env python3
import heapq

h, w = map(int, input().split())
cx, cy = map(lambda x: int(x) - 1, input().split())
dx, dy = map(lambda x: int(x) - 1, input().split())
s = [input() for _ in range(h)]
c = [[10**6] * w for _ in range(h)]


def bfs():
    d = ((1, 0), (-1, 0), (0, 1), (0, -1))
    d2 = (
        (-2, -2),
        (-2, -1),
        (-2, 0),
        (-2, 1),
        (-2, 2),
        (-1, -2),
        (-1, -1),
        (-1, 1),
        (-1, 2),
        (0, -2),
        (0, 2),
        (1, -2),
        (1, -1),
        (1, 1),
        (1, 2),
        (2, -2),
        (2, -1),
        (2, 0),
        (2, 1),
        (2, 2),
    )
    hp = []

    heapq.heappush(hp, (0, (cx, cy)))
    c[cx][cy] = 0

    while hp:
        cp, (
            x,
            y,
        ) = heapq.heappop(hp)
        if (x, y) == (dx, dy):
            c[x][y] = cp
            break
        for i in range(4):
            nx = x + d[i][0]
            ny = y + d[i][1]
            if 0 <= nx < h and 0 <= ny < w and s[nx][ny] != "#" and c[nx][
                    ny] > cp:
                heapq.heappush(hp, (cp, (nx, ny)))
                c[nx][ny] = cp
        cp += 1
        for i in range(20):
            nx = x + d2[i][0]
            ny = y + d2[i][1]
            if 0 <= nx < h and 0 <= ny < w and s[nx][ny] != "#" and c[nx][
                    ny] > cp:
                c[nx][ny] = cp
                heapq.heappush(hp, (cp, (nx, ny)))

    return c[dx][dy] if c[dx][dy] < 10**6 else -1


print(bfs())
### BUGGY CODE ###

#reference Segment-Tree code from:https://ikatakos.com/pot/programming_algorithm/data_structure/segment_tree

def bisect(pos):
  l=-1
  r=n
  while r-l!=1:
    mid=(l+r)//2
    if arr[mid][0]>=pos:
      r=mid
    else:
      l=mid
  return r

mod=998244353
n=int(input())
arr=[list(map(int,input().split())) for _ in range(n)]
arr=sorted(arr,key=lambda x:x[0])
poss=[]
for i in range(n):
  poss.append(bisect(arr[i][0]+arr[i][1]))
poss.append(n)

offset=2**((n-1).bit_length())
st=[0]*(2*offset)

def update(pos,x):
  pos+=offset
  st[pos]=x
  while pos>1:
    y=st[pos^1]
    if x<=y:
      break
    pos>>=1
    st[pos]=x

def get_max(l,r):
  ret=0
  l+=offset
  r+=offset
  while l<r:
    if r&1:
      ret=max(ret,st[r-1])
    if l&1:
      ret=max(ret,st[l])
      l+=1
    l>>=1
    r>>=1
  return ret

for i in range(n):
  update(i,poss[i])
for i in range(n-1,-1,-1):
  poss[i]=get_max(i,poss[i])
  update(i,poss[i])

dp=[0]*(n+1)
dp[-1]=1
for i in range(n-1,-1,-1):
  dp[i]+=dp[i+1]
  dp[i]%=mod
  pos=poss[i]
  dp[i]+=dp[pos]
  dp[i]%=mod
print(dp[0]%mod)

### FIXED CODE ###

#reference Segment-Tree code from:https://ikatakos.com/pot/programming_algorithm/data_structure/segment_tree

def bisect(pos):
  l=-1
  r=n
  while r-l!=1:
    mid=(l+r)//2
    if arr[mid][0]>=pos:
      r=mid
    else:
      l=mid
  return r

mod=998244353
n=int(input())
arr=[list(map(int,input().split())) for _ in range(n)]
arr=sorted(arr,key=lambda x:x[0])
poss=[]
for i in range(n):
  poss.append(bisect(arr[i][0]+arr[i][1]))
poss.append(n)

offset=2**((n-1).bit_length())
st=[0]*(2*offset)

def update(pos,x):
  pos+=offset
  st[pos]=x
  while pos>1:
    y=st[pos^1]
    if x<=y:
      break
    pos>>=1
    st[pos]=x

def get_max(l,r):
  ret=0
  l+=offset
  r+=offset
  while l<r:
    if r&1:
      ret=max(ret,st[r-1])
    if l&1:
      ret=max(ret,st[l])
      l+=1
    l>>=1
    r>>=1
  return ret

for i in range(n):
  update(i,poss[i])
for i in range(n-1,-1,-1):
  poss[i]=get_max(i,poss[i])
  update(i,poss[i])

dp=[0]*(n+1)
dp[-1]=1
for i in range(n-1,-1,-1):
  dp[i]+=dp[i+1]
  dp[i]%=mod
  pos=poss[i]
  dp[i]+=dp[pos]
  dp[i]%=mod
print(dp[0]%mod)
### BUGGY CODE ###




n,k = map(int,input().split())
a = [0 for _ in range(n)]
b = [0 for _ in range(n)]
c = [[0 for _ in range(n)] for _ in range(n)]

for i in range(n - 1):
	A,B = map(int,input().split())
	a[i] = A
	b[i] = B
	c[A - 1][B - 1] = 1
	c[B - 1][A - 1] = 1

pat = k
pat_arr = [0 for _ in range(n)]
pat_arr[0] = k
queue = [0]

while(queue):
	pos = queue.pop(0)
	num = k-2
	if(pos == 0):num += 1
	
	for i in range(n):
		if(c[pos][i] == 0 or pat_arr[i] != 0):continue
		queue.append(i)
		pat_arr[i] = num
		pat *= num
		pat %= 1000000007
		num -= 1
		
		
print(pat % 1000000007)

### FIXED CODE ###

n,k = map(int,input().split())
#a = [0 for _ in range(n)]
#b = [0 for _ in range(n)]
c = [[] for _ in range(n)]

for i in range(n - 1):
	A,B = map(int,input().split())
	#a[i] = A
	#b[i] = B
	c[A - 1].append(B - 1)
	c[B - 1].append(A - 1)

pat = k
pat_arr = [0 for _ in range(n)]
pat_arr[0] = k
queue = [0]



while(queue):
	pos = queue.pop(0)
	num = k-2
	if(pos == 0):num += 1
	
	for i in c[pos]:
		if(pat_arr[i] != 0):continue
		queue.append(i)
		pat_arr[i] = num
		pat *= num
		pat %= 1000000007
		num -= 1
		
		
print(pat % 1000000007)
### BUGGY CODE ###

import sys
import numpy as np
import math
import collections
from collections import deque 
from functools import reduce

# input = sys.stdin.readline

n = int(input())
a = list(map(int, input().split()))
a.sort()
s = set(a)
c = collections.Counter(a)
q = int(input())
for _ in range(q):
    cf, ca = map(int, input().split())
    if ca in c:
        c[ca] += c[cf]
#         del sd[cf]
        del c[cf]
    else:
#         sd[ca] = sd[cf]
        c[ca] = c[cf]
#         del sd[cf]
        del c[cf]
    total = 0
    for key, val in c.items():
#        print(key, val)
        total += key * val
    print(total)




### FIXED CODE ###

import sys
import numpy as np
import math
import collections
from collections import deque 
from functools import reduce

# input = sys.stdin.readline

n = int(input())
a = list(map(int, input().split()))
c = collections.Counter(a)
c_n = np.array([(k, v) for k, v in c.items()])
total = np.dot(c_n.T[0], c_n.T[1])
q = int(input())
for _ in range(q):
    cf, ca = map(int, input().split())
    num = c[cf]
    if ca in c:
        c[ca] += c[cf]
        c[cf] = 0
#         del sd[cf]
#         del c[cf]
    else:
#         sd[ca] = sd[cf]
        c[ca] = c[cf]
        c[cf] = 0
#         del sd[cf]
#         del c[cf]
    total += num * (ca - cf)
    print(total)
### BUGGY CODE ###


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

AA=[]
for i in range(n):
  for j in range(m):
    if A[j][0]==i :
      AA.append([A[j][0],A[j][1]])

A=AA
def kyotu(J,K):
  aa,bb=max(J[0],K[0]),min(J[1],K[1])
  if aa>=bb:
    return 0
  else:
    return [aa,bb]


kyo=[]
kk=[]
def kyotu2(k):
  for i in range(len(kyo)):
    kk=kyotu(kyo[i],A[k])
    
    if kk!=0:
      kyo[i][0]=kk[0]
      kyo[i][1]=kk[1]
      return 0
    
  kyo.append([A[k][0],A[k][1]])



for i in range(m):
  kyotu2(i)
#print(kyo)
print(len(kyo))


### FIXED CODE ###


from operator import itemgetter
 
n,m=map(int, input().split())
A=[]
B=[]
a=0
b=0
for i in range(m):
  a,b=map(int, input().split())
  A.append([a,b])

A.sort(key=itemgetter(1))
bri=0 #取った橋のうち番号最大の島のもの。bri=5なら4,5番目の島の橋

count=0

for i in range(m):
  a=A[i][0]
  b=A[i][1]
  
  if a>=bri:
    bri=b
    count+=1

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

from sys import stdin
N = int(stdin.readline().rstrip())
print(0)
s = input()
cnt = 0
N = (N-1)//2
if s == "Male":
    for _ in range(25):
        print(N)
        s = input()
        if s == "Male" and N % 2 == 0:
            N += max(min(N//2,(L-N)//2),1)
        elif s == "Female" and N % 2 != 0:
            N += max(min(N//2,(L-N)//2),1)
        elif s == "Vacant":
            break
        else:
            N -= max(min(N//2,(L-N)//2),1)
        
elif s == "Female":
    for _ in range(25):
        print(N)
        s = input()
        if s == "Female" and N % 2 == 0:
            N += max(min(N//2,(L-N)//2),1)
        elif s == "Male" and N % 2 != 0:
            N += max(min(N//2,(L-N)//2),1)
        elif s == "Vacant":
            break
        else:
            N -= max(min(N//2,(L-N)//2),1)

### FIXED CODE ###

from sys import stdin
N = int(stdin.readline().rstrip())
r = N-1
l = 0
print(0)
s = input()
cnt = 0
mid = (r+l)//2
if s == "Male":
    for _ in range(25):
        print(mid)
        s = input()
        if s == "Male" and mid % 2 == 0:
            l += max((r-l)//2,1)
        elif s == "Female" and mid % 2 != 0:
            l += max((r-l)//2,1)
        elif s == "Vacant":
            break
        else:
            r -= max((r-l)//2,1)
        mid = (r+l)//2
        
elif s == "Female":
    for _ in range(25):
        print(mid)
        s = input()
        if s == "Female" and mid % 2 == 0:
            l += max((r-l)//2,1)
        elif s == "Male" and mid % 2 != 0:
            l += max((r-l)//2,1)
        elif s == "Vacant":
            break
        else:
            r -= max((r-l)//2,1)
        mid = (r+l)//2
### BUGGY CODE ###

import sys
def input():return sys.stdin.readline()[:-1]
def N(): return int(input())
def NM():return map(int,input().split())
def L():return list(NM())
def LN(n):return [N() for i in range(n)]
def LL(n):return [L() for i in range(n)]
n=N()
def primes(n):
    is_prime = [1] * (n + 1)
    is_prime[0] = 0
    is_prime[1] = 0
    for i in range(2, int(n**0.5) + 1):
        if not is_prime[i]:
            continue
        for j in range(i * 2, n + 1, i):
            is_prime[j] = 0
    return [i for i in range(n + 1) if is_prime[i]]
prime=primes(int(n**0.5)+10)
def prime_factorize2(n):
    a = []
    i=0
    f = prime[i]
    while f * f <= n:
        if n % f == 0:
            a.append(f)
            n //= f
        else:
            i+=1
            f = prime[i]
    if n != 1:
        a.append(n)
    return a
ans=0
import collections
for i in range(1,n+1):
    c=collections.Counter(prime_factorize2(i))
    t=i
    for j in c.values():
        t*=j+1
    ans+=t
print(ans)

### FIXED CODE ###

import sys
def input():return sys.stdin.readline()[:-1]
def N(): return int(input())
def NM():return map(int,input().split())
def L():return list(NM())
def LN(n):return [N() for i in range(n)]
def LL(n):return [L() for i in range(n)]
n=N()
ans=0
for i in range(1,n+1):
    x=n//i
    ans+=(i+x*i)*x//2
print(ans)
### BUGGY CODE ###

n,wei = [int(x) for x in input().split()]
w = []
v = []
for _ in range(n):
    a,b = [int(x) for x in input().split()]
    w.append(a)
    v.append(b)
dp = [[-1]*(wei+1) for x in range(n+1)]
for i in range(wei+1):
    dp[0][i] = 0

for i in range(n):
    for j in range(wei+1):
        if j<w[i]:
            dp[i+1][j] = dp[i][j]
        else:
            dp[i+1][j] = max(dp[i][j],dp[i][j-w[i]]+v[i])

print(dp[n][wei])

### FIXED CODE ###

n,wei = [int(x) for x in input().split()]
w = []
v = []
for _ in range(n):
    a,b = [int(x) for x in input().split()]
    w.append(a)
    v.append(b)
dp = [[-1]*(wei+1) for x in range(n+1)]
for i in range(wei+1):
    dp[0][i] = 0

for i in range(n):
    for j in range(wei+1):
        if j<w[i]:
            dp[i+1][j] = dp[i][j]
        else:
            dp[i+1][j] = max(dp[i][j],dp[i][j-w[i]]+v[i])

print(dp[n][wei])
### BUGGY CODE ###

while(1):
    [N,M]=[int(x) for x in raw_input().split()]
    if N==0:
        break
    a=[0]
    for i in range(N):
        a.append(int(raw_input()))
    #b=sorted([x+y for x in a for y in a])
    #c=[]
    #for i in range(1,len(b)):
    #    if b[i]>M:
    #        break
    #    elif b[i-1]!=b[i]:
    #        c.append(b[i-1])
    b=[a[x]+a[y] for x in range(N+1) for y in range(x,N+1)]
    #c=f7(b)
    c=sorted(b)
    largest=0
    id=0
    for i in range(1,len(c)+1):
        if id==len(c) or largest==M:
            break
        while(id<len(c) and c[-i]+c[id]<=M):
            largest=max(largest,c[-i]+c[id])
            id+=1
    print largest

### FIXED CODE ###

import bisect

while(1):
    [N,M]=[int(x) for x in raw_input().split()]
    if N==0:
        break
    a=[0 for x in range(N+1)]
    for i in range(N):
        a[i+1]=int(raw_input())
    #b=sorted([x+y for x in a for y in a])
    #c=[]
    #for i in range(1,len(b)):
    #    if b[i]>M:
    #        break
    #    elif b[i-1]!=b[i]:
    #        c.append(b[i-1])
    b=[a[x]+a[y] for x in range(N+1) for y in range(x,N+1)]
    #c=f7(b)
    c=sorted(b)
    #print c
    largest=0
    id=0
    st=len(c)-bisect.bisect(c,M)+1
    #print st
    for i in range(st,len(c)+1):
        if id==len(c):
            break
        while(id<len(c) and c[-i]+c[id]<=M):
            #print c[-i],c[id],c[-i]+c[id]
            largest=max(largest,c[-i]+c[id])
            id+=1
    print largest
### BUGGY CODE ###

x, k, d = map(int, input().split())
dp = [[float('inf'), float('inf')] for i in range(k+1)]
dp[0] = [x, x]
for i in range(k):
  if abs(dp[i][0] + k) < abs(dp[i][1] + k):
    dp[i+1][0] = dp[i][0] + d
  else:
    dp[i+1][0] = dp[i][1] + d
  if abs(dp[i][0] - k) < abs(dp[i][1] - k):
    dp[i+1][1] = dp[i][0] - d
  else:
    dp[i+1][1] = dp[i][1] - d
if abs(dp[k][0]) < abs(dp[k][1]):
  print(abs(dp[k][0]))
else:
  print(abs(dp[k][1]))

### FIXED CODE ###

x, k, d = map(int, input().split())
x_abs = abs(x)
if x_abs - k * d >= 0:
  print(x_abs - k * d)
else:
  kk = k - x_abs // d
  x_now = x_abs - (k - kk) * d
  if kk % 2 == 0:
    print(x_now)
  else:
    print(abs(x_now - d))
### BUGGY CODE ###

from collections import deque
n,k=map(int,input().split())
ints=[list(map(int,input().split())) for _ in range(n)]
d=deque()
for x in ints:
  d.extend([x[0]]*x[1])
ans=sorted(list(d))
print(ans[k-1])

### FIXED CODE ###

import sys
rl=sys.stdin.readline

def main():
    n,k=map(int,rl().strip().split())
    ints=[list(map(int,rl().strip().split())) for _ in range(n)]
    ints.sort(key=lambda e:e[0])
    s=0
    for e in ints:
        s+=e[1]
        if s>=k:
            print(e[0])
            break

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

N = input()
t, a = map(int, raw_input().split())
for i in xrange(N-1):
    new_t, new_a = map(int, raw_input().split())
    dt, da = new_t, new_a
    while new_t < t or new_a < a:
        new_t += dt
        new_a += da
    t, a = new_t, new_a
print t+a


### FIXED CODE ###

N = input()
t, a = map(int, raw_input().split())
for i in xrange(N-1):
    new_t, new_a = map(int, raw_input().split())
    d = max((t-1)/new_t+1, (a-1)/new_a+1, 1)
    t, a = new_t*d, new_a*d
print t+a