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

import itertools
from functools import lru_cache

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

XY = [[int(x) for x in input().split()] for _ in range(N)]
XY.sort()
X,Y = zip(*XY)

@lru_cache(None)
def cnt(x,y):
  c = 0
  for x1,y1 in XY:
    if x1 > x:
      break
    if y1 <= y:
      c += 1
  return c

min_area = 5*10**18

for x1,x2 in itertools.combinations(X,2):
  for y1,y2 in itertools.combinations(Y,2):
    if y1 > y2:
      y1,y2 = y2,y1
    area = (x2-x1) * (y2-y1)
    if area > min_area:
      continue
    
    c = cnt(x2,y2) - cnt(x2,y1-1) - cnt(x1-1,y2) + cnt(x1-1,y1-1)
    if c < K:
      continue
      
    min_area = area
    
print(min_area)


### FIXED CODE ###

import itertools

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

X = []
Y = []

for _ in range(N):
  x,y = map(int, input().split())
  X.append(x)
  Y.append(y)

# 全部数えても間に合う

min_area = 5*10**18

for x1,x2 in itertools.combinations(X,2):
  for y1,y2 in itertools.combinations(Y,2):
    if x1 > x2:
      x1,x2 = x2,x1
    if y1 > y2:
      y1,y2 = y2,y1

    area = (x2-x1) * (y2-y1)
    if area > min_area:
      continue
      
    cnt = 0
    for x,y in zip(X,Y):
      if x1 <= x <= x2 and y1 <= y <= y2:
        cnt += 1
    if cnt < K:
      continue
      
    min_area = area
    
print(min_area)
### BUGGY CODE ###

Q = int(input())
a = []
for i in range(Q):
    a.append(list(map(int, input().split())))
number_list = []
for i in range(1,100000):
    number_list.append(i+1)
number_list_set = set(number_list)
prime_number_list = []
while True:
    try:
        prime_number_list.append(min(number_list_set))
        synthesis_number = {x for x in number_list if x % min(number_list_set) == 0}
        number_list_set = number_list_set - synthesis_number
    except:
        break
for i in range(Q):
    like_2017 = []
    for j in range(a[i][0], a[i][1] + 1, 2):        
        if (j in prime_number_list) and (int((j + 1) / 2) in prime_number_list):
            like_2017.append(j)
    print(len(like_2017))

### FIXED CODE ###

def prime(n):
    p = []
    flag = [True] * (n - 1)
    for i in range(n - 1):
        if flag[i] == True:
            p.append(i + 2)
            num = i
            while num <= n - 2:
                flag[num] = False
                num += i + 2
    return set(p)

p1 = prime(10 ** 5)
p2 = [0]
for i in range(10 ** 5):
    if i % 2 == 1:
        p2.append(p2[-1])
        continue
    else:
        if i + 1 in p1 and (i + 2) // 2 in p1:
            p2.append(p2[-1] + 1)
        else:
            p2.append(p2[-1])
q = int(input())
for i in range(q):
    l, r = map(int, input().split())
    print(p2[r] - p2[l -1])
### BUGGY CODE ###

n=int(input())
x=1
for s in range(2,n+1):
  x*=s
print(x%(10**9+7))

### FIXED CODE ###

from math import factorial;print(factorial(int(input()))%(10**9+7))
### BUGGY CODE ###

from itertools import permutations
n,m,r=map(int,input().split());R=min(r,8)
d = [[10**12for i in range(n)]for j in range(n)]
l=[int(i)-1 for i in input().split()]
for i in range(m):
  a,b,c=map(int,input().split())
  d[a-1][b-1]=d[b-1][a-1] = c
for k in range(n):
  for i in range(n):
    for j in range(n):
      if d[i][j]>d[i][k]+d[k][j]:
        d[i][j]=d[i][k]+d[k][j]
#print(d)
ans=10**12
for v in permutations(l, R):
  cnt=0
  for i in range(1,R):
    cnt+=d[v[i-1]][v[i]]
  ans=min(ans,cnt)
print(ans)

### FIXED CODE ###

