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

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10000)
'''
allinputs = iter(input().splitlines())
input = lambda : next(allinputs)
#'''
H, W = map(int, input().split())
S = [input() for _ in range(H)]

memo = [[[0] * 4 for _ in range(W)] for _ in range(H)]
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]

def dfs(x, y, i):
	nx = x + dx[i]
	ny = y + dy[i]
	if nx >= 0 and nx < H and ny >= 0 and ny < W and S[nx][ny] == '.':
		memo[x][y][i] = dfs(nx, ny, i) + 1
		return memo[x][y][i]
	else:
		return 0
		
ans = 0

for sx in range(H):
	for sy in range(W):
		if S[sx][sy] == '.':
			tmp = 1

			for j in range(4):
				nx = sx + dx[j]
				ny = sy + dy[j]
				if nx >= 0 and nx < H and ny >= 0 and ny < W and memo[nx][ny][j] > 0:
					memo[sx][sy][j] = memo[nx][ny][j] + 1
					tmp += memo[sx][sy][j]
				else:
					tmp += dfs(sx, sy, j)
				
			if tmp > ans:
				ans = tmp
				
print(ans)

### FIXED CODE ###

import sys
input = sys.stdin.readline
'''
allinputs = iter(input().splitlines())
input = lambda : next(allinputs)
#'''
H, W = map(int, input().split())
S = [input() for _ in range(H)]
R = [[0] * W for _ in range(H)]
L = [[0] * W for _ in range(H)]
U = [[0] * W for _ in range(H)]
D = [[0] * W for _ in range(H)]

for i in range(H):
	for j in range(W):
		if S[i][j] == '.':
			if j > 0:
				L[i][j] = L[i][j - 1] + 1
			elif j == 0:
				L[i][j] = 1
				
			if i > 0:
				U[i][j] = U[i - 1][j] + 1
			elif i == 0:
				U[i][j] = 1
		
		if S[i][W - j - 1] == '.':
			if j > 0:
				R[i][W - j - 1] = R[i][W - j] + 1
			elif j == 0:
				R[i][W - j - 1] = 1
		
		if S[H - i - 1][j] == '.':
			if i > 0:
				D[H - i - 1][j] = D[H - i][j] + 1
			elif i == 0:
				D[H - i - 1][j] = 1
			
ans = 0
for i in range(H):
	for j in range(W):
		tmp = L[i][j] + R[i][j] + U[i][j] + D[i][j] - 3
		if tmp > ans:
			ans = tmp
			
print(ans)
### BUGGY CODE ###

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


a_sum = [0]
for i in range(n):
    a_sum.append((a_sum[-1]+a[i]))

val = []
cnt = []
for i in range(n+1):
    idx = bisect.bisect_left(val, a_sum[i])
    if len(val) > idx and val[idx] == a_sum[i]:
        cnt[idx] += 1
    else:
        val.insert(idx, a_sum[i])
        cnt.insert(idx,1)

ans = 0
for i in range(len(cnt)):
    ans += cnt[i]*(cnt[i]-1)//2

print(ans)

### FIXED CODE ###

from collections import Counter

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

a_sum = [0]
for i in range(n):
    a_sum.append((a_sum[-1]+a[i]))

cnt = Counter(a_sum)

ans = 0
for v in cnt.values():
    ans += v*(v-1)//2

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

n, x = map(int, input().split())
c = list(map(int, input().split()))
c = set([abs(x-c[i]) for i in range(n)])
l = min(c)
for i in range(l, 0, -1):
    d = True
    for item in c:
        if item % i != 0:
            d = False
    if d:
        print(i)
        break

### FIXED CODE ###

n, x = map(int, input().split())
c = list(map(int, input().split()))
c = set([abs(x-c[i]) for i in range(n)])
l = min(c)
for i in range(l+1, 0, -1):
    if l % i == 0:
        d = True
        for item in c:
            if item % i != 0:
                d = False
        if d:
            print(i)
            break
### BUGGY CODE ###

N = int(input())
A = list(map(int, input().split()))

