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

from sys import stdin
from collections import deque
H, W = [int(x) for x in stdin.readline().rstrip().split()]

data = []

for _ in range(H):
    data.append(list(input()))

searched = [[0]*(W+2)]

for _ in range(H):
    searched.append([0] + [1000000]*W + [0])
searched.append([0]*(W+2))

visit_p = deque()
for h,i in enumerate(data):
    for w, j in enumerate(i):
        if j == "#":
            searched[h+1][w+1] = 0
            visit_p.append((h+1, w+1, 0))
while visit_p:
    nh,nw,num = visit_p.popleft()
    for dh,dw in [(0,1),(1,0),(0,-1),(-1,0)]:
        if searched[nh+dh][nw+dw] > num:
            searched[nh+dh][nw+dw] = num + 1
            visit_p.append((nh+dh,nw+dw,num+1))
print(max(map(max, searched)))

### FIXED CODE ###

from sys import stdin
from collections import deque
H, W = [int(x) for x in stdin.readline().rstrip().split()]

data = []

for _ in range(H):
    data.append(list(input()))

searched = [[0]*(W+2)]

for _ in range(H):
    searched.append([0] + [1000000]*W + [0])
searched.append([0]*(W+2))

visit_p = deque()
for h,i in enumerate(data):
    for w, j in enumerate(i):
        if j == "#":
            searched[h+1][w+1] = 0
            visit_p.append((h+1, w+1, 0))
while visit_p:
    nh,nw,num = visit_p.popleft()
    if searched[nh][nw] < num:
        continue
    for dh,dw in [(0,1),(1,0),(0,-1),(-1,0)]:
        if searched[nh+dh][nw+dw] > num + 1:
            searched[nh+dh][nw+dw] = num + 1
            visit_p.append((nh+dh,nw+dw,num+1))
print(max(map(max, searched)))
### BUGGY CODE ###

n = int(input())
a = list(map(int,input().split()))
total = 1
maxi = 10 ** 18
for ae in a:
    total *= ae
if total > maxi:
    print(-1)
    exit()
print(total)



### FIXED CODE ###

n = int(input())
a = list(map(int,input().split()))
a.sort(reverse = True)
if a[-1] == 0:
    print(0)
    exit()
total = 1
maxi = 10 ** 18
for ae in a:
    total *= ae
    if total > maxi:
        print(-1)
        exit()
print(total)
### BUGGY CODE ###

n, m = map(int, input().split())
broken = []
for i in range(m):
    broken.append(int(input()))
    
num = [0] * (n + 1)
num[0] = int(0 not in broken)
num[1] = int(1 not in broken)

for i in range(2, n):
    if i in broken:
        num[i] = 0
    else:
        num[i] = (num[i-1] + num[i-2])%1000000007
        
if n <= 1:
    print(num[n])
else:
    print((num[n-1]+num[n-2])%1000000007)

### FIXED CODE ###

n, m = map(int, input().split())
broken = []
for i in range(m):
    broken.append(int(input()))
    
num = [-1] * (n + 1)
num[0] = 1
num[1] = 1


for i in broken:
    num[i] = 0

for i in range(2, n):
    if num[i] == -1:
        num[i] = (num[i-1] + num[i-2])%1000000007
        
if n <= 1:
    print(num[n])
else:
    print((num[n-1]+num[n-2])%1000000007)
### BUGGY CODE ###

import sys, math, itertools, bisect, copy, re
from collections import Counter, deque, defaultdict

# from itertools import accumulate, permutations, combinations, takewhile, compress, cycle
# from functools import reduce
# from math import ceil, floor, log10, log2, factorial
# from pprint import pprint

INF = float('inf')
MOD = 10 ** 9 + 7
EPS = 10 ** -7
sys.setrecursionlimit(1000000)

# N = int(input())
# N,M = [int(x) for x in input().split()]
# V = [[0] * 100 for _ in range(100)]
# A = [int(input()) for _ in range(N)]
# DP = [[0] * 100 for _ in range(100)]
# DP = defaultdict(lambda: float('inf'))

S = input()
N = len(S)
sum = 0
dp = [0] * 13
dp[0] = 1