import itertools
n,m,r=map(int,input().split());R=min(r,8)
d = [[10**12for i in range(n)]for j in range(n)]
l=list(map(int,input().split()))
for i in range(r):
  l[i]-=1
for i in range(m):
  a,b,c=map(int,input().split())
  d[a-1][b-1]=d[b-1][a-1] = c
for k in range(n):
  for i in range(n):
    for j in range(n):
      d[i][j]=min(d[i][j], d[i][k]+d[k][j])
#print(d)
ans=10**12
for v in itertools.permutations(l, R):
  cnt=0
  for i in range(1,R):
    cnt+=d[v[i-1]][v[i]]
  ans=min(ans,cnt)
print(ans)
### BUGGY CODE ###

import heapq
n,a,b = map(int,input().split())
H = []
for _ in range(n):
    h = int(input())
    H.append(-h)
heapq.heapify(H)
ans = 0
dm = 0
d = a-b
while True:
    mx = heapq.heappop(H)
    if mx+dm <0:
        mx += d
        dm += b
        ans += 1
        heapq.heappush(H, mx)
    else:
        break
print(ans)


### FIXED CODE ###

import math
n,a,b = map(int,input().split())
H = list(int(input()) for _ in range(n))
l,r = 0, 10**9
d = a-b
while r-l>1:
    mid = (r+l)//2
    tmp = 0
    for h in H:
        if h <= mid*b:
            continue
        tmp += math.ceil((h-mid*b)/d)
    if tmp <= mid:
        r = mid
    else:
        l = mid
print(r)
### BUGGY CODE ###

n, m, k = map(int, input().split())

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

A = [0]
B = [0]

for i in range(0, n):
    A.append(A[i]+a[i])
for i in range(0, m):
    B.append(B[i]+b[i])


ans= 0
for i in range(n + 1):
    j = m
    if A[i] > k:
        break
    while A[i] + B[j] > k:
        j -= 1
    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_pre,b_pre=[0],[0]

for i in range(n):
	a_pre.append(a_pre[i]+a[i])

for i in range(m):
	b_pre.append(b_pre[i]+b[i])

ans,j=0,m
for i in range(n+1):
	if a_pre[i]>k:
		break
	while b_pre[j]>k-a_pre[i]:
		j-=1

	ans=max(ans,i+j)

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

N, M = map(int, input().split())
B = [list(map(int, input().split())) for _ in range(M)]

pt = []
G = [0 for x in range(N+1)]
C = [1 for x in range(N+1)]

def find(x):
    while G[x] != 0:
        x = G[x]
    return x

cnt = 0
while len(B):
    x, y = B.pop()
    wx = find(x)
    wy = find(y)
    if wx is wy:
        pt.append(0)
    else:
        pt.append(C[wx] * C[wy])
        C[wx] += C[wy]
        G[wy] = wx

    #print(G)

cnt = 0
for _ in range(M):
    cnt += pt.pop()
    print(cnt)


### FIXED CODE ###

N, M = map(int, input().split())
B = [list(map(int, input().split())) for _ in range(M)]

pt = []
G = [[None, 1] for x in range(N+1)]

def find(x):
    n = G[x]
    c = []
    while not n[0] is None:
        c.append(n)
        n = n[0]
    for ci in c:
        ci[0] = n
    return n

cnt = 0
while len(B):
    x, y = B.pop()
    wx = find(x)
    wy = find(y)
    if wx is wy:
        pt.append(0)
    else:
        pt.append(wx[1] * wy[1])
        wx[1] += wy[1]
        wy[0] = wx

    #print(G)

cnt = 0
for _ in range(M):
    cnt += pt.pop()
    print(cnt)
### BUGGY CODE ###

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

### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
c = [0] * n
for i in a:
    c[i - 1] += 1
[print(i) for i in c]
### BUGGY CODE ###

from scipy.sparse.csgraph import dijkstra
from scipy.sparse import csr_matrix
import numpy as np

H, W, ch, cw, gh, gw, *S = open(0).read().split()
H, W, ch, cw, gh, gw = [int(_) - 1 for _ in [H, W, ch, cw, gh, gw]]
H += 1
W += 1

