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

# classを使うのをやめてlistで実施する
from collections import deque
import sys
sys.setrecursionlimit(10 ** 9)
import sys
input = sys.stdin.readline

def dfs(v):
    visited[v] = True
    for i in range(len(AL[v][CHILDREN])):
        u = AL[v][CHILDREN][i]
        if visited[u]:
            AL[v][CHILDREN][i] = None
            continue
        AL[v][SIZE] += dfs(u)
    return AL[v][SIZE]

def anaaki(v):
    ret = pow(2, n - 1, p) - 1
    for ch in AL[v][CHILDREN]:
        if ch is None: continue
        ret -= pow(2, AL[ch][SIZE], p) - 1
        ret %= p
    ret -= pow(2, n - AL[v][SIZE], p) - 1
    ret %= p
    return ret

n = int(input())
SIZE = 0
CHILDREN = 1
AL = [[1, []] for _ in range(n)]
visited = [False] * n
p = 10 ** 9 + 7
for i in range(n - 1):
    a, b = [int(x) - 1 for x in input().split()]
    AL[a][CHILDREN].append(b)
    AL[b][CHILDREN].append(a)

dfs(0)
numer = 0
for i in range(n):
    numer += anaaki(i)
    numer %= p

denom = pow(2, n, p)
print(numer * pow(denom, p - 2, p) % p)

### FIXED CODE ###

# classを使うのをやめてlistで実施する
from collections import deque
import sys
sys.setrecursionlimit(10 ** 9)
import sys
input = sys.stdin.readline

def dfs(v):
    visited[v] = True
    for i in range(len(AL[v][CHILDREN])):
        u = AL[v][CHILDREN][i]
        if visited[u]:
            AL[v][CHILDREN][i] = None
            continue
        AL[v][SIZE] += dfs(u)
    return AL[v][SIZE]


def anaaki(v):
    ret = powp - 1
    for ch in AL[v][CHILDREN]:
        if ch is None: continue
        ret -= pow(2, AL[ch][SIZE], p) - 1
        ret %= p
    ret -= pow(2, n - AL[v][SIZE], p) - 1
    ret %= p
    return ret

n = int(input())
SIZE = 0
CHILDREN = 1
AL = [[1, []] for _ in range(n)]
visited = [False] * n
p = 10 ** 9 + 7
powp = pow(2, n - 1, p)

for i in range(n - 1):
    a, b = [int(x) - 1 for x in input().split()]
    AL[a][CHILDREN].append(b)
    AL[b][CHILDREN].append(a)

dfs(0)
numer = 0
for i in range(n):
    numer += anaaki(i)
    numer %= p

denom = pow(2, n, p)
print(numer * pow(denom, p - 2, p) % p)
### BUGGY CODE ###

import sys
def inpl(): return list(map(int, sys.stdin.readline().split()))
n = int(sys.stdin.readline())
a = inpl()
count = 0
maxx = max(a)
minn = min(a)
for i in range(n):
    for j in range(i+1, n):
        if a[i] + maxx < j-i:
            break
        elif a[i] + minn > j-i:
            continue
        if a[i] + a[j] == j - i:
            count += 1
print(count)

### FIXED CODE ###

import sys
def inpl(): return list(map(int, sys.stdin.readline().split()))
n = int(sys.stdin.readline())
a = inpl()
dic ={}
res = 0
for i in range(n):
    res += dic.get(i - a[i], 0)
    dic[i + a[i]] = dic.get(i + a[i], 0) + 1

print(res)
### BUGGY CODE ###

# -*- coding: utf-8 -*-
#ABC137C
import copy
import sys
import math

n = int(input())
#tmp = input().split()
#hoge = list(map(lambda a: int(a), tmp))
#k=hoge[0]
#x=hoge[1]

#list = [[0 for i in range(26)] for j in range(n)]
fuga = [[0 for i in range(10)] for j in range(n)]
#list[0][1]=1
#print(list)


for i in range(0,n):
	tmp=input()
	for j in range(0,10):
		fuga[i][j]=ord(tmp[j])
	fuga[i].sort()