for i, s in enumerate(S):
    n = N - i - 1
    if s == '?':
        # print("{}".format(10 ** n))
        a = [0] * 13
        for j in range(10):
            m = j * (10 ** n) % 13
            a[m] += 1

        newDP = [0] * 13
        for j1 in range(13):
            for j2 in range(13):
                newDP[(j1 + j2) % 13] += dp[j1] * a[j2]
        dp = [x % MOD for x in newDP]

    else:
        # print("{}".format(int(s) * (10 ** n)))
        sum += (int(s) * (10 ** n))
        sum = sum % 13
        # m2 = int(s) * (10 ** n)
        # m = (int(s) * (10 ** n)) % 13
        # dp = dp[m:] + dp[:m]

# print("sum:{}, sum%13:{}".format(sum, sum % 13))
# print(dp)
print(dp[(-(sum % 13) + 5 + 13) % 13])
# for i in range(13):
#     print("{:3} : {}".format(i, dp[i] % MOD))


### FIXED CODE ###

import sys, math, itertools, bisect, copy, re
from collections import Counter, deque, defaultdict

# from itertools import accumulate, permutations, combinations, takewhile, compress, cycle
# from functools import reduce
# from math import ceil, floor, log10, log2, factorial
# from pprint import pprint

INF = float('inf')
MOD = 10 ** 9 + 7
EPS = 10 ** -7
sys.setrecursionlimit(1000000)

# N = int(input())
# N,M = [int(x) for x in input().split()]
# V = [[0] * 100 for _ in range(100)]
# A = [int(input()) for _ in range(N)]
# DP = [[0] * 100 for _ in range(100)]
# DP = defaultdict(lambda: float('inf'))

S = input()
M = 13
DP = [0] * M
DP[0] = 1

mul = 1
for i in range(len(S) - 1, -1, -1):
    s = S[i]
    newDP = [0] * M
    if s == '?':
        for k in range(10):
            for j in range(M):
                newDP[(mul * k + j) % M] += DP[j]
    else:
        k = int(s)
        for j in range(M):
            newDP[(mul * k + j) % M] += DP[j]
    DP = [x % MOD for x in newDP]
    mul *= 10
    mul %= M

print(DP[5])
### BUGGY CODE ###

import sys

def main():
    N = int(input())
    A = list(map(int, input().split()))
    Q = int(input())

    answer = sum(A)
    numNumberList = [0] * 100001

    for Ai in A:
        numNumberList[Ai] = A.count(Ai)    

    for i in range(Q):
        B, C = list(map(int, sys.stdin.readline().split()))
        answer = answer + (int(C) - int(B)) * numNumberList[B]

        numNumberList[C] = numNumberList[C] + numNumberList[B]
        numNumberList[B] = 0

        print(answer)

if __name__ == "__main__":
    main()

### FIXED CODE ###

import sys

def main():
    N = int(input())
    A = list(map(int, input().split()))
    Q = int(input())

    answer = sum(A)
    setA = set(A)
    numNumberList = [0] * 100001

    for Ai in A:
        numNumberList[Ai] = numNumberList[Ai] + 1    

    for i in range(Q):
        B, C = list(map(int, sys.stdin.readline().split()))
        answer = answer + (int(C) - int(B)) * numNumberList[B]

        numNumberList[C] = numNumberList[C] + numNumberList[B]
        numNumberList[B] = 0

        print(answer)

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

import math

N = int(input())

a = pow(10,12)

is_not_prime = False
for k in range(2, int(math.sqrt(N)) + 1):
    if N % k == 0:
        is_not_prime = True
        break
if is_not_prime:
    for i in range(1, N):

        j = N/i
        if j.is_integer():

            if (i+int(j)) < a:
                a = i+int(j)
        if j < 1:
            break

    print(a - 2)
else:
    print(N - 1)

### FIXED CODE ###

import math

N = int(input())

a = pow(10,12)