X = []
Y = []
D = []
for i in range(H * W):
    h, w = divmod(i, W)
    if S[h][w] == '#':
        continue
    for dh in range(-2, 3):
        for dw in range(-2, 3):
            if 0 <= h + dh < H and 0 <= w + dw < W and (
                    dh > 0 or dh == 0 and dw > 0) and S[h + dh][w + dw] == '.':
                X += [i]
                Y += [i + dw + W * dh]
                D += [0 if (dh, dw) in ((1, 0), (0, 1)) else 1]
dist = dijkstra(
    csr_matrix((D, (X, Y)), (H * W, H * W)), indices=ch * W + cw, directed=0)
ans = dist[gh * W + gw]
if ans == np.inf:
    ans = -1
else:
    ans = int(ans)
print(ans)


### FIXED CODE ###

import collections, itertools
H, W, ch, cw, dh, dw, *S = open(0).read().split()
H, W, ch, cw, dh, dw = [int(_) + 1 for _ in [H, W, ch, cw, dh, dw]]
H += 3
W += 3
S = ['#' * W] + ['#' * W] + ['##' + s + '##'
                             for s in S] + ['#' * W] + ['#' * W]
Dist = [[None] * W for _ in range(H)]
Q = collections.deque([(0, ch, cw)])
while Q:
    d, ox, oy = Q.popleft()
    if Dist[ox][oy] is not None:
        continue
    stack = [[ox, oy]]
    warp = set()
    while stack:
        x, y = stack.pop()
        if (x, y) == (dh, dw):
            print(d)
            exit()
        Dist[x][y] = d
        for dx, dy in [[-1, 0], [1, 0], [0, -1], [0, 1]]:
            nx, ny = x + dx, y + dy
            if Dist[nx][ny] is None:
                if S[nx][ny] == '.':
                    stack += [[nx, ny]]
                else:
                    warp.add((x, y))
    for x, y in warp:
        for dx, dy in itertools.product(range(-2, 3), repeat=2):
            nx, ny = x + dx, y + dy
            if Dist[nx][ny] is None and S[nx][ny] == '.':
                Q += [(d + 1, nx, ny)]
print(-1)
### BUGGY CODE ###

n,k=map(int,input().split())
a=[int(i) for i in input().split()]
f=[int(i) for i in input().split()]

# aとfの組み合わせはソートして逆向きが最適
# 帰納法で示す

# チームの成績x→単に成績x,メンバーiの成績→xi

# 0<=x<=a[-1]*f[0]な整数xがあったら
# 成績x以下にすることはできるか？という命題を考える

# gi=int(x/fi)は食べ物iで成績xiを出せる最大値
# 　aiがgiを超えてしまうと成績xi以下は修行しないと出せない
# 　ai<=giならその人の成績はxi以下になる
# なのでmax(ai-gi,0)は成績xi以下であるために必要な修行の回数

# よってsum=Σmax(ai-gi,0)は成績x以下を達成するのに、必要なチーム全体の総修行回数
# したってsum<=Kなら成績x以下にすることができる

# 各整数について命題はFalseかTrueを返す
# その順番は1から順にF...FT...Tとなる
# この一番左のTの整数xが求めたい最小値：チームの成績xの最小値

a.sort()
f.sort(reverse=True)

def score(x):
    syugyo = 0
    for A,F in zip(a,f):
        syugyo += max(A-int(x/F),0)
    if syugyo <= k:
        return True
    else:
        return False


left = 0
right = a[-1]*f[0]+1
while left < right-1:
    mid = (left+right)//2
    if score(mid):
        right = mid
    else:
        left = mid
print(left+1 if left != 0 else 0)
    
# 計算量は 1+2logN + N*log(2)N <= N*logN < 3.6 * 10^6 
# ぎりぎりセーフ？

### FIXED CODE ###

n,k=map(int,input().split())
a=[int(i) for i in input().split()]
f=[int(i) for i in input().split()]

# aとfの組み合わせはソートして逆向きが最適
# 帰納法で示す

# チームの成績x→単に成績x,メンバーiの成績→xi

