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

import sys
sys.setrecursionlimit(10 ** 6)
n = int(input())

def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)

    # divisors.sort()
    return divisors



ansl = list(set(make_divisors(n-1)))
ansl.remove(1)

import sys
sys.setrecursionlimit(10 ** 6)

def check(i, k):
    if i == 1:
        return True
    if i < 1:
        return False
    if i % k == 0:
        return check(i // k, k)
    else:
        return check(i - k, k)

ansl2 = []
for i in make_divisors(n):
    if i == 1:
        continue
    elif i == 2:
        ansl.append(2)
    elif check(n, i):
        ansl2.append(i)

print(len(set(ansl + ansl2)))

### FIXED CODE ###

n = int(input())


def make_divisors(n):
    divisors = []
    for i in range(1, int(n ** 0.5) + 1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n // i)

    # divisors.sort()
    return divisors



ansl = make_divisors(n-1)
ansl.remove(1)
for i in make_divisors(n):
    if i == 1:
        continue
    k = n
    while k:
        if k % i == 0:
            k //= i
        else:
            if k % i == 1:
                ansl.append(i)
            break

print(len(set(ansl)))
### BUGGY CODE ###

n = int(input())
a = sorted(list(map(int, input().split())), reverse = True)

sum = 0
for i in range(n):
    a.pop(0)
    sum += a.pop(0)
print(sum)


### FIXED CODE ###

n = int(input())
a = sorted(list(map(int, input().split())), reverse = True)
print(sum(a[1::2][:n]))
### BUGGY CODE ###

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

def gcd(m, n) :
    while n :
        m, n = n, m % n
    return m

ret = 0
i = 2
x = gcd(A, B)
while x != 1 :
    flg = False
    while x % i == 0 :
        x //= i
        flg = True
        
    if flg :
        ret += 1
    i += 1
        
print(ret + 1)

### FIXED CODE ###

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

def gcd(m, n) :
    while n :
        m, n = n, m % n
    return m

ret = 0
x = gcd(A, B)
if x % 2 == 0 :
    ret += 1
    while x % 2 == 0 :
        x //= 2
        
i = 3
while i * i <= x :
    if x % i == 0 :
        ret += 1
        x //= i
        
    while x % i == 0 :
        x //= i
        
    i += 2

if x != 1 :
    ret += 1
print(ret + 1)
### BUGGY CODE ###

class BIT:
  def __init__(self, n):
    self.n = n
    self.data = [0]*(n+1)
    self.el = [0]*(n+1)
  def sum(self, i):
    s = 0
    while i > 0:
      s += self.data[i]
      i -= i & -i
    return s
  def add(self, i, x):
    # assert i > 0
    self.el[i] += x
    while i <= self.n:
      self.data[i] += x
      i += i & -i
  def get(self, i, j=None):
    if j is None:
      return self.el[i]
    return self.sum(j) - self.sum(i)

N, Q = map(int, input().split())
Cs = [0] + list(map(int, input().split()))

Qs = []
for i in range(Q):
  l,r = map(int, input().split())
  Qs.append((i,l,r))
  
Qs.sort(key=lambda x:x[2])

ans = [-1]*Q
dic = {}
b = 1
bt = BIT(N)

for i,l,r in Qs:
  st = set()
  for j in range(b,r+1):
    if not Cs[j] in st and Cs[j] in dic:
      bt.add(dic[Cs[j]],-1)
    st.add(Cs[j])
    dic[Cs[j]] = j
  for s in st:
    bt.add(dic[s], 1)
  ans[i] = bt.get(l-1,r)
  b = r + 1
  
for i in range(Q):
  print(ans[i])

### FIXED CODE ###

from sys import stdin
input = stdin.readline
class Bit:
    def __init__(self, n):
        self.size = n
        self.tree = [0] * (n + 1)
 
    def sum(self, i):
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s
 
    def add(self, i, x):
        while i <= self.size:
            self.tree[i] += x
            i += i & -i
 
n, q = map(int, input().split())
tmp = list(map(int, input().split()))
color = [-1]
for v in tmp:
    color.append(v)
qry = [None]*q
ans = [0]*q
p = 0
for _ in ans:
    l, r = map(int, input().split())
    qry[p] = [l-1, r, p]
    p += 1
qry.sort(key=lambda x: x[1])
dic = {}
last_update_idx = 1
bit = Bit(n)
for l, r, i in qry:
    if last_update_idx < r+1:
        st = set()
        for j in range(last_update_idx, r+1):
            if not color[j] in st and color[j] in dic:
                bit.add(dic[color[j]], -1)
            dic[color[j]] = j
            st.add(color[j])
        for v in st:
            bit.add(dic[v], 1)
        last_update_idx = r+1
    ans[i] = bit.sum(r) - bit.sum(l)
for v in ans:
    print(v)
### BUGGY CODE ###

import bisect


N, Q = map(int, input().split(" "))
check_points = [input() for _ in range(N)]
querys = [int(input()) for _ in range(Q)]
time = {}
for q in querys:
    time[q] = -1

for line in check_points:
    s, f, x = map(int, line.split(" "))
    start = s-x
    end = f-x
    left = bisect.bisect_left(querys, start)
    right = bisect.bisect_right(querys, end)
    for q in querys[left:right]:
        if q >= end:
            break
        if time[q] == -1 or time[q] > x:
            time[q] = x

for q in querys:
    print(time[q])


### FIXED CODE ###

from bisect import bisect_left
from operator import itemgetter

N, Q = map(int, input().split(" "))
check_points = [tuple(map(int, input().split(" "))) for _ in range(N)]
querys = [int(input()) for _ in range(Q)]
time = [-1 for _ in range(Q)]
jump = [-1 for _ in range(Q)]
check_points = sorted(check_points, key=itemgetter(2))
b_left = bisect_left

for line in check_points:
    s, f, x = line
    start = s-x
    end = f-x
    left = b_left(querys, start)
    right = b_left(querys, end)
    while left < right:
        if time[left] == -1:
            time[left] = x
            jump[left] = right
            left += 1
        else:
            left = jump[left]

for t in time:
    print(t)
### BUGGY CODE ###

n, k = map(int, input().split())
a = list(map(int, input().split()))
def last_k(a, i):
    p = 1
    for j in range(k):
        p=p*a[i-j]
    return p
seed = last_k(a, k-1)
for i in range(n-k):
    if seed < int(seed*a[i+k]/a[i]):
        print('Yes')
    else:
        print('No')


### FIXED CODE ###

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

for i in range(n-k):
    if a[i+k] > a[i]:
        print('Yes')
    else:
        print('No')
### BUGGY CODE ###

# import sys
# sys.setrecursionlimit(10 ** 6)
# import bisect
# from collections import deque
# from decorator import stop_watch
#
#
# @stop_watch
def solve(N, XY):
    tmp = 0
    for x, y in XY:
        tmp += (abs(x) + abs(y)) % 2
    if tmp % N != 0:
        print(-1)
        return
    m = 20 if tmp == 0 else 21
    d = [1] * m
    w = []
    for x, y in XY:
        mm = m
        ww = ''
        ww += ('R' if x >= 0 else 'L') * abs(x)
        ww += ('U' if y >= 0 else 'D') * abs(y)
        ww += 'RL' * ((mm - (abs(x) + abs(y))) // 2)
        w.append(ww)
    print(m)
    print(' '.join([str(di) for di in d]))
    [print(wi) for wi in w]


if __name__ == '__main__':
    # S = input()
    N = int(input())
    # N, M = map(int, input().split())
    # A = [int(i) for i in input().split()]
    # B = [int(i) for i in input().split()]
    XY = [[int(i) for i in input().split()] for _ in range(N)]
    solve(N, XY)

    # # test
    # from random import randint
    # from func import random_str
    # solve()


### FIXED CODE ###

# 解説を参考に作成
# import sys
# sys.setrecursionlimit(10 ** 6)
# import bisect
# from collections import deque
# from decorator import stop_watch
#
#
# @stop_watch
def solve(N, XY):
    tmp = 0
    for x, y in XY:
        tmp += (abs(x) + abs(y)) % 2
    if tmp % N != 0:
        print(-1)
        return
    import math
    m = math.ceil(math.log2(2 * 10 ** 9)) + 1
    d = [2 ** (m - i) for i in range(m)] + [1]
    d += [1] if tmp == 0 else []
    m = len(d)
    w = []
    for xi, yi in XY:
        xx = 0
        yy = 0
        W = ''
        for di in d:
            if abs(xi - xx) >= abs(yi - yy):
                if xx <= xi:
                    xx += di
                    W += 'R'
                else:
                    xx -= di
                    W += 'L'
            else:
                if yy <= yi:
                    yy += di
                    W += 'U'
                else:
                    yy -= di
                    W += 'D'
        w.append(W)
    print(m)
    print(' '.join([str(i) for i in d]))
    [print(wi) for wi in w]


if __name__ == '__main__':
    # S = input()
    N = int(input())
    # N, M = map(int, input().split())
    # A = [int(i) for i in input().split()]
    # B = [int(i) for i in input().split()]
    XY = [[int(i) for i in input().split()] for _ in range(N)]
    solve(N, XY)

    # # test
    # from random import randint
    # from func import random_str
    # solve()
### BUGGY CODE ###

import queue
n,m=map(int,input().split())
a=[[0 for i in range(n)] for j in range(n)]
for i in range(0,m):
    b,c=map(int,input().split())
    a[b-1][c-1]=1
    a[c-1][b-1]=1
re=[0 for i in range(n)]
le=[0]
for i in range(0,n):
    if re[i]==0:
        ans=queue.Queue()
        ans.put(i)
        le.append(1)
        re[i]=1
        while ans.empty()==False:
            d=ans.get()
            for j in range(d,n):
                if a[i][j]==1 and re[j]==0:
                    ans.put(j)
                    re[j]=1
                    le[-1]+=1
print(max(le))

### FIXED CODE ###

import queue
n,m=map(int,input().split())
a=[[] for j in range(n)]
for i in range(0,m):
    b,c=map(int,input().split())
    a[b-1].append(c-1)
    a[c-1].append(b-1)
re=[0 for i in range(n)]
le=[0]
for i in range(0,n):
    if re[i]==0:
        ans=queue.Queue()
        ans.put(i)
        le.append(1)
        re[i]=1
        while ans.empty()==False:
            d=ans.get()
            for j in range(len(a[d])):
                if re[a[d][j]]==0:
                    ans.put(a[d][j])
                    re[a[d][j]]=1
                    le[-1]+=1
print(max(le))
### BUGGY CODE ###

n=int(input())
a=list(map(int,input().split()))
for i in range(1,n+1):
    print(a.index(i)+1,end=' ')

### FIXED CODE ###

n=int(input())
a=list(map(int,input().split()))
b=[]
for i in range(n):
    b.append([a[i],i+1])
b.sort()
for i in b:
    print(i[1],end=' ')
### BUGGY CODE ###

from collections import defaultdict
from collections import deque

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

chg = 10**6
G = defaultdict(set)
for _ in range(M):
    p, q, c = map(int, input().split())
    # 無向グラフ
    G[p].add(p+chg*c)
    G[p+chg*c].add(p)
    G[q].add(q+chg*c)
    G[q+chg*c].add(q)
    G[p+chg*c].add(q+chg*c)
    G[q+chg*c].add(p+chg*c)


dist = defaultdict(lambda: 10**11)
dist[1] = 0

que = deque([1])

while que:
    ci = que.popleft()

    for ni in G[ci]:
        if dist[ni] == 10**11:
            if ci >= chg and ni >= chg:
                dist[ni] = dist[ci]
                que.appendleft(ni)
            else:
                dist[ni] = dist[ci]+1
                que.append(ni)


if dist[N] < 10**11:
    print(dist[N]//2)
else:
    print(-1)


### FIXED CODE ###

from collections import defaultdict
from collections import deque

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

chg = 10**6
G = defaultdict(set)
for _ in range(M):
    p, q, c = map(int, input().split())
    # 無向グラフ
    G[p].add(p+chg*c)
    G[p+chg*c].add(p)
    G[q].add(q+chg*c)
    G[q+chg*c].add(q)
    G[p+chg*c].add(q+chg*c)
    G[q+chg*c].add(p+chg*c)


dist = defaultdict(lambda: 10**11)
dist[1] = 0

que = deque([1])

while que:
    ci = que.popleft()

    for ni in G[ci]:
        if dist[ni] == 10**11:
            if ci >= chg and ni >= chg:
                dist[ni] = dist[ci]
                que.appendleft(ni)
            else:
                dist[ni] = dist[ci]+1
                que.append(ni)


if dist[N] < 10**11:
    print(dist[N]//2)
else:
    print(-1)
### BUGGY CODE ###

#coding:utf-8
n, m = list(map(int, input().split()))
count = 0
for i in range(n):
    for j in range(m):
        around = 0
        for w in range(-1, 2):
            for h in range(-1, 2):
                if i+w >= 0 and i+w < n and j+h >= 0 and j+h < m:
                    around += 1
        if around % 2 == 1:
            count += 1
print(count)

### FIXED CODE ###

#coding:utf-8
n, m = list(map(int, input().split()))
count = 0
if n == 1 and m == 1:
    print("1")
elif n == 1 or m == 1:
    print(n*m-2)
else:
    print((n-2)*(m-2))
### BUGGY CODE ###

#coding:utf-8
   
n, k = map(int, input().split())
backList = []
for i in range(n):
    backList.append(int(input()))

def capa(p,k):
    cnt = 0
    pcopy = p
    num = 0
    for back in backList:
        if back > p:
            break
        if back <= pcopy:
            pcopy -= back
            cnt += 1
            continue
        elif back > pcopy:
            if num == k-1:
                return cnt
            pcopy = p - back
            cnt += 1
            num += 1          
    return cnt


p_min = 0
p_max = 100000 * 10000
def biSearch(p_min, p_max):
    p = p_max - p_min
    if p_min == p_max:
        return p_min
    if p % 2 == 0:
        p = int(p/2)
    else:
        p = int((p+1)/2)
    v = capa(p,k)
    if v < n:
        p_min = p_min + p
    else:
        p_max = p_min + p

    return biSearch(p_min, p_max)
            

p = biSearch(p_min, p_max)
n_init = n
while n_init <= n:
    p -= 1
    n = capa(p,k)

print(p+1)



### FIXED CODE ###

#coding:utf-8
   
n, k = map(int, input().split())
backList = []
for i in range(n):
    backList.append(int(input()))

def capa(p,k):
    cnt = 0
    pcopy = p
    num = 0
    for back in backList:
        if back > p:
            break
        if back <= pcopy:
            pcopy -= back
            cnt += 1
            continue
        elif back > pcopy:
            if num == k-1:
                return cnt
            pcopy = p - back
            cnt += 1
            num += 1          
    return cnt


p_min = 0
p_max = 100000 * 10000
def biSearch(p_min, p_max):
    p = p_max - p_min
    if p_max - p_min <= 1:
        return p_max
    if p % 2 == 0:
        c = p_min + int(p/2)
    else:
        c = p_min + int((p+1)/2)
    v = capa(c,k)
    if v < n:
        p_min = c
    else:
        p_max = c

    return biSearch(p_min, p_max)
            

p = biSearch(p_min, p_max)
n_init = n
while n_init <= n:
    p -= 1
    n = capa(p,k)

print(p+1)
### BUGGY CODE ###

# -*- coding: utf-8 -*-
s = list(input())
k = int(input())

part = [[]]

for i in range(len(s)):
    for j in range(1,len(s)+1):
        if i + j > len(s):
            break
        part.append(s[i:i+j])
del part[0]

part.sort()

delete = []

for i in range(1,len(part)):
    if part[i-1] == part[i]:
        delete.append(i)

diff = 0
for i in range(len(delete)):
    del part[delete[i] - diff]
    diff += 1

print("".join(part[k-1]))


### FIXED CODE ###

# -*- coding: utf-8 -*-
s = list(input())
k = int(input())

part = [[]]

for i in range(len(s)):
    for j in range(1,k+1):
        if i + j > len(s):
            break
        part.append(s[i:i+j])
del part[0]

part.sort()

delete = []

for i in range(1,len(part)):
    if part[i-1] == part[i]:
        delete.append(i)

diff = 0
for i in range(len(delete)):
    del part[delete[i] - diff]
    diff += 1

print("".join(part[k-1]))
### BUGGY CODE ###

# @oj:atcoder
# @id: hitwanyang
# @email: 296866643@qq.com
# @date: 2020-04-20 10:31
# @url:https://atcoder.jp/contests/dp/tasks/dp_b
import sys
def input():
    return sys.stdin.readline().strip()

def main():
    nk=list(map(int,input().split()))
    h=list(map(int,input().split()))
    n=nk[0]
    k=nk[1]
    dp=[10**9]*n
    dp[0]=0
    dp[1]=abs(h[1]-h[0])
    for i in range(2,n):
        for j in range(max(0,i-k),i):
            dp[i]=min(dp[j]+abs(h[i]-h[j]),dp[i])

    print (dp[n-1])

if __name__ == "__main__":
    main()

### FIXED CODE ###

import sys


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


def main():
    size, jumps = map(int, input().split())
    array = list(map(int, input().split()))
    dp = [999999999] * size
    dp[0]= 0
    dp[1] = abs(array[0]- array[1])
    for i in range(2,size):
        dp[i] = min(abs(array[i] - array[j]) + dp[j] for j in range(max(0, i - jumps), i))
    print(dp[size-1])

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

N, M, K = map(int, input().split())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
ans = 0
sum_a = 0
for i in range(len(A)+1):
    if i == 0:
        sum_a = 0
    else:
        sum_a += A[i-1]
    if sum_a > K:
        break
    sum_b = 0
    for j in range(len(B)+1):
        if j == 0:
            sum_b = 0
        else:
            sum_b += B[j-1]
        if sum_b > K - sum_a:#Bを全部読み切れない場合
            ans = max(ans, i+j-1)
            break
        if j == len(B): #Bを全部読み切れる場合
            ans = max(ans, i+j)
print(ans)

### FIXED CODE ###

N, M, K = map(int, input().split())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
a = [0]*(N+1)
b = [0]*(M+1)
for i in range(1, N+1):
    a[i] = a[i-1] + A[i-1]
for j in range(1, M+1):
    b[j] = b[j-1] + B[j-1]

ans = 0
j = M
for i in range(N+1):
    if K - a[i] < 0:
        break
    while b[j] > K - a[i]:
        j -= 1
    ans = max(ans, i+j)
print(ans)
### BUGGY CODE ###

A, B, Q = map(int, input().split())
S = [int(input()) for _ in range(A)]
T = [int(input()) for _ in range(B)]
X = [int(input()) for _ in range(Q)]
INF = 10**12

def binary_search(query, arr):
    arr = [-INF] + arr + [INF]
    low = 0
    high = len(arr)
    while high-low>1:
        mid = (low+high)//2
        if query>arr[mid]:
            low = mid
        else:
            high = mid
    return arr[low], arr[high]

def main():
    for x in X:
        s1, s2 = binary_search(x, S)
        t1, t2 = binary_search(x, T)
        ans = INF
        for s in [s1, s2]:
            for t in [t1, t2]:
                ans = min(ans, abs(t-s)+min(abs(t-x), abs(s-x)))
        print(ans)
    return

main()

### FIXED CODE ###

A, B, Q = map(int, input().split())
INF = 10**12
S = [-INF] + [int(input()) for _ in range(A)] + [INF]
T = [-INF] + [int(input()) for _ in range(B)] + [INF]
X = [int(input()) for _ in range(Q)]


def binary_search(query, arr):
    low = 0
    high = len(arr)
    while high-low>1:
        mid = (low+high)//2
        if query>arr[mid]:
            low = mid
        else:
            high = mid
    return arr[low], arr[high]

def main():
    for x in X:
        s1, s2 = binary_search(x, S)
        t1, t2 = binary_search(x, T)
        ans = [ abs(t-s)+min(abs(t-x), abs(s-x)) \
            for t in [t1, t2] for s in [s1, s2] ]
        print(min(ans))
    return

main()
### BUGGY CODE ###

n = int(input())
a = list(map(str,input().split()))
q = int(input())
for i in range (q):
    Sum = 0
    b,c = map(str,input().split())
    a.sort()
    a = [s.replace(b,c) for s in a]
    for i in a:
        i= int(i)
        Sum +=i
    print(Sum)

### FIXED CODE ###

from collections import defaultdict
n = int(input())
a = list(map(int,input().split()))
q = int(input())
d = defaultdict(lambda: 0)
Sum = 0
for nums in a:
    d[nums] += 1
for keys in d:
        cnt = d[keys]
        keys = int(keys)
        Sum += keys*cnt
for i in range (q):
    b,c = map(int,input().split())
    d[c] += d[b]
    Sum += (c-b)*d[b]
    del d[b]
    print(Sum)
### BUGGY CODE ###

X, Y, Z, K = map(int,input().split())
A = list(map(int,input().split()))
B = list(map(int,input().split()))
C = list(map(int,input().split()))
ans = []
for i in range(X):
    for j in range(Y):
        for k in range(Z):
            ans.append(A[i]+B[j]+C[k])
ans.sort(reverse = True)
for i in ans[:K]:
    print(i)

### FIXED CODE ###

import heapq
X, Y, Z, K = map(int,input().split())
A = list(map(lambda x: -1 * int(x),input().split()))
B = list(map(lambda x: -1 * int(x),input().split()))
C = list(map(lambda x: -1 * int(x),input().split()))
A.sort()
B.sort()
C.sort()
Q = []
heapq.heappush(Q, (A[0] + B[0] + C[0], 0, 0, 0))
for _ in range(K):
    SUM, a, b, c = heapq.heappop(Q)
    print(-1 * SUM)
    if a <= X - 2 and not (A[a+1] + B[b] + C[c], a+1, b, c) in Q:
        heapq.heappush(Q, (A[a+1] + B[b] + C[c], a+1, b, c))
    if b <= Y - 2 and not (A[a] + B[b+1] + C[c], a, b+1, c) in Q:
        heapq.heappush(Q, (A[a] + B[b+1] + C[c], a, b+1, c))
    if c <= Z - 2 and not (A[a] + B[b] + C[c+1], a, b, c+1) in Q:
        heapq.heappush(Q, (A[a] + B[b] + C[c+1], a, b, c+1))
### BUGGY CODE ###

n, w = map(int, input().split())
items = []

for i in range(n):
    items.append(list(map(int, input().split())))


def knapsack(n, w, items):
    c = [[0 for _ in range(w + 1)] for _ in range(n + 1)]
    g = [[0 for _ in range(w + 1)] for _ in range(n + 1)]

    for i in range(w + 1):
        c[0][i] = 0
        g[0][i] = 1

    for i in range(n + 1):
        c[i][0] = 0

    for i in range(1, n + 1):
        for j in range(1, w + 1):
            c[i][j] = c[i - 1][j]
            g[i][j] = 0
            item = items[i - 1]
            if item[0] > j:
                continue
            if item[1] + c[i - 1][j - item[0]] > c[i - 1][j]:
                c[i][j] = item[1] + c[i - 1][j - item[0]]
                g[i][j] = 1

    max_value = c[n][w]
    routes = []
    for i in range(n, 0, -1):
        if g[i][w] == 1:
            routes.append(i)
            w -= items[i - 1][0]
    return max_value, routes


result, _ = knapsack(n, w, items)
print(result)


### FIXED CODE ###

n, w = map(int, input().split())
items = []
 
for i in range(n):
    items.append(list(map(int, input().split())))
 
 
def knapsack(n, w, items):
    c = [[0 for _ in range(w + 1)] for _ in range(n + 1)]
    g = [[0 for _ in range(w + 1)] for _ in range(n + 1)]
 
    for i in range(w + 1):
        c[0][i] = 0
        g[0][i] = 1
 
    for i in range(n + 1):
        c[i][0] = 0
 
    for i in range(1, n + 1):
        for j in range(1, w + 1):
            c[i][j] = c[i - 1][j]
            g[i][j] = 0
            item = items[i - 1]
            if item[0] > j:
                continue
            if item[1] + c[i - 1][j - item[0]] > c[i - 1][j]:
                c[i][j] = item[1] + c[i - 1][j - item[0]]
                g[i][j] = 1
 
    max_value = c[n][w]
    routes = []
    for i in range(n, 0, -1):
        if g[i][w] == 1:
            routes.append(i)
            w -= items[i - 1][0]
    return max_value, routes
 
 
result, _ = knapsack(n, w, items)
print(result)
### BUGGY CODE ###

n, m = map(int, input().split())
sum = 0
money = 0
A = list()
B = list()
for i in range(n):
    a, b = input().split()
    A.append(int(a))
    B.append(int(b))
for i in range(n):
    index = A.index(min(A))
    if(B[index] >= m - sum):
        money += A[index] * (m - sum)
        sum = m
    else:
        sum += B[index]
        money += A[index]*B[index]
    if(sum == m):
        print(money)
        break
    del A[index]
    del B[index]


### FIXED CODE ###

n, m = map(int, input().split())
sum = 0
money = 0
list_ab = list()
for i in range(n):
    list_ab.append(list(map(int, input().split())))
list_ab = sorted(list_ab)
for i in range(n):
    if(list_ab[i][1] >= m - sum):
        money += list_ab[i][0] * (m - sum)
        break
    else:
        sum += list_ab[i][1]
        money += list_ab[i][0]*list_ab[i][1]
print(money)
### BUGGY CODE ###

h, w = map(int, input().split())
a = [['#'] * (w + 2)] + [['#'] + list(input()) + ['#']
                          for _ in range(h)] + [['#'] * (w + 2)]
p = [(i, j) for i in range(1, h + 1) for j in range(1, w + 1) if a[i][j] == '#']
d = (-1, 0), (1, 0), (0, -1), (0, 1)
r = -1
while p:
    r += 1
    s = []
    for i, j in p:
        for di, dj in d:
            di += i
            dj += j
            if a[di][dj] == '.':
                a[di][dj] = '#'
                s.append((di, dj))
    p = s
print(r)


### FIXED CODE ###

h, w = map(int, input().split())
a = [['#'] * (w + 2)] + [['#'] + list(input()) + ['#']
                          for _ in range(h)] + [['#'] * (w + 2)]
p = [(i, j) for i in range(1, h + 1) for j in range(1, w + 1) if a[i][j] == '#']
d = (-1, 0), (1, 0), (0, -1), (0, 1)
r = -1
while p:
    r += 1
    s = []
    for i, j in p:
        for di, dj in d:
            di += i
            dj += j
            if a[di][dj] == '.':
                a[di][dj] = '#'
                s.append((di, dj))
    p = s
print(r)