is_not_prime = False
#for k in range(2, int(math.sqrt(N)) + 1):
#    if N % k == 0:
#        is_not_prime = True
#        break
#if is_not_prime:
for i in range(1, int(math.sqrt(N))+1):
    #print(i)
    j = N/i
    if j.is_integer():

        if (i+int(j)) < a:
            a = i+int(j)
    #if j < 2:
    #    break

print(a - 2)
#else:
#    print(N - 1)
### BUGGY CODE ###

N,K=map(int,input().split())
h=list(map(int,input().split()))
dp=[10**10]*(N)#dp[i]→i+1番目の柱にくる最小コスト
dp[0]=0
for i in range(N-1):
    dp[i+1]=min(dp[i+1-j]+abs(h[i+1]-h[i+1-j]) for j in range(1,min(i+1,K)+1))
print(dp[N-1])

### FIXED CODE ###

N,K=map(int,input().split())
h=list(map(int,input().split()))
dp=[10**10]*(N)#dp[i]→i+1番目の柱にくる最小コスト
dp[0]=0
for i in range(N-1):
    dp[i+1]=min(dp[i+1-j]+abs(h[i+1]-h[i+1-j]) for j in range(1,min(i+1,K)+1))
print(dp[N-1])
### BUGGY CODE ###

h,w = map(int,input().split())
s = list(map(int,input().split()))
g = list(map(int,input().split()))
s[0] -= 1
s[1] -= 1
g[0] -= 1
g[1] -= 1
raw = []
seen = []
for _ in range(h):
  tmp = input()
  raw.append(tmp)
  t = []
  for j in range(w):
    if tmp[j] == '.':
      t.append(0)
    else:
      t.append(1)
  seen.append(t)

now = [s]
ans = 0

def check(ii,jj):
  if 0 <= ii < h and 0 <= jj < w:
    if seen[ii][jj] == 0:
      seen[ii][jj] = 1
      now.append([ii,jj])

while now:
  for x in now:
    a,b = x
    check(a-1,b)
    check(a+1,b)
    check(a,b-1)
    check(a,b+1)
  if seen[g[0]][g[1]] == 1:
    print(ans)
    break
  ans += 1
  last = now
  now = []
  for x in last:
    a,b = x
    for di in range(-2,3):
      for dj in range(-2,3):
        check(a+di,b+dj)
else:
  print(-1)

### FIXED CODE ###

h,w = map(int,input().split())
s = list(map(int,input().split()))
g = list(map(int,input().split()))
s[0] -= 1
s[1] -= 1
g[0] -= 1
g[1] -= 1
raw = []
seen = []
for _ in range(h):
  tmp = input()
  raw.append(tmp)
  t = []
  for j in range(w):
    if tmp[j] == '.':
      t.append(0)
    else:
      t.append(1)
  seen.append(t)

now = [s]
ans = 0

def check(ii,jj):
  if 0 <= ii < h and 0 <= jj < w:
    if seen[ii][jj] == 0:
      seen[ii][jj] = 1
      now.append([ii,jj])

while now:
  for x in now:
    a,b = x
    check(a-1,b)
    check(a+1,b)
    check(a,b-1)
    check(a,b+1)
  if seen[g[0]][g[1]] == 1:
    print(ans)
    break
  ans += 1
  last = now
  now = []
  for x in last:
    a,b = x
    for di in range(-2,3):
      for dj in range(-2,3):
        check(a+di,b+dj)
else:
  print(-1)
### BUGGY CODE ###

import math
N,M = map(int,input().split())
route_list = [[0]*N for i in range(N)]
for i in range(M):
  a,b = map(int,input().split())
  route_list[a-1][b-1] = 1
  route_list[b-1][a-1] = 1


node_num = N #ノードの数

unsearched_nodes = list(range(node_num)) # 未探索ノード
distance = [math.inf] * node_num # ノードごとの距離のリスト
previous_nodes = [-1] * node_num # 最短経路でそのノードのひとつ前に到達するノードのリスト
distance[0] = 0 # 初期のノードの距離は0とする

# @GDaigo さんのコメントより関数の追加 2017/03/18
def get_target_min_index(min_index, distance, unsearched_nodes):
    start = 0
    while True:
        index = distance.index(min_index, start)
        found = index in unsearched_nodes
        if found:
            return index
        else:
            start = index + 1