# 0<=x<=a[-1]*f[0]な整数xがあったら
# 成績x以下にすることはできるか？という命題を考える

# gi=int(x/fi)は食べ物iで成績xiを出せる最大値
# 　aiがgiを超えてしまうと成績xi以下は修行しないと出せない
# 　ai<=giならその人の成績はxi以下になる
# なのでmax(ai-gi,0)は成績xi以下であるために必要な修行の回数

# よってsum=Σmax(ai-gi,0)は成績x以下を達成するのに、必要なチーム全体の総修行回数
# したってsum<=Kなら成績x以下にすることができる

# 各整数について命題はFalseかTrueを返す
# その順番は1から順にF...FT...Tとなる
# この一番左のTの整数xが求めたい最小値：チームの成績xの最小値

a.sort()
f.sort(reverse=True)

def score(x):
    syugyo = 0
    for A,F in zip(a,f):
        syugyo += max(A-int(x/F),0)
    if syugyo <= k:
        return True
    else:
        return False


left = 0
right = a[-1]*f[0]+1
while left < right-1:
    mid = (left+right)//2
    if score(mid):
        right = mid
    else:
        left = mid
print(left+1 if left != 0 else 0)
    
# 計算量は 1+2logN + N*log(2)N <= N*logN < 3.6 * 10^6 
# ぎりぎりセーフ？
### BUGGY CODE ###

import fractions
import numpy as np


mod = 10 ** 9 + 7

def lcm(a, b):
    return a * b / fractions.gcd(a, b)


n = int(input())
A = np.array(list(map(int, input().split())), dtype=np.uint64)

num = 1
for a in A:
    num = lcm(num, a)