for i in range(0, A[0] * 2 + 1, 2):
    M = [i]
    for j in range(N):
        v = 2 * A[j] - M[-1]
        M.append(v)
        if v < 0:
            break
    else:
        if M[0] == M[-1]:
            M = M[:-1]
            # print('M', M)
            print(*M, sep=' ')
            exit()

# 一番小さいi値を 0, 2, 4, .... 2 * M[i]まで総当たりでやってみる


### FIXED CODE ###

import sys
input = sys.stdin.buffer.readline
import numpy as np
N = int(input())
A = np.array(list(map(int, input().split())))
# print(f'{A=}, {A[1::2]=}')

M = [0] * N
M[0] = A.sum() - 2 * A[1::2].sum()

for i in range(N - 1):
    M[i + 1] = 2 * A[i] - M[i]

print(*M, sep=' ')
# A1 + A2 + ... + AN = X1 + X2 + ... + XN = S
# XN+1 = N1とすると
# (Xi + Xi+1) / 2 = Ai
# Xi + Xi+1 = 2 * Ai
# X1 = S - (X2 + ... + XN) = S - 2(A2 + A4 + ... + AN-1)
# Xi+1 = 2Ai - Xi
### BUGGY CODE ###

n = int(input())
s_list = list(str(input()))
r = 0
g = 0
b = 0

for i in range(n):
    if s_list[i] == 'R':
        r += 1
    elif s_list[i] == 'G':
        g += 1
    else:
        b += 1

ans = r * g * b

for d in range(1, n):
    for i in range(n):
        if i + 2 * d < n and \
            s_list[i] != s_list[i + d] and \
            s_list[i] != s_list[i + 2 * d] and \
            s_list[i + d] != s_list[i + 2 * d]:
            ans -= 1

print(ans)


### FIXED CODE ###

n = int(input())
s_list = list(str(input()))
r = 0
g = 0
b = 0

for i in range(n):
    if s_list[i] == 'R':
        r += 1
    elif s_list[i] == 'G':
        g += 1
    else:
        b += 1

ans = r * g * b

for d in range(1, n):
    for i in range(n):
        if i + 2 * d >= n:
            break
        if s_list[i] != s_list[i + d] and \
            s_list[i] != s_list[i + 2 * d] and \
            s_list[i + d] != s_list[i + 2 * d]:
            ans -= 1

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

import sys
sys.setrecursionlimit(1000000)
def dfs(vertex):
  visited[vertex] = True
  if vertex != 0:
    maxlen = 0
    x = a[vertex]
    for (L, z) in table:
      if z < x: # strict increasing
        maxlen = max(maxlen, L)
    table.append((maxlen+1, x))
  ans[vertex] = max(L for (L, _) in table)
  for node in adjacent[vertex]:
    if not visited[node]:
      dfs(node)
  table.pop()
  return
n = int(input())
a = list(map(int, input().split()))
adjacent = {i: [] for i in range(n)}
for _ in range(n-1):
  node1, node2 = map(int, input().split())
  node1 -= 1
  node2 -= 1
  adjacent[node1].append(node2)
  adjacent[node2].append(node1)
visited = [False]*n
ans = [0]*n
table = [(1, a[0])]
dfs(0)
[print(value) for value in ans]

### FIXED CODE ###

import sys
sys.setrecursionlimit(1000000)
from bisect import bisect, bisect_left
def longest_subsequence(sequence):
  subsequence = [float("inf") for _ in range(len(sequence)+1)]
  subsequence[0] = float("-inf")
  for value in sequence:
    j = bisect(subsequence, value)
    if subsequence[j-1] != value: # strict increasing
      subsequence[j] = value
  return bisect_left(dp, float("inf"))-1
# print(longest_subsequence([9, 13, 2, 10, 4, 13, 11, 13]))
# sys.exit()
def dfs(vertex):
  visited[vertex] = True
  value = a[vertex]
  j = bisect(subsequence, value)
  previous = subsequence[j]
  if subsequence[j-1] != value: # strict increasing
    subsequence[j] = value
  ans[vertex] = bisect_left(subsequence, float("inf"))-1
  for node in adjacent[vertex]:
    if not visited[node]:
      dfs(node)
  subsequence[j] = previous
  return