sum=0
for i in range(0,n-1):
	for j in range(i+1,n):
		for k in range(0,10):
			if(fuga[i][k]!=fuga[j][k]):
				break
			elif(k==9):
				sum+=1
#print(fuga)
print(sum)

#print(list)
#print(list[0][:])



### FIXED CODE ###

# -*- coding: utf-8 -*-
#ABC137C
import copy
import sys
import math

n = int(input())
fuga = [0 for i in range(10)]

wordlist={}
for i in range(0,n):
	tmp=input()
	for j in range(0,10):
		fuga[j]=tmp[j]
	fuga.sort()
	hoge=fuga[0]+fuga[1]+fuga[2]+fuga[3]+fuga[4]+fuga[5]+fuga[6]+fuga[7]+fuga[8]+fuga[9]

	if(hoge in wordlist):
		wordlist[hoge]+=1
	else:
		wordlist[hoge]=1

#print(hoge)
#print(wordlist)

total=0
for i in wordlist:
	t=wordlist[i]
	if(t>=2):
		total+=t*(t-1)//2


print(total)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**7)


N, Q = map(int, input().split())
G = [[] for _ in range(N)]
P = [0 for _ in range(N)]

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

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


def dfs(current, parent):
    for child in G[current]:
        if child == parent:
            continue
        P[child] += P[current]
        dfs(child, current)


dfs(0, -1)

print(' '.join([str(p) for p in P]))


### FIXED CODE ###

import sys
input = sys.stdin.readline #for input speed
sys.setrecursionlimit(10**6) #for deep recursion

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

v = [[] for i in range(N)]
score = [0]*N

def dfs(cur,par):
  for chi in v[cur]:
    if chi == par:
      continue
    score[chi] += score[cur]
    dfs(chi, cur)
      
for i in range(N-1):
  a, b = map(int, input().split())
  a -= 1
  b -= 1
  v[a].append(b)
  v[b].append(a)

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

dfs(0,-1)
score_int=[str(a) for a in score]
output= ' '.join(score_int)
print(output)
### BUGGY CODE ###

N = int(input())
S = input()

ans = set()

for i in range(N - 2):
    for j in range(i + 1, N - 1):
        for k in range(j + 1, N):
            ans.add(S[i] + S[j] + S[k])

print(len(ans))


### FIXED CODE ###

N = int(input())
S = input()

ans = 0
for i in range(10):
    for j in range(10):
        for k in range(10):
            fi = S.find(str(i))
            if fi < 0:
                continue
            fj = S[fi+1:].find(str(j))
            if fj < 0:
                continue
            fk = S[fi+fj+2:].find(str(k))
            if fk < 0:
                continue
            ans += 1

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

import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits

def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 998244353

def power(x, y):
   if y == 0:
       return 1
   elif y == 1:
       return x % mod
   elif y % 2 == 0:
       return power(x, y/2) ** 2 % mod
   else:
       return power(x, (y-1)/2) ** 2 * x % mod
N = INT()
a = [INT() for _ in range(N)]

sum_a = sum(a)
dp = [[0]*(sum_a+1) for _ in range(N+1)]
dp[0][0] = 1

dp2 = [[0]*(sum_a+1) for _ in range(N+1)]
dp2[0][0] = 1

for i, x in enumerate(a):
	for j in range(sum_a+1):
		if j+x >= sum_a+1:
			continue
		dp[i+1][j] = (dp[i+1][j] + dp[i][j]*2) # 赤以外に塗り分ける
		dp[i+1][j+x] = (dp[i+1][j+x] + dp[i][j]) # 赤に塗り分ける
		dp2[i+1][j] += dp2[i][j]
		dp2[i+1][j+x] += dp2[i][j]