B = np.array(num // A).astype('int64')
print(sum(B)%mod)

### FIXED CODE ###

import fractions


mod = 10 ** 9 + 7

def lcm(a, b):
    return a * b // fractions.gcd(a, b)


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

num = 1
for a in A:
    num = lcm(num, a)

ans = 0
for a in A:
    ans += num // a
print(ans%mod)
### BUGGY CODE ###

import numpy as np
n, k = map(int, input().split())
h = np.array(sorted([int(input()) for _ in range(n)]))
print(min([max(h[x:x+k]) - min(h[x:x+k]) for x in range(n-k+1)]))


### FIXED CODE ###

import numpy as np
n, k = map(int, input().split())
h = np.array([int(input()) for _ in range(n)],dtype=int)
h.sort()
print(min([h[x+k-1] - h[x] for x in range(n-k+1)]))
### BUGGY CODE ###

import sys
MOD = 10**9 + 7
n, m = map(int, input().split())
a = [int(x) for x in sys.stdin.readlines()]
ans = [0 for i in range(n)]
if 1 not in a:
    ans[0] = 1
if 2 not in a and n >=2:
    ans[1] = ans[0] + 1

for i in range(2, n):
    if i+1 not in a:
        ans[i] = (ans[i-1] + ans[i-2])%MOD

print(ans[-1])

### FIXED CODE ###

import sys
MOD = 10**9 + 7
n, m = map(int, input().split())
a = [int(x) for x in sys.stdin.readlines()]
ans = [1 for i in range(n)]
for x in a:
    ans[x-1] = 0
for i in range(n):
    if i == 0 and ans[i] == 0:
        ans[0] = 0
    elif i == 1:
        if ans[i] == 1:
            ans[1] += ans[0]
        elif ans[i] == 0:
            ans[1] = 0
    elif i >= 2 and ans[i] == 1:
        ans[i] = (ans[i-1] + ans[i-2])%MOD

print(ans[-1])
### BUGGY CODE ###

import sys
from fractions import gcd
input = sys.stdin.readline

n = input()
arr = list(map(int, input().split()))
tmp = arr[0]
for i in arr:
    tmp = tmp*i//gcd(tmp,i)
ans = sum(tmp//a for a in arr)
ans = ans % (10**9+7)
print(ans)

### FIXED CODE ###

import sys
from fractions import gcd
input = sys.stdin.readline

n = input()
arr = list(map(int, input().split()))
tmp = arr[0]
for i in arr:
    tmp = tmp*i//gcd(tmp,i)
print(sum(tmp//a for a in arr) % (10**9+7))
### BUGGY CODE ###

# LongestCommonSubsequences
S = input()
T = input()
Ns = len(S)
Nt = len(T)

dp = [[0] * (Nt + 1) for _ in range(Ns + 1)]

for i in range(1, Ns + 1):
    s = S[i-1]
    for j in range(1, Nt + 1):
        t = T[j-1]
        if s == t:
            dp[i][j] = dp[i-1][j-1]+1
        else:
            dp[i][j] = max(dp[i][j-1], dp[i-1][j])

ans = ""
i = Ns
j = Nt
while i > 0 and j > 0:
    if dp[i][j] == dp[i - 1][j]:
        i -= 1
    elif dp[i][j] == dp[i][j - 1]:
        j -= 1
    else:
        ans += S[i-1]
        i -= 1
        j -= 1

ans = ans[::-1]
print(ans)

### FIXED CODE ###

# LongestCommonSubsequences
import numpy as np
S = np.array([ord(i)-97 for i in input()], dtype=int)
T = np.array([ord(i)-97 for i in input()], dtype=int)
Ns = len(S)
Nt = len(T)
equal = np.equal.outer(S, T).astype(int)

dp = [np.zeros(Nt + 1, dtype=int)]
for i in range(Ns):
    x = dp[-1].copy()
    newDP = x.copy()
    newDP[1:] = np.maximum(x[:-1] + equal[i], newDP[1:])
    np.maximum.accumulate(newDP, out=newDP)
    dp.append(newDP)


ans = ""
i, j = Ns, Nt
while i > 0 and j > 0:
    if S[i-1] == T[j-1]:
        ans += chr(S[i-1]+97)
        i -= 1
        j -= 1
        continue
    if dp[i][j] == dp[i - 1][j]:
        i -= 1
    else:
        j -= 1

print(ans[::-1])
### BUGGY CODE ###

N = int(input())

for i in range(1, N+1):
    num = 0
    sqi = int(float(i)**0.5)
    for j in range(1,sqi+1):
        sqj = int(float(i-j**2)**0.5)
        for k in range(1, sqj+1):
            c = float(i-j**2-k**2-j*k)
            if c > 0:
                c *= -1.0
                b = float(j) + float(k)
                d = b**2-4*c
                if d >=0.0:
                    z = (-b + d**0.5)/2.0
                    if z.is_integer():
                        #print(j,k,z)
                        num +=1
    print(num)

### FIXED CODE ###

N = int(input())
ans = [0]*(10**4+10)

for i in range(1,10**2+10):
    for j in range(1, 10**2+10):
        for k in range(1, 10**2+10):
            v = i**2 + j**2 + k**2 + i*j + j*k + k*i
            if v < 10**4+10:
                ans[v]+=1

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

from collections import deque
import sys
input = sys.stdin.readline

def bfs():
    H, W = map(int, input().split())
    ls = deque([])
    D = [[0] * (W+2)]
    D += ([[0] + [float("inf")]*W + [0] for i in range(H)])
    D.append([0]*(W+2))
    G = [["#"]*(W+2)]
    for i in range(H):
        line = [i for i in input().strip()]
        for j in range(W):
            if line[j] == "#":
                ls.append([i+1, j+1, 0])
                D[i+1][j+1] = 0
        G.append(["#"]+line+["#"])
    G.append([["#"]*(W+2)])

    while len(ls) > 0:
        h, w, depth = ls.popleft()
        if depth + 1 < D[h+1][w] and G[h+1][w] != "#":
            ls.append([h+1, w, depth+1])
            D[h+1][w] = depth + 1
        if depth + 1 < D[h-1][w] and G[h-1][w] != "#":
            ls.append([h-1, w, depth+1])
            D[h-1][w] = depth + 1
        if depth + 1 < D[h][w+1] and G[h][w+1] != "#":
            ls.append([h, w+1, depth+1])
            D[h][w+1] = depth + 1
        if depth + 1 < D[h][w-1] and G[h][w-1] != "#":
            ls.append([h, w-1, depth+1])
            D[h][w-1] = depth + 1

    ans = 0
    for h in range(H+2):
        ans = max(ans, max(D[h]))
        
    return ans
    
print(bfs())

### FIXED CODE ###

import sys
input = sys.stdin.readline

H, W = map(int, input().split())
G = [[i for i in input()] for j in range(H)]

ls = []
dp = [[-1 for i in range(W)] for j in range(H)]
for h in range(H):
    for w in range(W):
        if G[h][w] == "#":
            ls.append([h,w])
            dp[h][w] = 1

ans = -1
while len(ls) > 0:
    ans += 1
    temp = []
    for h, w in ls:
        if 0 <= h+1 <= H-1 and dp[h+1][w] == -1:
            dp[h+1][w] = 1
            temp.append([h+1,w])
        if 0 <= h-1 <= H-1 and dp[h-1][w] == -1:
            dp[h-1][w] = 1
            temp.append([h-1,w])
        if 0 <= w+1 <= W-1 and dp[h][w+1] == -1:
            dp[h][w+1] = 1
            temp.append([h,w+1])
        if 0 <= w-1 <= W-1 and dp[h][w-1] == -1:
            dp[h][w-1] = 1
            temp.append([h,w-1])
    ls = temp

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

def main():
    n, k = map(int, input().split())
    h = list(map(int, input().split()))
    dp = [float("inf")] * n
    dp[0] = 0
    for i in range(n):
        for j in range(1,k+1):
            if i+j >= n:
                break
            dp[i+j] = min([dp[i+j], dp[i]+abs(h[i]-h[i+j])])
    print(dp[n-1])

if __name__ == "__main__":
    main()

### FIXED CODE ###

def main():
    n, k = map(int, input().split())
    h = list(map(int, input().split()))
    dp = [float("inf")] * n
    dp[0] = 0
    for i in range(n):
        for j in range(1,k+1):
            if i+j >= n:
                break
            dp[i+j] = min([dp[i+j], dp[i]+abs(h[i]-h[i+j])])
    print(dp[n-1])

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

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

def calc(a, k):
    s = 0
    x = 0
    for i in range(len(a)):
        if i == k:
            continue
        s += abs(a[i] - x)
        x = a[i]
    s += abs(0 - x)
    print(s)

for i in range(n):
    calc(a, i)


### FIXED CODE ###

n = int(input())
a = list(map(int, input().split(" ")))
s = 0
a.insert(0, 0)
a.insert(n+1, 0)
for j in range(n+1):
    s += abs(a[j] - a[j+1])
for i in range(1, n+1):
    s_i = s + abs(a[i-1]-a[i+1]) - ((abs(a[i-1] - a[i]) + abs(a[i]-a[i+1])))
    print(s_i)
### BUGGY CODE ###

import math
from bisect import bisect_left

def C(a,b):
    if a - b < 0:
        return 0
    else:
        return math.factorial(a) // (math.factorial(b)*math.factorial(a-b))

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

Cn, ans = N * (N-1) // 2, 0

for i in range(60):
    count = 0
    for j in range(N):
        count += A[j] % 2
        A[j] //= 2
    if count == 0:
        continue
    ans += (Cn - (C(count, 2) + C(N-count, 2))) * (2**i)
print(ans % (10**9 + 7)) 

### FIXED CODE ###

import numpy as np

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

Cn, ans = N * (N-1) // 2, 0

for i in range(60):
    count = int(np.sum(A % 2))
    A //= 2
    if count == 0:
        continue
    ans += (Cn - (count*(count-1)//2 + (N-count)*(N-count-1)//2)) * (2**i)
print(ans % (10**9 + 7))
### BUGGY CODE ###

n = int(input())
ls = list(map(int,input().split()))
ls.sort()
p = 0
for i in range(n-2):
    for j in range(i+1,n-1):
        di = [e for e in ls[j+1:] if ls[i]+ls[j] > e]
        p += len(di)
print(p)


### FIXED CODE ###

n = int(input())
ls = list(map(int,input().split()))
ls.sort()
p = 0
def is_ok(arg,l):
    return ls[arg] < l
def meguru_bisect(ng, ok):
    while (abs(ok - ng) > 1):
        mid = (ok + ng) // 2
        l = ls[i] + ls[j]
        if is_ok(mid,l):
            ok = mid
        else:
            ng = mid
    return ok
for i in range(n-2):
    for j in range(i+1,n-1):
        ng = n
        ok = j
        m = meguru_bisect(ng, ok)
        p += m-j 
print(p)
### BUGGY CODE ###

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

def gcd(num):
    k = []
    for i in range(1, num+1):
        if num%i == 0:
            k.append(i) 
    return k

def is_prime(num):
    for i in range(2, num):
        if num % i == 0:
            return False
    return True

ka = gcd(a)
kb = []
for i in ka:
  if is_prime(i) and b%i == 0:
    kb.append(i)

print(len(kb))

### FIXED CODE ###

def f(n):
    res = set()
    for i in range(2, int(n ** 0.5)):
        if n % i: continue
        while not n % i: n //= i
        res.add(i)
    return res | {n}
 
a, b = map(int,input().split())
print(len(f(a) & f(b) | {1}))
### BUGGY CODE ###

from heapq import heapify, heappop, heappush, heappushpop
inputs = open(0).readlines()

n, m = map(int, inputs[0].split())
*A, = map(int, inputs[1].split())
heapify(A)
BC = [tuple(map(int, bc.split())) for bc in inputs[2:]]

for b, c in BC:
    for _ in range(b):
        if c > A[0]:
            _ = heappushpop(A, c)
        else:
            break
print(sum(A))

### FIXED CODE ###

from heapq import heapify, heappushpop
from operator import itemgetter
inputs = open(0).readlines()

n, m = map(int, inputs[0].split())
*A, = map(int, inputs[1].split())
heapify(A)
BC = [tuple(map(int, bc.split())) for bc in inputs[2:]]
BC.sort(key=itemgetter(1), reverse=True)

for b, c in BC:
    for _ in range(b):
        if c > A[0]:
            _ = heappushpop(A, c)
        else:
            break
print(sum(A))
### BUGGY CODE ###


def main():
    M = 2019
    dp = [0] * M
    s = input()
    x = 0
    for c in s:
        c = int(c)
        dp2 = [0] * M
        for j in range(M):
            index = (j*10 + c) % M
            dp2[index] += dp[j]
        dp = dp2
        dp[c] += 1
        x += dp[0]
    print(x)

main()


### FIXED CODE ###

M = 2019
dp = [0] * M
s = input()
x = 0
for c in s:
    c = int(c)
    dp2 = [0] * M
    for j in range(M):
        index = (j*10 + c) % M
        dp2[index] += dp[j]
    dp = dp2
    dp[c] += 1
    x += dp[0]
print(x)
### BUGGY CODE ###

import numpy as np
from numba import njit

N = int(input())
scores = np.array(list(map(int, input().split())), dtype='int32')

@njit('i8(i4[:],i4,i4)', cache=True)
def get_max_score(scores, i, j):
    if i == j:
        return scores[i]
    return max(scores[i] - get_max_score(scores, i+1, j), scores[j] - get_max_score(scores, i, j-1))

print(get_max_score(scores, 0, len(scores)-1))


### FIXED CODE ###

import numpy as np
from numba import njit

N = int(input())
scores = np.array(list(map(int, input().split())), dtype='int64')
dpt = np.full((N, N), -10**18, dtype='int64')

@njit('i8(i8[:],i8[:,:],i8,i8)', cache=True)
def get_max_score(scores, dpt, i, j):
    if i == j:
        dpt[i][j] = scores[i]
        return scores[i]
    else:
        if dpt[i][j] != -10**18:
            return dpt[i][j]
        result = max(scores[i] - get_max_score(scores, dpt, i+1, j), scores[j] - get_max_score(scores, dpt, i, j-1))
        dpt[i][j] = result
        return result

print(get_max_score(scores, dpt, 0, len(scores)-1))