while(len(unsearched_nodes) != 0): #未探索ノードがなくなるまで繰り返す
    # まず未探索ノードのうちdistanceが最小のものを選択する
    posible_min_distance = math.inf # 最小のdistanceを見つけるための一時的なdistance。初期値は inf に設定。
    for node_index in unsearched_nodes: # 未探索のノードのループ
        if posible_min_distance > distance[node_index]: 
           posible_min_distance = distance[node_index] # より小さい値が見つかれば更新
    target_min_index = get_target_min_index(posible_min_distance, distance, unsearched_nodes) # 未探索ノードのうちで最小のindex番号を取得
    unsearched_nodes.remove(target_min_index) # ここで探索するので未探索リストから除去

    target_edge = route_list[target_min_index] # ターゲットになるノードからのびるエッジのリスト
    for index, route_dis in enumerate(target_edge):
        if route_dis != 0:
            if distance[index] > (distance[ target_min_index] + route_dis):
                distance[index] = distance[ target_min_index] + route_dis # 過去に設定されたdistanceよりも小さい場合はdistanceを更新
                previous_nodes[index] =  target_min_index #　ひとつ前に到達するノードのリストも更新

# 以下で結果の表示
#print("-----距離-----")
ans = ''
j = 1
for i in range(1,N):
  if(i != N-1):
    ans += str(previous_nodes[i]+1)+'\n'
  else:  
    ans += str(previous_nodes[i]+1)
  if(previous_nodes[i]<0):
    j = 0

if(j == 1):
  print('Yes')
  print(ans)
else:
  print('No')

### FIXED CODE ###

import math
import queue

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

# キューの定義
q = queue.Queue()
# キューにデータを挿入
q.put(0)
    
# キューからデータがなくなるまで取り出しを行う
flag = [0]*N 
flag[0]  = 1
ans_list = [0]*N

while(1):
  if(q.empty()):
    break
  num = q.get()
  for n in Map[num]:
    if(flag[n] != 1): # 訪問済みでないなら
      flag[n] = 1 # 訪問済みに
      ans_list[n] = num #　接続ノード(n)の1つ前のノードを今のノード(now)に
      q.put(n) # queueに接続ノードを入れる

print('Yes')
for i in range(1,N):
  print(ans_list[i]+1)
### BUGGY CODE ###

# 組み合わせ(高速，フェルマーの小定理を利用)
def cmb(n, r, mod):
    if ( r<0 or r>n ):
        return 0
    r = min(r, n-r)
    return g1[n] * g2[r] * g2[n-r] % mod
mod = 10**9+7 #出力の制限
N = 10 ** 5
g1 = [1, 1] # 元テーブル
g2 = [1, 1] #逆元テーブル
inverse = [0, 1] #逆元テーブル計算用テーブル