# print(dp)
# print(dp2)
if sum_a%2 == 0:
	print((3**N-3*sum([dp[N][i] for i in range(sum_a+1) if i >= sum_a//2])+3*dp2[N][sum_a//2])%mod)
else:
	print((3**N-3*sum([dp[N][i] for i in range(sum_a+1) if i >= sum_a//2+1]))%mod)


### FIXED CODE ###

import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
import numpy as np

def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 998244353

def power(x, y):
   if y == 0:
       return 1
   elif y == 1:
       return x % mod
   elif y % 2 == 0:
       return power(x, y/2) ** 2 % mod
   else:
       return power(x, (y-1)/2) ** 2 * x % mod

N = INT()
a = np.array([INT() for _ in range(N)])

sum_a = np.sum(a)
dp = np.zeros((N+1, sum_a+1))
dp[0][0] = 1

dp2 = np.zeros((N+1, sum_a//2+1))
dp2[0][0] = 1

for i, x in enumerate(a):
	dp[i+1, :] += dp[i, :]*2 % mod # 赤以外に塗り分ける
	dp[i+1, x:] += dp[i, :-x] % mod # 赤に塗り分ける
	dp2[i+1,:] += dp2[i, :] % mod
	dp2[i+1, x:] += dp2[i, :-x] % mod
# print(dp)
# print(dp2)
if sum_a%2 == 0:
	print(int((power(3, N)-3*np.sum(dp[N,sum_a//2:])+3*dp2[N,sum_a//2])%mod))
else:
	print(int((power(3, N)-3*np.sum(dp[N,sum_a//2+1:]))%mod))
### BUGGY CODE ###

# coding: utf-8
# Your code here!

# coding: utf-8
# Your code here!
# coding: utf-8
import sys
sys.setrecursionlimit(10000000)

#const
dxdy=((1,0),(0,1))
# my functions here!
def pin(type=int):
    return map(type,input().rstrip().split())

def resolve():  
    N=int(input())
    S=input()
    r,g,b=[],[],[]
    for i,s in enumerate(S):
        if s=="R":r.append(i)
        elif s=="B":b.append(i)
        else: g.append(i)
    #print(r,g,b)
    #RGBのリストが作れたので、このうち１個ずつとっていけば
    #<1>の条件を満たすことができる（ijkの順序が決まっていることから、
    #最後にこれらが<2>を満たすことを確認する？または、満たさないものを除く
    #<2> i<=j<=k　に対して　j-i = k-j でない
    #"この式を整理すると"k-j*2+i=0ではない:i+j+k=j*3ではない
    #逆にこの式を満たす（平均の関係になっているなら、jは必ず真ん中になる
    
    cnt=0
    for R in r:
        for G in g:
            t=0
            for B in b:
                temp= R+G+B
                
                if temp==R*3 or temp==G*3 or temp == B*3:
                    t+=1
                if t==3:
                    cnt+=t
                    break
                
            if t<3:
                cnt+=t   
                    #print(R,G,B)
    print(len(r)*len(g)*len(b)-cnt)
        
"""         
#printデバッグ消した？
#前の問題の結果見てないのに次の問題に行くの？
"""
"""
お前カッコ閉じ,るの忘れてるだろ
"""
import sys
from io import StringIO
import unittest


class TestClass(unittest.TestCase):
    def assertIO(self, input, output):
        stdout, stdin = sys.stdout, sys.stdin
        sys.stdout, sys.stdin = StringIO(), StringIO(input)
        resolve()
        sys.stdout.seek(0)
        out = sys.stdout.read()[:-1]
        sys.stdout, sys.stdin = stdout, stdin
        self.assertEqual(out, output)

    def test_入力例_1(self):
        input = """4
RRGB"""
        output = """1"""
        self.assertIO(input, output)

    def test_入力例_2(self):
        input = """39
RBRBGRBGGBBRRGBBRRRBGGBRBGBRBGBRBBBGBBB"""
        output = """1800"""
        self.assertIO(input, output)


if __name__ == "__main__":
    #unittest.main()
    resolve()


### FIXED CODE ###

#%%code
def resolve():
    N=int(input())
    S=input()
    RGB=[0,0,0]
    subcnt=0
    for i,c in enumerate(S):
        if c=="R":RGB[0]+=1
        if c=="G":RGB[1]+=1
        if c=="B":RGB[2]+=1
            
        for j in range(i+1,N):
            s=S[j]
            k=j*2-i
            if k<N :
                x=S[k]
                if   x!=s and s!=c and x!=c :
                    #print(i,j,k)
                    
                    subcnt+=1
            else:break

    #print(RGB,subcnt)
    A=RGB[0]*RGB[1]*RGB[2]
    print(A-subcnt)
            
#%%submit!
resolve()
### BUGGY CODE ###

import math
n = int(input())
for f in range(1,n+1):
	try:
		l = int(-1+math.sqrt(-2+f)+0.999)
	except:
		print(0)
		continue
	e = 0
	for x in range(1,l+1):
		for y in range(1,l+1):
			try:
				q = (-(x+y)+math.sqrt((x+y)**2-4*(x**2+y**2+x*y-f)))/2
				if q==int(q) and q >= 1:
					e += 1
			except:
				pass
	print(e)

### FIXED CODE ###

n = int(input())
ret = [0 for _ in range(1,n+1)]
def f(x,y,z):
	return x*x + y*y + z*z + x*y + y*z + x*z

for x in range(1,n+1):
	for y in range(1,n+1):
		for z in range(1,n+1):
			if f(x,y,z) > n:
				z = 1
				break
			ret[f(x,y,z)-1] += 1
		if f(x,y,z) > n:
			y = 1
			break
	if f(x,y,z) > n:
		x = 1
		break

for i in ret:
	print(i)
### BUGGY CODE ###

import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,queue,copy

sys.setrecursionlimit(10**7)
inf=10**20
mod=10**9+7
dd=[(-1,0),(0,1),(1,0),(0,-1)]
ddn=[(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return input()

def main():
  h,w,d=LI()
  l1=[LI() for _ in range(h)]
  q=I()
  l2=[LI() for _ in range(q)]

  ans=[]
  for a,b in l2:
    _ans=0
    ff=True
    f1=f2=False
    _x=_y=0
    while True:
      for i,x in enumerate(l1):
        for j,y in enumerate(x):
          if a==y:
            if b==a:
              if ff:
                ff=False
              else:
                _ans+=abs(_x-i)+abs(_y-j)
              ans.append(_ans)
              f1=f2=True
              break
            else:
              if ff:
                ff=False
              else:
                _ans+=abs(_x-i)+abs(_y-j)
              _x=i
              _y=j
              a+=d
        if f1:
          break
      if f2:
        break

  for x in ans:
    print(x)

main()
# print(main())


### FIXED CODE ###

import math,itertools,fractions,heapq,collections,bisect,sys,queue,copy

sys.setrecursionlimit(10**7)
inf=10**20
mod=10**9+7
dd=[(-1,0),(0,1),(1,0),(0,-1)]
ddn=[(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
# def LF(): return [float(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return input()

def main():
  h,w,d=LI()
  l=[LI() for _ in range(h)]

  q=I()
  ql=[LI() for _ in range(q)]

  dic={}
  for i in range(h):
    for j in range(w):
      x=l[i][j]
      dic[x]=(i+1,j+1)

  n=h*w
  to_last_distance=[0]*n
  for i in range(1,n+1)[::-1]:
    if i+d<=n:
      i_y,i_x=dic[i]
      ipd_y,ipd_x=dic[i+d]
      to_last_distance[i-1]=to_last_distance[i+d-1]
      to_last_distance[i-1]+=(abs(i_y-ipd_y)+abs(i_x-ipd_x))

  # print(to_last_distance)

  ans=[]
  for st,ed in ql:
    ans.append(to_last_distance[st-1]-to_last_distance[ed-1])

  for x in ans:
    print(x)

main()
# print(main())
### BUGGY CODE ###

#n,m = map(int,input().split())
#h = list(map(int,input().split()))

#ab = [map(int,input().split()) for _ in range(m)]
#a,b = [list(i) for i in zip(*ab)]

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

cnt=0

for i in range(n-1):
    for j in range(i+1,n):
        if j-i==a[j]+a[i]:
            #print(i,j)
            cnt+=1
        
print(cnt)


    

### FIXED CODE ###

#n,m = map(int,input().split())
#h = list(map(int,input().split()))

#ab = [map(int,input().split()) for _ in range(m)]
#a,b = [list(i) for i in zip(*ab)]

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

cnt=0
"""
for i in range(n-1):
    for j in range(i+1,n-1):
        if j-i==a[j]+a[i]:
            #print(i,j)
            cnt+=1

"""

R=dict()
L=dict()

for i in range(n):
    if a[i]+i+1 in R:
        R[a[i]+i+1]+=1
    else:
        R[a[i]+i+1]=1

    if i+1-a[i] in L:
        L[i+1-a[i] ]+=1
    else:
        L[i+1-a[i] ]=1


for i in R:
    if i in L:
        cnt+=R[i]*L[i]

print(cnt)
### BUGGY CODE ###

N = int(input())

ans = 0
for i in range(1,N+1):
    y = int(N/i)
    ans += int(1/2*y*(y+1)*i)
    
print(ans)


### FIXED CODE ###

N = int(input())

ans = 0
for i in range(1,N+1):
    y = N//i
    ans += y*(y+1)*i//2
    
print(ans)
### BUGGY CODE ###

from collections import*
import sys
sys.setrecursionlimit(10**8)
input=sys.stdin.readline

n=int(input())
d={}

q=[]
for i in range(n-1):
    a,b=map(int,input().split())
    if a not in d:
        d[a]=[]
    if b not in d:
        d[b]=[]
    d[b].append(a)
    d[a].append(b)        
    q.append(tuple(sorted([a,b])))

m=max(map(len,d.values()))
print(m)

dcolars={}

def BFS(d,point,c):
    colar=deque(range(1,m+1))
    for i in d[point]:
        if tuple(sorted([point,i])) not in dcolars:
            ckamo=colar.pop()
            if c==ckamo:
                colar.appendleft(ckamo)
                ckamo=colar.pop()
            dcolars[tuple(sorted([point,i]))]=ckamo
            BFS(d,i,ckamo)
    return dcolars

ans=BFS(d,1,0)

for i in q:
    print(ans[i])

### FIXED CODE ###

from collections import*
import sys
sys.setrecursionlimit(10**8)
input=sys.stdin.readline

n=int(input())
d={}

q=[]
for i in range(n-1):
    a,b=map(int,input().split())
    if a not in d:
        d[a]=[]
    if b not in d:
        d[b]=[]
    d[b].append(a)
    d[a].append(b)        
    q.append(tuple(sorted([a,b])))

m=max(map(len,d.values()))
print(m)

dcolars={}

def BFS(d,point,c):
    for i in d[point]:
        if tuple(sorted([point,i])) not in dcolars:
            c+=1
            if c==m+1:
                c=1
            dcolars[tuple(sorted([point,i]))]=c
            BFS(d,i,c)
    return dcolars

ans=BFS(d,1,0)

for i in q:
    print(ans[i])
### BUGGY CODE ###

from collections import Counter
import sys

sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline


def f(c1, c2, c3, s):
    if dp[c1][c2][c3] is not None:
        return dp[c1][c2][c3]

    res = n
    if c1 != 0:
        res += f(c1 - 1, c2, c3, s - 1) * c1
    if c2 != 0:
        res += f(c1 + 1, c2 - 1, c3, s) * c2
    if c3 != 0:
        res += f(c1, c2 + 1, c3 - 1, s) * c3
    res /= s
    dp[c1][c2][c3] = res
    return res


n = int(input())
a = tuple(map(int, input().split()))

dp = tuple(
    tuple(
        [None] * (n + 1) for _ in range(n + 1)
    ) for _ in range(n + 1))
dp[0][0][0] = 0
# dp[x][y][z]:=1,2,3個の皿がx,y,z残っているときの期待値

c = Counter(a)
c1 = c[1]
c2 = c[2]
c3 = c[3]

print(f(c1, c2, c3, c1 + c2 + c3))

# dp[now] =
# 1
# + dp[1個の皿を食べた] * p
# + dp[2個の皿を食べた] * p
# + dp[3個の皿を食べた] * p
# + dp[0個の皿を食べた==now] * p


### FIXED CODE ###

def main():
    from collections import Counter

    n = int(input())
    a = tuple(int(x) for x in input().split())

    c = Counter(a)
    c1 = c[1]
    c2 = c[2]
    c3 = c[3]

    x1 = 310 ** 2
    x2 = 310

    dp = [0.0] * (310 ** 3)
    dp[0] = 0.0
    # dp[x * x1 + y * x2 + z]:=1,2,3個の皿がx,y,z残っているときの期待値

    for r3 in range(c3 + 1):
        d3 = c3 - r3
        for r2 in range(c2 + d3 + 1):
            for r1 in range(c1 + d3 + c2 - r2 + 1):
                ind = r1 * x1 + r2 * x2 + r3
                if ind != 0:
                    dp[ind] = (n \
                               + (dp[ind - x1] * r1 if r1 > 0 else 0) \
                               + (dp[ind + x1 - x2] * r2 if r2 > 0 else 0) \
                               + (dp[ind + x2 - 1] * r3 if r3 > 0 else 0)) \
                              / (r1 + r2 + r3)

    print(dp[c1 * x1 + c2 * x2 + c3])


if __name__ == '__main__':
    main()

# dp[now] =
# 1
# + dp[1個の皿を食べた] * p
# + dp[2個の皿を食べた] * p
# + dp[3個の皿を食べた] * p
# + dp[0個の皿を食べた==now] * p

# if mainの追加
# 初期値None->-1.0にした
# checked配列を辞めた
# チェック済みかどうかの判定を-1.0と一致するかの比較にした

# カウントはCounterを使う方が速い
# 1次元にした
# resの加算を複数回に分けると
# 三項演算子より遅くなる
# 再帰関数を辞めた
### BUGGY CODE ###

def f_pond_skater():
    from fractions import Fraction
    from heapq import heappop, heappush
    from math import ceil
    H, W, K = [int(i) for i in input().split()]
    start_row, start_col, target_row, target_col = [int(i) - 1 for i in input().split()]
    Grid = [input() for _ in range(H)]

    def is_inside(row, col):
        return (0 <= row < H) and (0 <= col < W)

    dp = [[[float('inf')] * 4 for j in range(W)] for i in range(H)]
    dr, dc = (0, -1, 0, 1), (-1, 0, 1, 0)  # '0123' と '左上右下' を対応
    queue = [(0, start_row, start_col, i) for i in range(4)]
    while queue:
        cost, row, col, direction = heappop(queue)
        dp[row][col][direction] = cost

        # 1マス直進する
        nr, nc = row + dr[direction], col + dc[direction]
        if (is_inside(nr, nc) and Grid[nr][nc] == '.' and
                dp[nr][nc][direction] > cost + Fraction(1, K)):
            heappush(queue, (dp[row][col][direction] + Fraction(1, K), nr, nc, direction))

        # 向きを 90 度変える
        for i in (1, 3):
            if dp[row][col][(direction + i) % 4] > ceil(float(cost)):
                heappush(queue, (ceil(float(cost)), row, col, (direction + i) % 4))

    ans = min(dp[target_row][target_col][d] for d in range(4))
    return ceil(float(ans)) if ans != float('inf') else -1

print(f_pond_skater())


### FIXED CODE ###

def f_pond_skater():
    from heapq import heappush, heappop
    H, W, K = [int(i) for i in input().split()]
    start_row, start_col, target_row, target_col = [int(i) - 1 for i in input().split()]
    Grid = [input() for _ in range(H)]

    heap = []
    dist = [[float('inf')] * W for _ in range(H)]
    dist[start_row][start_col] = 0

    diff = ((0, 1), (1, 0), (0, -1), (-1, 0))
    heappush(heap, (0, start_row, start_col))
    while heap:
        cost, row, col = heappop(heap)
        cost_next = cost + 1

        if row == target_row and col == target_col:
            return cost

        for dr, dc in diff:
            nr, nc = row, col
            for _ in range(K):
                nr += dr
                nc += dc
                if not (0 <= nr < H and 0 <= nc < W) or Grid[nr][nc] == '@':
                    break
                if dist[nr][nc] > cost_next:
                    dist[nr][nc] = cost_next
                    heappush(heap, (cost_next, nr, nc))
                elif dist[nr][nc] == cost_next:
                    continue
                else:
                    break
    return -1

print(f_pond_skater())
### BUGGY CODE ###

N =  int(input())
S = [input() for _ in range(N)]
S = [s for s in S if "AB" in s or s[0] == "B" or s[-1] == "A"]
n = len(S)

import itertools
perm = itertools.permutations
ans = 0
for per in perm(S, n):
  x = "".join(per)
  ans = max(ans, x.count("AB"))
print(ans)


### FIXED CODE ###


N =  int(input())
S = [input() for _ in range(N)]

cnt = 0
b, a = 0, 0
ab = 0
for s in S:
  cnt += s.count("AB")
  if s[0] == "B" and s[-1] == "A":
    ab += 1
  elif s[0] == "B":
    b += 1
  elif s[-1] == "A":
    a += 1
if ab > 1:
  cnt += ab-1
  ab = 1
if ab:
  if a:
    cnt += 1
    a -= 1
  if b:
    cnt += 1
    b -= 1
at = 0
bt = 0
while a > 0 and b > 0:
  if a:
    at += 1
    a -= 1
  if b:
    bt += 1
    b -= 1
  if at + bt == 2:
    cnt += 1
  at = 0
  bt = 0
print(cnt)
### BUGGY CODE ###

n = int(input())
*l, = map(int, input().split())

for i in range(n):
    _l = l[:]
    _l.pop(i)
    _l.sort()
    print(_l[(n-1)//2])


### FIXED CODE ###

n = int(input())
*l, = map(int, input().split())

p, q = sorted(l)[n//2-1 : n//2+1]
for _l in l:
    print(p if _l >= q else q)
### BUGGY CODE ###

N = int(input())
S = N*(N+1)//2
for n in range(N,0,-1):
    if S-n<N:
        print(n)
    else:
        S-=n

### FIXED CODE ###

N = int(input())
X = 1
while X*(X+1)<N*2:
    X+=1
flg = X*(X+1)//2-N
for n in range(X):
    if n+1==flg:
        continue
    else:
        print(n+1)
### BUGGY CODE ###

x = input()
y = x.split(" ")
parameters = [int(i) for i in y]
N = parameters[0]
M = parameters[1]
i = N
count = 0
A = [[0] * M for i in range(N)]
while(i > 0):
    x = input()
    y = x.split(" ")
    A[count] = [int(i) for i in y]
    count += 1
    i -= 1

cash = 0
while(M > 0):
    i = 0
    min = A[i][0]
    index = 0
    while(i < N):
        if(min > A[i][0]):
            min = A[i][0]
            index = i
        i += 1
    if(M - A[index][1] >= 0):
        M -= A[index][1]
        cash += A[index][1] * A[index][0]
    else:
        cash += A[index][0] * M
        M -= A[index][1]
    del A[index]
    N -= 1

print(cash)


### FIXED CODE ###

NM = [int(i) for i in input().split()]
N = NM[0]
M = NM[1]
datalist = []
index = 0
cost = 0
num = 1
total_cost = 0
while(N > 0):
    data = [int(i) for i in input().split()]
    datalist.append(data)
    N -= 1
datalist.sort(key=lambda x:x[0])
while(M > 0):
    M -= datalist[index][num]
    total_cost += datalist[index][cost] * datalist[index][num]
    if(M < 0):
        n = abs(M)
        total_cost -= n * datalist[index][cost]
    index += 1
print(total_cost)