n = int(input())
a = list(map(int, input().split()))
adjacent = {i: [] for i in range(n)}
for _ in range(n-1):
  node1, node2 = map(int, input().split())
  node1 -= 1
  node2 -= 1
  adjacent[node1].append(node2)
  adjacent[node2].append(node1)
visited = [False]*n
ans = [0]*n
subsequence = [float("inf") for _ in range(n+1)]
subsequence[0] = float("-inf")
dfs(0)
[print(value) for value in ans]
### BUGGY CODE ###

n = int(input())

count = 0
for a in range(1,n+1):
  for b in range(1,(n//a)+1):
    if n-b*a > 0:
      count += 1
print(count)

### FIXED CODE ###

n = int(input())

count = 0
for a in range(1,n):
  count += (n-1)//a

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

from collections import deque

def bfs():
  global direction
  d = [0]*n
  que = deque([])
  que.append(0)
  d[0] = 1 #到達済み
  while que:
    now = que.popleft() 
    if d == [1]*n: #全て到達したら終わり
      break
    for next in g[now]: #部屋1から行ける場所で回す
      if d[next] == 0:
        que.append(next)
        d[next] = 1
        direction[next] = now 
  

n,m = map(int,input().split())
g = [[] for i in range(n)]
direction = [0]*n
for i in range(m):
  a,b = map(int,input().split())
  a -= 1
  b -= 1
  g[a].append(b)
  g[b].append(a)
  
bfs()
print('Yes')
for i in range(1,n):
  print(direction[i]+1)

### FIXED CODE ###

from collections import deque
 
def bfs():
  que = deque([])
  que.append(0)
  
  while que:
    now = que.popleft()
    for next in g[now]: #部屋1から行ける場所で回す
      if d[next] == 0:
        que.append(next)
        d[next] = now +1
        
n,m = map(int,input().split())
g = [[] for i in range(n)]
d = [0]*n
for i in range(m):
  a,b = map(int,input().split())
  a -= 1
  b -= 1
  g[a].append(b)
  g[b].append(a)
  
bfs()
print('Yes')
for i in range(1,n):
  print(d[i])
### BUGGY CODE ###

import itertools
n,m,r=map(int,input().split())
rx=[int(i) for i in input().split()]
inf=100000000000
wf=[[inf]*n for i in range(n)]
for i in range(n):
    wf[i][i]=0

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

for k in range(n):
    for i in range(n):
        for j in range(n):
            wf[i][j]=min(wf[i][j],wf[i][k]+wf[k][j])
cnt=0
l=list(itertools.permutations([i for i in range(r)]))
#print(l)
cnt=inf
for i in l:
    cnt_sub=0
    for j in range(r-1):
        cnt_sub+=wf[rx[i[j]]-1][rx[i[j+1]]-1]
    cnt=min(cnt,cnt_sub)
print(cnt)


### FIXED CODE ###

import itertools
n,m,r=map(int,input().split())
rx=[int(i) for i in input().split()]
inf=100000000
wf=[[inf]*n for i in range(n)]
for i in range(n):
    wf[i][i]=0

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

for k in range(n):
    for i in range(n):
        for j in range(n):
            if wf[i][j]>wf[i][k]+wf[k][j]:
                wf[i][j]=wf[i][k]+wf[k][j]
cnt=0
l=list(itertools.permutations([i for i in range(r)]))
cnt=inf
for i in l:
    cnt_sub=0
    for j in range(r-1):
        cnt_sub+=wf[rx[i[j]]-1][rx[i[j+1]]-1]
    cnt=min(cnt,cnt_sub)
print(cnt)
### BUGGY CODE ###

N,A,B,K = map(int,input().split())
MOD = 998244353

def mul(a,b):
    return (a*b) % MOD

def pow(a,n): # a^n
    ret = 1
    mag = a
    while n > 0:
        if n & 1:
            ret = mul(ret, mag)
        mag = mul(mag, mag)
        n >>= 1
    return ret

def inv(a):
    return pow(a, MOD-2)

fac = [1]
#fac_inv = [1]
for n in range (1,N+10):
    f = mul(fac[n-1], n)
    fac.append(f)
#    fac_inv.append(inv(f))

P = 1000
pascal = [None] * (P+1)
pascal[0] = [1,0]
for n in range(1,P+1):
    pascal[n] = [1]
    for r in range(1,n+1):
        pascal[n].append(pascal[n-1][r-1] + pascal[n-1][r])
    pascal[n].append(0)

def ncr(n,r):
    if n <= P:
        return pascal[n][r]
    else:
        return mul(mul(fac[n], inv(fac[n-r])), inv(fac[r]))

ans = 0
for a in range(N+1):
    if a*A > K: break
    rem = K-a*A
    if rem%B: continue
    b = rem//B
    for green in range(min(a,b) + 1):
        red = a - green
        blue = b - green
        if red + green + blue > N: continue
        tmp = 1
        tmp = mul(tmp, ncr(N, red+green+blue))
        tmp = mul(tmp, ncr(red+green+blue, green+blue))
        tmp = mul(tmp, ncr(green+blue, blue))
        ans += tmp
print(ans % MOD)


### FIXED CODE ###

N,A,B,K = map(int,input().split())
if A<B: A,B = B,A
MOD = 998244353

def mul(a,b):
    return (a*b) % MOD

def pow(a,n): # a^n
    ret = 1
    mag = a
    while n > 0:
        if n & 1:
            ret = mul(ret, mag)
        mag = mul(mag, mag)
        n >>= 1
    return ret

def inv(a):
    return pow(a, MOD-2)

fac = [1]
fac_inv = [1]
for n in range (1,N+10):
    f = mul(fac[n-1], n)
    fac.append(f)
    fac_inv.append(inv(f))

mem = [0] * (N+1)
def ncr(n,r):
    if mem[r] > 0:
        return mem[r]
    else:
        ret = mul(mul(fac[n], fac_inv[n-r]), fac_inv[r])
        mem[r] = ret
        return ret

ans = 0
for a in range(N+1):
    if a*A > K: break
    rem = K-a*A
    if rem%B: continue
    b = rem//B
    if b > N: continue
    ans += mul(ncr(N,a), ncr(N,b))
print(ans % MOD)
### BUGGY CODE ###

import sys

input = sys.stdin.readline

def LcpByZ(target):
    len_t = len(target)
    lcp = [-1] * len_t
    top = 1  # 右の箱において、左の箱の0に対応する点
    right = 0  # 左の箱の右端
    lcp[0] = 0
    while top < len_t:
        # 箱を右に広げていく
        while top + right < len_t and target[right] == target[top + right] and right<top:
            right += 1
        # 右の箱左端のlcpを記録
        lcp[top] = right
        left = 1
        # 左端＝右端だったらtopを動かして、このターン終了
        if right == 0:
            top += 1
            continue
        # lcpを記録しながら箱を左に縮めていく（最初の条件重要）
        while left + lcp[left] < right and left < right:
            lcp[top + left] = lcp[left]
            left += 1
        # topを右の箱の左端にして、左の箱を0まで戻す
        top += left
        right -= left
    return max(lcp)

def main():
    n = int(input())
    s = input()[::-1]
    ans=0
    for i in range(n):
        ans=max(ans,LcpByZ(s[i:]))
    print(ans)

main()

### FIXED CODE ###

# YouTube
def main():
    n = int(input())
    s = input()
    dp = [[0] * (n + 1) for _ in range(n + 1)]
    for i, c in enumerate(s):
        for j in range(n):
            if c == s[j]:
                dp[i + 1][j + 1] = dp[i][j] + 1
    ans = 0
    for i in range(n):
        for j in range(i+1,n+1):
            tmp=min(dp[i][j],j-i)
            ans=max(tmp,ans)
    print(ans)

main()
### BUGGY CODE ###

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

for i in range(n):
    b *= a[i]

if b > 10 ** 18:
    print(-1)
else:
    print(b)

### FIXED CODE ###

import sys
input = sys.stdin.readline

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

for i in range(n):
    b *= a[i]
    if b > 10 ** 18:
        b = -1
        break

for i in range(n):
    if a[i] == 0:
        b = 0

print(b)
### BUGGY CODE ###

n = int(input())
L =[list(input()) for i in range(n)]

for i in range(n):
      L[i] = sorted(L[i])
      L[i] = ''.join(L[i])
L = sorted(L)

c=0
for i in range(n):
      c += L[i+1:].count(L[i])
print(c)

### FIXED CODE ###

import sys
input = sys.stdin.readline
 
N=int(input())
dic={}
sum=0
for i in range(N):
    s=list(input())
    s.sort()
    s = "".join(s)
    if s in dic:
        sum+=dic[s]
        dic[s]+=1
    else:
        dic[s]=1
print(sum)
### BUGGY CODE ###

N, Q = map(int, input().split())
edges = [input().split() for _ in range(N-1)]
operations = [input().split() for _ in range(Q)]

tree = {}
counter = [0]*N
result = [0]*N
numbers = []

for o in operations:
    counter[int(o[0])-1] += int(o[1])

result[0] = counter[0]

# print(counter)

for e in edges:
    parent = e[0]
    sun = e[1]
    if sun in numbers:
        sun = e[0]
        parent = e[1]
    else:
        numbers.append(sun)

    if sun in tree:
        tree[sun].append(parent)
    else:
        tree[sun] = [parent]

    if parent in tree:
        tree[sun].extend(tree[parent])


# print(tree)

for k in tree.keys():
    result[int(k)-1] += counter[int(k) - 1]
    for i in tree[k]:
        result[int(k)-1] += counter[int(i)-1]

print(' '.join(map(str, result)))

### FIXED CODE ###

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

tree = [[] for _ in range(N)]
result = [0]*N

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

for _ in range(Q):
    p, x = map(int, input().split())
    result[p-1] += x

for i in range(N - 1):
    for j in tree[i]:
        result[j-1] += result[i]

print(' '.join(map(str, result)))
### BUGGY CODE ###

n , m = map(int,input().split())
p = {i+1 for i in range(n)}
for i in range(m):
    l , r = map(int,input().split())
    s = {l+i for i in range(r-l+1)}
    p = p & s

print(len(p))


### FIXED CODE ###

n , m = map(int,input().split())
l=[]
r=[]
for i in range(m):
    x , y = map(int,input().split())
    l.append(x)
    r.append(y)

a = max(l)
b = min(r)
if a > b:
    print(0)
else:
    print(b-a+1)
### BUGGY CODE ###

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

li = li + [0]*k
dp = [10**9]*(n+k)
dp[0] = 0
for i in range(n):
  for j in range(k):
    dp[i+j+1] = min(dp[i+j+1],dp[i] + abs(li[i]-li[i+j+1]))
print(dp[n-1])

### FIXED CODE ###

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

li = li + [0]*k
dp = [10**9]*(n+k)
dp[0] = 0
for i in range(n):
  for j in range(k):
    dp[i+j+1] = min(dp[i+j+1],dp[i] + abs(li[i]-li[i+j+1]))
print(dp[n-1])
### BUGGY CODE ###

import sys
input = sys.stdin.readline
r,c,k = map(int,input().split())
l = [[0]*c for i in range(r)]

for i in range(k):
    x,y,v = map(int,input().split())
    l[x-1][y-1] = v

dp = [[[0]*4 for i in range(c+1)] for j in range(r+1)]

for i in range(r):
    for j in range(c):
        M = max(dp[i][j+1])
        if l[i][j] > 0:
            v = l[i][j]
            dp[i+1][j+1][0] = max(M,dp[i+1][j][0])
            dp[i+1][j+1][1] = max(M+v,dp[i+1][j][0]+v,dp[i+1][j][1])
            dp[i+1][j+1][2] = max(dp[i+1][j][1]+v,dp[i+1][j][2])
            dp[i+1][j+1][3] = max(dp[i+1][j][2]+v,dp[i+1][j][3])
        else:
            dp[i+1][j+1][0] = max(M,dp[i+1][j][0])
            dp[i+1][j+1][1] = dp[i+1][j][1]
            dp[i+1][j+1][2] = dp[i+1][j][2]
            dp[i+1][j+1][3] = dp[i+1][j][3]
print(max(dp[-1][-1]))

### FIXED CODE ###

import sys
input = sys.stdin.readline
r,c,k = map(int,input().split())
l = [[0]*c for i in range(r)] 
for i in range(k):
    x,y,v = map(int,input().split())
    l[x-1][y-1] = v
dp = [[0]*4 for i in range(c+1)]

for i in range(r):
    ndp = [[0]*4 for i in range(c+1)]
    for j in range(c):
        M = max(dp[j+1])
        if l[i][j]>0:
            v = l[i][j]
            ndp[j+1][0] = max(M,dp[j][0],ndp[j][0])
            ndp[j+1][1] = max(M+v,dp[j][0]+v,ndp[j][0]+v,dp[j][1],ndp[j][1])
            ndp[j+1][2] = max(dp[j][1]+v,ndp[j][1]+v,dp[j][2],ndp[j][2])
            ndp[j+1][3] = max(dp[j][2]+v,ndp[j][2]+v,dp[j][3],ndp[j][3])
        else:
            ndp[j+1][0] = max(M,dp[j][0],ndp[j][0])
            ndp[j+1][1] = max(dp[j][1],ndp[j][1])
            ndp[j+1][2] = max(dp[j][2],ndp[j][2])
            ndp[j+1][3] = max(dp[j][3],ndp[j][3])
    dp = ndp
print(max(dp[-1]))
### BUGGY CODE ###

# "#"=black, "."=white
import copy

H, W = map(int, input().split())
HW = []
for i in range(H):
  HW.append(list(input()))
# print(HW)

def whiteCount(HWlist):
  return [flatten for inner in HWlist for flatten in inner].count(".")    

pHW = copy.deepcopy(HW)
turnCnt=0
while(whiteCount(HW)):
  for i in range(H):
    for j in range(W):
      if HW[i][j] == ".":
        if (i > 0 and HW[i-1][j] == "#") or \
           (i < H-1 and HW[i+1][j] == "#") or \
           (j > 0 and HW[i][j-1] == "#") or \
           (j < W-1 and HW[i][j+1] == "#"):
          pHW[i][j] = "#"
  turnCnt += 1
  HW = copy.deepcopy(pHW)
  # print(pHW)
print(turnCnt)


### FIXED CODE ###

from collections import deque
h, w = map(int, input().split())

field = [] # 白黒情報を持つリスト
mark = [] # 操作回数を保持するリスト
INF = 10**6

for i in range(h):
    field.append(list(input()))
    mark.append([0 for i in range(w)])

dx = [1, 0, -1, 0]
dy = [0, 1, 0, -1]

queue = deque()
for i in range(h):
    for j in range(w):
        if field[i][j] == "#":
            queue.append([i, j])

while len(queue) > 0:
    y, x = queue.popleft()
    for k in range(4):
        nx = x + dx[k]
        ny = y + dy[k]
        if 0 <= ny < h and 0 <= nx < w:
            if field[ny][nx] == ".":
                mark[ny][nx] = mark[y][x] + 1
                queue.append([ny, nx])
                field[ny][nx] = "#"

ans=0

for i in mark:
    ans = max(ans, max(i))

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

import math
import copy
import fractions
import numpy as np
from functools import reduce

# ===FUNCTION===

def getInputNum():
    inputNum = int(input())
    return inputNum

def getInputListInt():
    outputoData = []
    inputData = input().split()
    outputData = [int(n) for n in inputData]

    return outputData

def getSomeInputInt(n):
    outputDataList = []
    for i in range(n):
        inputData = int(input())
        outputDataList.append(inputData)

    return outputDataList

def getSomeInputListInt(n):
    inputDataList = []
    outputDataList = []
    for i in range(n):
        inputData = input().split()
        inputDataList = [int(n) for n in inputData]
        outputDataList.append(inputDataList)

    return outputDataList

# ===CODE===

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

dataSorted = sorted(data, key=lambda x:x[0])

cnt = 0
ans = 0

while cnt != m:
    for i in range(len(dataSorted)):
        if dataSorted[i][1] != 0:
            cnt += 1
            ans += dataSorted[i][0]
            dataSorted[i][1] -=1
            break
        else:
            continue

print(ans)

### FIXED CODE ###

import math
import copy
import fractions
import numpy as np
from functools import reduce

# ===FUNCTION===

def getInputNum():
    inputNum = int(input())
    return inputNum

def getInputListInt():
    outputoData = []
    inputData = input().split()
    outputData = [int(n) for n in inputData]

    return outputData

def getSomeInputInt(n):
    outputDataList = []
    for i in range(n):
        inputData = int(input())
        outputDataList.append(inputData)

    return outputDataList

def getSomeInputListInt(n):
    inputDataList = []
    outputDataList = []
    for i in range(n):
        inputData = input().split()
        inputDataList = [int(n) for n in inputData]
        outputDataList.append(inputDataList)

    return outputDataList

# ===CODE===

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

dataSorted = sorted(data, key=lambda x:x[0])

dataSum = np.zeros(n)

for i in range(n):
    dataSum[i] = dataSorted[i][1]
    if i == 0:
        continue
    else:
        dataSum[i] += dataSum[i-1]

tmpNum = 0
tmpSa = 0
for i in range(n):
    if dataSum[i] >= m:
        tmpNum = i
        if i == 0:
            tmpSa = m
            break
        else:
            tmpSa = m - dataSum[i-1]
            break

ans = 0
for i in range(tmpNum):
    ans += dataSorted[i][0] * dataSorted[i][1]

ans += dataSorted[tmpNum][0] * tmpSa

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

mod = 10**9+7

def combi(m,n):
    child = 1
    mom = 1
    while n != 0:
        child *= m
        child %= mod
        mom *= n
        mom %= mod
        m -= 1
        n -= 1
    return (child*modpow(mom,mod-2))%mod

def modpow(m,n):
    if n == 0:
        return 1
    if n % 2:
        return ((modpow(m,n//2)**2)*m)%mod
    else:
        return (modpow(m,n//2)**2)%mod

X,Y = map(int,input().split())

A = (-1) * X +   2  * Y
B =   2  * X + (-1) * Y

if A % 3 or B % 3:
    print(0)
    exit()

A //= 3
B //= 3

print(combi(A+B,min(A,B)))

### FIXED CODE ###

mod = 10**9+7

FRAC_RANGE = 2000000
frac = [1] * FRAC_RANGE

for i in range(2,FRAC_RANGE):
    frac[i] = frac[i-1] * i % mod

def combi(n,k):
    a = frac[n]
    b = modpow(frac[k],mod-2)
    c = modpow(frac[n-k],mod-2)
    return a*b*c%mod

def bi(x):
    o = []
    while x != 0:
        o.append(x%2)
        x //= 2
    return o

def modpow(m,n):
    o = bi(n)
    p = [m]
    leo = len(o)
    while leo > len(p):
        a = p[-1]
        p.append(a*a%mod)
    b = 1
    for i in range(leo):
        if o[i] == 1:
            b *= p[i]
            b %= mod
    return b

X,Y = map(int,input().split())

A = (-1) * X +   2  * Y
B =   2  * X + (-1) * Y

if A % 3 or B % 3 or A < 0 or B < 0:
    print(0)
    exit()

A //= 3
B //= 3

print(combi(A+B,min(A,B)))
### BUGGY CODE ###

a, b, k = map(int, input().split())
for i in range(a, b + 1):
    if (a <= i) and (i <= (a + k -1)):
        print(i)
    elif ((b - k + 1) <= i) and (i <= b):
        print(i)

### FIXED CODE ###

a, b, k = map(int, input().split())
for i in range(a, min(b + 1, a + k)):
    print(i)
for i in range(max(a + k, b - k + 1), b + 1):
    print(i)
### BUGGY CODE ###

def resolve():
    n, m = map(int, input().split())
    lst = [list(map(int, input().split())) for _ in range(m)]

    ans = set(range(lst[0][0], lst[0][1] + 1))
    for l in lst[1:]:
        ans = ans.intersection(set(range(l[0], l[1] + 1)))

    print(len(ans))


resolve()


### FIXED CODE ###

def resolve():
    n, m = map(int, input().split())
    lst = [list(map(int, input().split())) for _ in range(m)]

    prev = lst[0]
    for new in lst[1:]:
        prev = [max(prev[0], new[0]), min(prev[1], new[1])]

    print(len(range(prev[0], prev[1]+1)))


resolve()