for i in range( 2, N + 1 ):
    g1.append( ( g1[-1] * i ) % mod )
    inverse.append( ( -inverse[mod % i] * (mod//i) ) % mod )
    g2.append( (g2[-1] * inverse[-1]) % mod )

mod = 10 ** 9 + 7
N, K = map(int, input().split())
A = list(map(int, input().split()))
A.sort()
ans = 0
for i in range(N-K+1):
    now_A = A[i]
    tmp = 1
    count = 0
    for k in range(i+K-1, N):
        ans += cmb(K-2+count, count, mod) * (A[k] - now_A)
        ans %= mod
        count += 1
        

print(ans%mod)

### FIXED CODE ###

# 組み合わせ(高速，フェルマーの小定理を利用)
def cmb(n, r, mod):
    if ( r<0 or r>n ):
        return 0
    r = min(r, n-r)
    return g1[n] * g2[r] * g2[n-r] % mod
mod = 10**9+7 #出力の制限
N = 10 ** 5
g1 = [1, 1] # 元テーブル
g2 = [1, 1] #逆元テーブル
inverse = [0, 1] #逆元テーブル計算用テーブル

for i in range( 2, N + 1 ):
    g1.append( ( g1[-1] * i ) % mod )
    inverse.append( ( -inverse[mod % i] * (mod//i) ) % mod )
    g2.append( (g2[-1] * inverse[-1]) % mod )

mod = 10 ** 9 + 7
N, K = map(int, input().split())
A = list(map(int, input().split()))
A.sort()
ans_max = 0
ans_min = 0
# ans_minを求める
for i in range(N-K+1):
    ans_min += A[i] * cmb(N-1-i, K-1, mod)
    ans_min %= mod
for i in range(K-1, N):
    ans_max += A[i] * cmb(i, K-1, mod)
    ans_max %= mod
##print(ans_max, ans_min)
print((ans_max - ans_min + mod)%mod)
### BUGGY CODE ###

import numpy as np
S = input()
mod = 10 ** 9 + 7

n = len(S)
dp = np.zeros((n, 13), int)
a = S[-1]
x_ = dp[0]
l = [1, 10, 9, 12, 3, 4]
l = [[i * l_ % 13 for i in range(1, 10)] for l_ in l] * (n // 6 + 1)
if a == "?":
    x_[0:10] = 1
else:
    x_[int(a)] = 1
for s, x, l_ in zip(S[-2::-1], dp[1:], l[1:]):
    if s == "?":
        x += x_
        for v in l_:
            x[v:] += x_[:-v]
            x[:v] += x_[-v:]
    else:
        if s == "0":
            x += x_
        else:
            v = l_[int(s) - 1]
            x[v:] += x_[:-v]
            x[:v] += x_[-v:]
    x %= mod
    x_ = x
print(dp[-1][5])

### FIXED CODE ###

#!python3

LI = lambda: list(map(int, input().split()))

# input
S = input()

MOD = 10 ** 9 + 7


def main():
    n = len(S)
    m = 5
    w = []
    p = 1
    for i in range(n):
        s = S[-1 - i]
        if s == "?":
            w.append(p)
        else:
            m = (m - int(s) * p) % 13
        p = p * 10 % 13

    n = len(w)
    l1 = [0] * 13
    l1[0] = 1
    for i in range(1, n + 1):
        l2 = [0] * 13
        for j in range(10):
            x = w[i - 1] * j % 13
            for k in range(13):
                t = (x + k) % 13
                l2[t] += l1[k]
        l1 = [y % MOD for y in l2]
    
    ans = l1[m]
    print(ans)


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

n, w = map(int,input().split())
items = []
for i in range(n):
    items.append(list(map(int,input().split())))
possibilities = []
for wi, vi in items:
    to_add =[]
    for wp, vp in possibilities:
        if wp + wi <= w:
            to_add.append([wp+wi, vp + vi])
    possibilities += to_add + [[wi, vi]]
print(max([x for y,x in possibilities]))


### FIXED CODE ###

def main():
    n, w = tuple([int(e) for e in input().split()])
    items = []
    for i in range(n):
        items.append(tuple([int(e) for e in input().split()]))
    items.sort(key=lambda x: x[0])
    
    t = [[0] * (n + 1) for _ in range(w + 1)]
    for i in range(1, w + 1):
        for j in range(1, n + 1):
            if i - items[j - 1][0] >= 0:
                t[i][j] = t[i - items[j - 1][0]][j - 1] + items[j - 1][1]
            t[i][j] = max(t[i][j], t[i][j - 1], t[i - 1][j], t[i - 1][j - 1])
    print(t[w][n])
    return 0

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

# ABC 65, B - trained
n = int(input())
A = [int(input()) for i in range(n)]

togo = [1]
went = []

while togo:
    for i in togo:
        togo.remove(i)
        went.append(i)
        if A[i-1] not in went:
            togo.append(A[i-1])
if 2 in went:
    print(went.index(2))
else:
    print(-1)


### FIXED CODE ###

# ABC 65, B - trained
n = int(input())
A = [int(input()) for i in range(n)]
now = 1
went = set()
for i in range(n):
    if now == 2:
        print(i)
        break
    if now in went:
        print(-1)
        break
    went.add(now)
    now = A[now-1]
### BUGGY CODE ###

import sys
input = lambda: sys.stdin.readline().rstrip() 

def resolve():

    class BinaryIndexedTree():
        def __init__(self, n):
            self.n = n
            self.bit = [0]*(n+1)

        def add(self, item, pos):
            index = pos
            while index < self.n+1:
                self.bit[index] += item
                index += index & (-index)

        def sum(self, pos):
            ret = 0
            index = pos
            while index > 0:
                ret += self.bit[index]
                index -= index & -index
            return ret

    N = int(input())
    S = list(input())
    Q = int(input())
    Query = [input().split() for _ in range(Q)] 

    pos_bit_list = [BinaryIndexedTree(len(S)) for _ in range(26)]

    for i, c in enumerate(S):
        pos_bit_list[ord(c)-ord('a')].add(1, i+1)

    for q in Query:
        if q[0] == '1':
            pos_bit_list[ord(S[int(q[1])-1])-ord('a')].add(-1, int(q[1]))
            pos_bit_list[ord(q[2])-ord('a')].add(1, int(q[1]))
            S[int(q[1])-1] = q[2]
        else:
            ans = 0
            for p in pos_bit_list:
                if p.sum(int(q[2])) - p.sum(int(q[1])-1) > 0:
                    ans += 1
            print(ans)


if __name__ == '__main__':
    resolve()


### FIXED CODE ###

import sys
input = lambda: sys.stdin.readline().rstrip() 

def resolve():

    class BinaryIndexedTree():
        def __init__(self, n):
            self.n = n
            self.bit = [0]*(n+1)

        def add(self, item, pos):
            index = pos
            while index < self.n+1:
                self.bit[index] += item
                index += index & (-index)

        def sum(self, pos):
            ret = 0
            index = pos
            while index > 0:
                ret += self.bit[index]
                index -= index & -index
            return ret

    N = int(input())
    S = list(input())
    Q = int(input())
    Query = [input().split() for _ in range(Q)] 

    pos_bit_list = [BinaryIndexedTree(len(S)) for _ in range(26)]

    for i, c in enumerate(S):
        pos_bit_list[ord(c)-ord('a')].add(1, i+1)

    for q in Query:
        if q[0] == '1':
            pos_bit_list[ord(S[int(q[1])-1])-ord('a')].add(-1, int(q[1]))
            pos_bit_list[ord(q[2])-ord('a')].add(1, int(q[1]))
            S[int(q[1])-1] = q[2]
        else:
            print(len([p for p in pos_bit_list if p.sum(int(q[2])) - p.sum(int(q[1])-1) > 0]))

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

def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10**7)
    from collections import Counter, deque
    #from collections import defaultdict
    from itertools import combinations, permutations, accumulate, groupby
    #from itertools import product
    from bisect import bisect_left,bisect_right
    import heapq
    from math import floor, ceil
    #from operator import itemgetter

    #inf = 10**17
    mod = 10**9 + 7

    s = input().rstrip()
    n = len(s)
    dp = [[0]*13 for _ in range(n)]

    if s[-1]=='?':
        for i in range(10):
            dp[0][i] = 1
    else:
        a = int(s[-1])
        dp[0][a] = 1

    for i in range(1, n):
        if s[-(i+1)] == '?':
            for j in range(10):
                a = (10**i) * j % 13
                for k in range(13):
                    dp[i][(a+k)%13] += dp[i-1][k]
                    dp[i][(a+k)%13] %= mod
        else:
            a = int(s[-(i+1)])
            a = (10**i) * a % 13
            for k in range(13):
                dp[i][(a+k)%13] += dp[i-1][k]
                dp[i][(a+k)%13] %= mod
                
    print(dp[-1][5])


if __name__ == '__main__':
    main()

### FIXED CODE ###

def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10**7)
    from collections import Counter, deque
    #from collections import defaultdict
    from itertools import combinations, permutations, accumulate, groupby
    #from itertools import product
    from bisect import bisect_left,bisect_right
    import heapq
    from math import floor, ceil
    #from operator import itemgetter

    #inf = 10**17
    mod = 10**9 + 7

    s = input().rstrip()
    n = len(s)
    dp = [[0]*13 for _ in range(n)]

    if s[-1]=='?':
        for i in range(10):
            dp[0][i] = 1
    else:
        a = int(s[-1])
        dp[0][a] = 1

    a = 1
    for i in range(1, n):
        a = 10 * a % 13
        if s[-(i+1)] == '?':
            for j in range(10):
                for k in range(13):
                    dp[i][(a*j+k)%13] += dp[i-1][k] % mod
        else:
            j = int(s[-(i+1)])
            for k in range(13):
                dp[i][(a*j+k)%13] += dp[i-1][k] % mod
    print(dp[-1][5]%mod)


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

import sys
 
ma = {}
def _sum(n):
    if not n in ma:
        ma[n] = sum(range(1,n+1))
    return ma[n]

def ev(v):
    return _sum(v) * 1.0/v

N, K = [int(x) for x in sys.stdin.readline().strip().split(" ")]
p = [ev(int(x)) for x in sys.stdin.readline().strip().split(" ")]
 
m = 0
i = 0
while K+i <= N:
    v = 0
    for k in range(K):
        v += p[i+k]
    if m < v:
        m = v
    i += 1
print(m)


### FIXED CODE ###

import sys
 
ma = {}
def _sum(n):
    if not n in ma:
        ma[n] = sum(range(1,n+1))
    return ma[n]

def ev(v):
    return _sum(v) * 1.0/v
 
N, K = [int(x) for x in sys.stdin.readline().strip().split(" ")]
p = [ev(int(x)) for x in sys.stdin.readline().strip().split(" ")]
 

cur = sum([p[i] for i in range(K)])
_max = cur

i = K-1
j = 0

while i < N - 1:
    cur -= p[j]
    i += 1
    j += 1
    cur += p[i]
    if _max < cur:
        _max = cur

print(_max)
### BUGGY CODE ###

def cutter(nums):
    if len(nums) < 2:
        return []
    
    for i in xrange(1, len(nums)):
        if int(nums[i]) != int(nums[i-1]):
            pos = i
            flag = int(nums[i]) > int(nums[i-1])  # is asc?
            # print flag
            break
    else:
        return []

    for i in xrange(pos, len(nums)):

        if flag:
            if int(nums[i]) < int(nums[i-1]):
                return nums[i:]
        else:
            if int(nums[i]) > int(nums[i-1]):
                return nums[i:]
    return []


n = int(raw_input())
arr = raw_input().split()
if n < 2:
    print n
else:
    count = 0
    while arr:
        # print arr
        count += 1
        arr = cutter(arr)

    print count

### FIXED CODE ###

def cutter(nums, idx):
    if len(nums) - idx <= 2:
        return len(nums)
    
    for i in xrange(idx+1, len(nums)):
        if int(nums[i]) != int(nums[i-1]):
            pos = i
            flag = int(nums[i]) > int(nums[i-1])  # is asc?
            # print flag
            break
    else:
        return len(nums)

    for i in xrange(pos, len(nums)):

        if flag:
            if int(nums[i]) < int(nums[i-1]):
                return i
        else:
            if int(nums[i]) > int(nums[i-1]):
                return i
    return len(nums)


n = int(raw_input())
idx = 0
arr = raw_input().split()
if n < 2:
    print n
else:
    count = 0
    while idx < n:
        # print arr[idx:]
        count += 1
        idx = cutter(arr, idx)

    print count
### BUGGY CODE ###

n,m=map(int,input().split());a,b=[],[]
for i in range(n):
  aa,bb=map(int,input().split())
  a.append(aa);b.append(bb)
c=sorted(a)
s,ans=0,0
for i in c:
  j=a.index(i)
  k=min(b[j],m-s)
  s+=k
  ans+=a[j]*k
  a[j]=-1
  if m==s:break
print(ans)

### FIXED CODE ###

n,m=map(int,input().split());d,ans=[],0
for i in range(n):d.append(list(map(int,input().split())))
d.sort()
for i in range(n):
  if d[i][1]<=m:
    ans+=d[i][0]*d[i][1]
    m-=d[i][1]
  else:
    ans+=d[i][0]*m
    m=0
  if m<=0:break
print(ans)