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


def dp_table(*counts):  # dp[x][y]を作りたかったら dp_table(xのサイズ,yのサイズ)
    if counts:
        return [dp_table(*counts[1:]) for _ in range(counts[0])]
    else:
        return 0


def main():

    N = int(input())
    A = [int(input()) for i in range(N)]
    mod = 998244353
    ans = pow(3, N, mod)
    sum_A = sum(A)
    dp = dp_table(N, sum_A + 1)
    # dp[i][j]: i番目までの中から辺をいくつか選んで、長さがjになるパターン数

    # init
    dp[0][A[0]] = 1
    dp[0][0] = 2  # 他の色のうちどちらに入れるかで2通り

    # init2
    dp2 = dp_table(N, sum_A+1)  # ある二色でsum_Aを等分するパターンを数える
    dp2[0][A[0]] = 1
    dp2[0][0] = 1  # 今度は片方に集中したパターン

    # dp
    sum_now = A[0]
    for i in range(1, N):
        a = A[i]
        sum_now += a
        for length in range(0, sum_now+1):
            # A[i]を追加しないのなら他の２食のうちどちらに入れるかで2倍選択肢がある
            if length >= a:
                dp[i][length] = dp[i - 1][length - a] + \
                    (dp[i - 1][length] << 1)
            else:
                dp[i][length] = dp[i-1][length] << 1
            dp[i][length] %= mod

        for length in range(min(sum_now + 1, sum_A // 2 + 1)):
            if length >= a:
                dp2[i][length] = dp2[i - 1][length - a] + dp2[i - 1][length]
            else:
                dp2[i][length] = dp2[i-1][length]
            dp2[i][length] %= mod
    # print(sum(dp[N-1][sum_A//2]))
    # print(dp)
    ans -= 3*sum(dp[N-1][(sum_A+1)//2:])
    if sum_A % 2 == 0:
        ans += 3*dp2[N-1][sum_A//2]
    print(ans % mod)


if __name__ == '__main__':
    main()


### FIXED CODE ###


def dp_table(*counts):  # dp[x][y]を作りたかったら dp_table(xのサイズ,yのサイズ)
    if counts:
        return [dp_table(*counts[1:]) for _ in range(counts[0])]
    else:
        return 0


def main():

    N = int(input())
    A = [int(input()) for _ in range(N)]
    mod = 998244353
    ans = pow(3, N, mod)
    sum_A = sum(A)
    dp = [[0] * (sum_A+1) for i in range(N)]
    # dp[i][j]: i番目までの中から辺をいくつか選んで、長さがjになるパターン数

    # init
    dp[0][A[0]] = 1
    dp[0][0] = 2  # 他の色のうちどちらに入れるかで2通り

    # init2
    dp2 = [[0] * (sum_A+1) for i in range(N)]  # ある二色でsum_Aを等分するパターンを数える
    dp2[0][A[0]] = 1
    dp2[0][0] = 1  # 今度は片方に集中したパターン

    # dp
    sum_now = A[0]
    for i in range(1, N):
        a = A[i]
        sum_now += a
        for length in range(sum_now+1):
            # A[i]を追加しないのなら他の２食のうちどちらに入れるかで2倍選択肢がある
            if length >= a:
                dp[i][length] = dp[i - 1][length - a] + \
                    (dp[i - 1][length] << 1)
            else:
                dp[i][length] = dp[i-1][length] << 1
            dp[i][length] %= mod

        for length in range(min(sum_now + 1, sum_A // 2 + 1)):
            if length >= a:
                dp2[i][length] = dp2[i - 1][length - a] + dp2[i - 1][length]
            else:
                dp2[i][length] = dp2[i-1][length]
            dp2[i][length] %= mod
    # print(sum(dp[N-1][sum_A//2]))
    # print(dp)
    ans -= 3*sum(dp[N-1][(sum_A+1)//2:])
    if sum_A % 2 == 0:
        ans += 3*dp2[N-1][sum_A//2]
    print(ans % mod)


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

N = int(input())
a = list(map(int, input().split()))
mindif = 1e15
minidx=0
for i in range(1,N):
    dif = abs(sum(a[:i])-sum(a[i:]))
    if dif<mindif:
        mindif = dif
        minidx = i
    else:
        break
print(mindif)

### FIXED CODE ###

N = int(input())
a = list(map(int, input().split()))
r = sum(a)
ra = 0
result = 1e30
for i in range(0,N):
    ra += a[i]
    r -= a[i]
    result = min(result, abs(ra-r))
print(int(result))
### BUGGY CODE ###

#[int(i) for i in input().split()]
t = input()
ans = ""
for i in range(len(t)):
    if t[i] == "?":
        ans += "D"
    else:
        ans += t[i]
print(ans)


### FIXED CODE ###

#[int(i) for i in input().split()]
t = input()
ans = ""
for i in range(len(t)):
    if t[i] == "?":
        ans += "D"
    else:
        ans += t[i]
print(ans)
### BUGGY CODE ###

S = input()
MOD = 10**9+7

S = S[::-1]
dp = [0]*13
for i,s in enumerate(S):
    new = [0]*13
    if i == 0:
        if s == "?":
            for j in range(10):
                dp[j] = 1
        else:
            s = int(s)
            dp[s%13] = 1
    else:
        if s == "?":
            for j in range(10):
                m = (j*(10**i))%13
                for k in range(13):
                    new[k] += dp[k-m]
            for l in range(13):
                dp[l] = new[l]%MOD
        else:
            s = int(s)
            m = (s*(10**i))%13
            for j in range(13):
                new[j] = dp[j-m]
            dp = new
print(dp[5])

### FIXED CODE ###

S = input()
MOD = 10**9+7

dp = [0]*13
dp[0] = 1

for s in S:
    prev = [x for x in dp]
    dp = [0]*13
    if s == "?":
        r = range(10)
    else:
        r = [int(s)]
    for i in range(13):
        for x in r:
            dp[(10*i+x)%13] += prev[i]
    dp = [x % MOD for x in dp]
print(dp[5])
### BUGGY CODE ###

import numpy as np


def read_input(trans=int):
    return list(map(trans, input().split()))


N, K = read_input()
A = np.array(read_input(), dtype="int")
coordinate = np.arange(1, N+1)

for _ in range(K):
    B = np.zeros(N, dtype="int")
    for i in range(N):
        end = np.minimum(coordinate[i]+A[i], N)
        start = np.maximum(coordinate[i]-A[i], 1)

        for j in range(start-1, end):
            B[j] += 1

    A = B

print(" ".join(map(str, A.tolist())))


### FIXED CODE ###

def read_input(trans=int):
    return list(map(trans, input().split()))


N, K = read_input()
A = read_input()
K = min(K, 41)

for _ in range(K):
    B = [0]*N
    for i in range(N):
        start = max(i-A[i], 0)
        end = min(i+A[i], N-1)

        B[start] += 1
        if end+1 < N:
            B[end+1] -= 1
    for i in range(1, N):
        B[i] += B[i-1]
    A = B.copy()


print(" ".join(map(str, A)))
### BUGGY CODE ###

S = input()
if len(S) < 4:
  print(0)
else:
  N = len(S)
  x = 0
  d = [0]*2019
  d[0] = 1
  for i, s in enumerate(reversed(S)):
    x += int(s)*(10**i)
    d[x%2019] += 1
  ans = 0
  for m in d:
    ans += m*(m-1)//2
  print(ans)



### FIXED CODE ###

S = input()
if len(S) < 4:
  print(0)
else:
  N = len(S)
  x = 0
  d = [0]*2019
  d[0] = 1
  for i, s in enumerate(reversed(S)):
    x = (x+int(s)*pow(10,i,2019))%2019
    d[x] += 1
  print(sum([m*(m-1)//2 for m in d]))
### BUGGY CODE ###

S=input()
keta=len(S)
import numpy as np
dp=np.zeros((keta,26),dtype=int)
DIV=10**9+7

if S[-1]=="?":
  for i in range(10):
    dp[0][i]=1
else:
  dp[0][int(S[-1])]=1
  
dig=1
for i in range(1,keta):
  dig*=10
  if S[keta-1-i]=="?":
    for k in range(10):
      d=k*dig%13
      dp[i][d:d+13]+=dp[i-1][:13]
      dp[i][:13]+=dp[i][13:]
      dp[i][13:]*=0
  else:
    ch=int(S[keta-1-i])
    d=ch*dig%13
    dp[i][d:d+13]+=dp[i-1][:13]
    dp[i][:13]+=dp[i][13:]
    dp[i][13:]*=0
  dp[i]=dp[i]%DIV

print(dp[len(dp)-1][5])

### FIXED CODE ###

# 各桁についての13で割ったあまりを足し合わせると5になる
# "??"の場合、
# 1桁目が"3"だと、13で割ったあまりは3
# 2桁目が"8"だと、13で割ったあまりは2
# 従い83を13で割ったあまりは5
# 下から数えてN桁目までに、あまりの合計がP(0〜12)になっている数がそれぞれいくつあるかをDPする
# dp[i桁目(下から数える)][あまりの合計]

S = input()
N = len(S)
S = S[::-1] # 逆順にしたほうがやりやすい
dp = [[0] * 13 for i in range(N)]
if S[0] != "?":
  dp[0][int(S[0])] = 1 # 指定の数をとりあえずカウント
else:
  for i in range(10):
    dp[0][i] = 1 # 1桁目は、あまり0〜9になる数が一つずつある
     
# あまりリストの管理 桁数が一つ増えるごとに、各数に対しての13で割ったあまりを計算する
amari = [i for i in range(10)]
amarimap = {1:10,10:9,9:12,12:3,3:4,4:1,2:7,7:5,5:11,11:6,6:8,8:2,0:0}

DIV = 10 ** 9 + 7

# 各桁のあまりの数を更新する
# これにより、桁が増えたときに更新すべきあまりの種類（あまり13種類に対して
# ひと桁は10種類しかない）を管理できる
def update_amari():
  for i in range(len(amari)):
    amari[i] = amarimap[amari[i]]

# 2桁目以降をDP
for i in range(1,N):
  update_amari() # 各桁のあまりをアップデート
  if S[i] == "?":
    # あらゆる数が入る
    # i-1桁目の各数のループと、i桁目のあまりの各数のループ
    for j in range(len(dp[i-1])):
      # 前の桁であまりがjだったとき
      for k in amari:
        dp[i][(j + k) % 13] += dp[i-1][j]
        dp[i][(j + k) % 13] %= DIV
  else:
    # 数が決まっている
    for j in range(len(dp[i-1])):
      # あまりが決まっている
      am = amari[int(S[i])]
      dp[i][(j + am) % 13] += dp[i-1][j]
      dp[i][(j + am) % 13] %= DIV
        
# 最終桁までいったときにあまりが5になる数が必要なので、dp[N-1][5]が答え
print(dp[N-1][5])
### BUGGY CODE ###

import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
from itertools import combinations_with_replacement 
def main():
    s = readline().rstrip().decode()
    K = int(readline())
    N = len(s)
    p = [int(i) for i in range(N)]
    S = set()

    #K番目のsubsitringは長さがK以下のsubstrigの集合に必ず含まれる
    #K<=5であるから列挙される要素数は最大でも26^5(およそ10,000,000)
    #したがって長さK以下のsubstringを列挙してからソートすればよい
    for l, r in combinations_with_replacement(p, 2):
        sub = s[l:r+1]
        ln = len(sub)
        if ln <= K:  
            S.add(sub)
    #最大でも26^5要素のソート
    lis = list(S)
    lis.sort()
    print(lis[K-1])
if __name__ == '__main__':
    main()

### FIXED CODE ###

import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(1000000)

def main():
    s = readline().rstrip().decode()
    K = int(readline())
    #sに含まれる文字を一文字ずつ抽出する.
    #ここで抽出した文字を組み合わせて辞書順に文字列を構成していく
    #K<=5だから高々26^5個の文字列を構成することになる
    l = sorted(list(set(s)))
    #cnd:=構成した文字列を辞書順に格納するリスト
    cnd = []
    #f(sub):=subから構成可能なK文字以下のSの部分文字列を構成する関数
    def f(sub):
        cnd.append(sub)
        if len(sub) < K: 
            #lから選んでsubに一文字追加する
            for i in l:
                nx = sub+i
                if nx in s:
                    f(nx)
    for i in l:
        f(i) 
    print(cnd[K-1])
if __name__ == '__main__':
    main()
### BUGGY CODE ###

import sys
import heapq
import bisect

mod = 10**9+7
dd = ((-1,0),(1,0),(0,-1),(0,1))

def I(): return(int(sys.stdin.readline()))
def LI(): return([int(x) for x in sys.stdin.readline().split()])
def S(): return(sys.stdin.readline()[:-1])
def IR(n): return([I() for _ in range(n)])

def GCD(a,b):
    while b!=0:
        a,b = b,a%b
    return a

def LCM(a,b):
    return a * b // GCD(a,b)

def Eratosthenes(N):
    r = [True]*(N+1)
    r[0] = False
    r[1] = False
    i = 2
    while i*i<=N:
        if r[i]: 
            j = i
            while i*j<=N:
                prime[i*j]=False
                j+=1
        i+=1
    return(r)

def main():
    N,M,R = LI()
    r = LI()
    node = [[] for _ in range(N)]
    for _ in range(M):
        a,b,c = LI()
        node[a-1].append([b-1,c])
        node[b-1].append([a-1,c])

    dic = {}
    for x in r:
        dic_part = {}
        for y in r:
            dic_part[y-1] = 0
        dic[x-1] = dic_part

    for x in r:
        ques = []
        flag = [True] * len(node)
        heapq.heappush(ques,[0,x-1])
        while ques:
            dist,crt = heapq.heappop(ques)
            if flag[crt]:
                flag[crt] = False
                if (crt+1) in r:
                    dic[x-1][crt] = dist
                    dic[crt][x-1] = dist
                for nxt,nxt_dist in node[crt]:
                    if flag[nxt]:
                        heapq.heappush(ques,[dist+nxt_dist,nxt])
    ans = 10**11
    for x in range(R**R):
        order = [0] * R
        i = 0
        while x>0:
            order[i] = x%R
            i += 1
            x //= R
        for j in range(1,R):
            for k in range(j):
                if order[j]==order[k]:
                    break
            else:
                continue
            break
        else:
            ans_tmp = 0
            for j in range(R-1):
                ans_tmp += dic[r[order[j]]-1][r[order[j+1]]-1]
            ans = min(ans,ans_tmp)
    return(ans)



    



if __name__ == "__main__":
    print(main())


### FIXED CODE ###

import sys
import itertools

def I(): return(int(sys.stdin.readline()))
def LI(): return([int(x) for x in sys.stdin.readline().split()])
def S(): return(sys.stdin.readline()[:-1])
def IR(n): return([I() for _ in range(n)])

def main():
    N,M,R = LI()
    rs = [int(x) -1 for x in sys.stdin.readline().split()]
    D = [[10**10]*N for _ in range(N)]
    for _ in range(M):
        A,B,C = LI()
        D[A-1][B-1] = C
        D[B-1][A-1] = C
    for i in range(N):
        D[i][i] = 0

    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])

    ans = 10**11
    for trs in itertools.permutations(rs):
        tans = 0
        for i in range(R-1):
            tans += D[trs[i]][trs[i+1]]
        ans = min(ans,tans)
    
    return(ans)

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

from collections import deque
import itertools
 
def dfs(visited, q, h, w):    
    while q:
        if not False in itertools.chain.from_iterable(visited):
            i, j, d = q.pop()
            return d
        i, j, d = q.popleft()
        if i > 0 and visited[i - 1][j] == False:
            q.append((i - 1, j, d + 1))
            visited[i - 1][j] = True
        if i < h - 1 and visited[i + 1][j] == False:
            q.append((i + 1, j, d + 1))
            visited[i + 1][j] = True
        if j > 0 and visited[i][j - 1] == False:
            q.append((i, j - 1, d + 1))
            visited[i][j - 1] = True
        if j < w - 1 and visited[i][j + 1] == False:
            q.append((i, j + 1, d + 1))
            visited[i][j + 1] = True
    else:
        return d


h , w = map(int, input().split())
visited = [[False] * w for _ in range(h)]
q = deque([])
for y in range(h):
    _in = input()
    for x, value in enumerate(_in):
        if value == '#':
            visited[y][x] = True
            q.append((y, x, 0))
d = dfs(visited, q, h, w)
print(d)

### FIXED CODE ###

import numpy as np

H,W = map(int,input().split())
use = np.zeros((H,W),dtype=int)
for i in range(H):
    s = input()
    for j,st in enumerate(s):
        if st == ".":
            use[i][j] = 10**10
        else:
            use[i][j] = 0

for i in range(1,H):
    use[i,:] = np.minimum(use[i,:],use[i-1,:]+1)
for i in reversed(range(H-1)):
    use[i,:] = np.minimum(use[i,:],use[i+1,:]+1)
for j in range(1,W):
    use[:,j] = np.minimum(use[:,j],use[:,j-1]+1)
for j in reversed(range(W-1)):
    use[:,j] = np.minimum(use[:,j],use[:,j+1]+1)

print(np.max(use))
### BUGGY CODE ###

n,k=map(int,input().split())
a=list(map(int,input().split()))
b=[0]*40
p=[1]*40
for i in range(39):
    p[i+1]=p[i]*2
for i in a:
    for j in range(40):
        if i&p[j]>0:
            b[j]+=1
ans=0
for i in range(k+1):
    kai=0
    for j in range(40):
        if i&p[j]==0:
            kai+=b[j]*p[j]
        else:
            kai+=(n-b[j])*p[j]
    ans=max(ans,kai)
print(ans)


### FIXED CODE ###

n,k=map(int,input().split())
l=list(map(int,input().split()))
a=[0]*42
for i in range(n):
    p=l[i]
    j=0
    while p>0:
        a[j]+=p%2
        p=p//2
        j+=1
ans=0
for i in range(41,-1,-1):
    if a[i]<n-a[i]:
        if k>=2**i:
            k-=2**i
            ans+=(2**i)*(n-a[i])
        else:
            ans+=(2**i)*a[i]
    else:
        ans+=(2**i)*a[i]
print(ans)
### BUGGY CODE ###

import sys
input = sys.stdin.readline

n = int(input())
a = list(map(int, input().split()))
q = int(input())
info = []
for i in range(q):
    info.append(list(map(int, input().split())))

a_dict = dict()
for num in a:
    if num in a_dict.keys():
        a_dict[num] += 1
    else:
        a_dict[num] = 1

for j in range(q):
    if info[j][0] in a_dict.keys():
        if info[j][1] in a_dict.keys():
            a_dict[info[j][1]] += a_dict[info[j][0]]
            del a_dict[info[j][0]]
        else:
            a_dict[info[j][1]] = a_dict[info[j][0]]
            del a_dict[info[j][0]]
    ans = 0
    a_key = list(a_dict.keys())
    a_value = list(a_dict.values())
    for k in range(len(a_dict)):
        ans += a_key[k] * a_value[k]

    print(ans)

### FIXED CODE ###

import sys
input = sys.stdin.readline

n = int(input())
a = list(map(int, input().split()))
q = int(input())
info = []
for i in range(q):
    info.append(list(map(int, input().split())))

a_dict = dict()
for num in a:
    if num in a_dict.keys():
        a_dict[num] += 1
    else:
        a_dict[num] = 1

a_key = list(a_dict.keys())
a_value = list(a_dict.values())
ans = 0
for k in range(len(a_dict)):
    ans += a_key[k] * a_value[k]

for j in range(q):
    if info[j][0] in a_dict.keys():
        if info[j][1] in a_dict.keys():
            ans -= info[j][0] * a_dict[info[j][0]]
            ans += info[j][1] * a_dict[info[j][0]]
            a_dict[info[j][1]] += a_dict[info[j][0]]
            del a_dict[info[j][0]]
        else:
            ans -= info[j][0] * a_dict[info[j][0]]
            a_dict[info[j][1]] = a_dict[info[j][0]]
            ans += info[j][1] * a_dict[info[j][1]]
            del a_dict[info[j][0]]


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

N = int(input())
A = list(map(int, input().split()))
for x in range(N):
    print(A.count(x+1))

### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
count_array = [0] * N
for x in range(N - 1):
    count_array[A[x] - 1] += 1
for y in count_array:
    print(y)
### BUGGY CODE ###


S=input()

tmp=S.split()

L=int(tmp[0])
R=int(tmp[1])

result=100000000000
flag=False
for i in range(L,R+1):
    for j in range(i+1,R+1):
        if i>=j:
            flag=True
            break
        n=(i*j)%2019
        if result>n:
            result=n
            
    if(flag):
        break

print(result)

### FIXED CODE ###


S=input()

tmp=S.split()

L=int(tmp[0])
R=int(tmp[1])

R=min(L+2019,R)

flag=False
result=1000000000000
for i in range(L,R+1):
    for j in range(i+1,R+1):
        if i>=j:
            flag=True
            break
        n=(i*j)%2019
        if result>n:
            result=n
    if(flag):
        break



print(result)
### BUGGY CODE ###

from collections import Counter
import sys

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

# 改行またはスペース区切りの入力をすべて読み込んでイテレータを返します。
def get_all_int():
    return map(int, open(0).read().split())

def log(*args):
    print("DEBUG:", *args, file=sys.stderr)

def make_divisors(n):
    lower_divisors , upper_divisors = [], []
    i = 1
    while i*i <= n:
        if n % i == 0:
            lower_divisors.append(i)
            if i != n // i:
                upper_divisors.append(n//i)
        i += 1
    
    return lower_divisors + upper_divisors[::-1]

n,*A = get_all_int()
A.sort()



C = dict(Counter(A))
keys = C.keys()
# log(C)

B = []
for i,a in enumerate(A):
    if C[a] == 1:
        B.append(a)

ans = 0

for i,a in enumerate(B):
    div = make_divisors(a)
    ok = True
    for d in div:
        if d == a:
            continue
        elif d in keys:
            ok = False
            break
    if ok:
        ans += 1

print(ans)


### FIXED CODE ###

from collections import Counter
import sys

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

# 改行またはスペース区切りの入力をすべて読み込んでイテレータを返します。
def get_all_int():
    return map(int, open(0).read().split())

def log(*args):
    print("DEBUG:", *args, file=sys.stderr)

def make_divisors(n):
    lower_divisors , upper_divisors = [], []
    i = 1
    while i*i <= n:
        if n % i == 0:
            yield i
            if i != n // i:
                yield n//i
        i += 1

n,*A = get_all_int()
A.sort()



C = dict(Counter(A))
keys = C.keys()
# log(C)

checks = [False] * (1000009)

B = []
for i,a in enumerate(A):
    if C[a] == 1:
        B.append(a)
    elif not checks[a]:
        for j in range(a, 1000009, a):
            checks[j] = True

# log(B)

ans = 0

for i,a in enumerate(B):
    if not checks[a]:
        ans += 1
        for j in range(a, 1000009, a):
            checks[j] = True

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

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


def main():
  S = input()[:-1]
  MOD = 2019

  dp = [0]*(len(S)+1)
  dp[0] = 0

  for i in range(1, len(S)+1):
    dp[i] = (dp[i-1] + (10**(i-1))*int(S[-i])) % MOD

  dic = defaultdict(int)
  sum_ = 0
  for sup in dp:
    if sup in dic:
      sum_ += dic[sup]
    dic[sup] += 1

  print(sum_)


if(__name__ == '__main__'):
  main()


### FIXED CODE ###

def main():
  # S = input()[-1:0:-1]
  S = input()[::-1]
  MOD = 2019

  # dp = [0]*(len(S)+1)
  # dp[0] = 0
  dic = [0]*2019
  dic[0] = 1

  ten = 1
  pre = 0
  for i, s in enumerate(S):
    # dp[i] = (dp[i-1] + ten*int(s)) % MOD
    pre = (pre + ten*int(s)) % MOD
    dic[pre] += 1
    ten *= 10
    ten %= MOD

  sum_ = 0
  # for sup in dp:
  #   dic[sup] += 1

  for v in dic:
    sum_ += v*(v-1)//2

  print(sum_)


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

s = input()
keta = len(s)
n = int(s)
infi = 10 ** 10
dp = [0] * (keta + 1)
dp[0] = 0
s = s[::-1] + "0"
kuri = 0
for i in range(keta):
    ni = i + 1
    num = int(s[i])
    if kuri:
        num += 1
        kuri = 0
    if num == 10:
        kuri = 1
        dp[ni] = dp[i]
    elif num < 5:
        dp[ni] = dp[i] + num
    elif num > 5:
        num %= 10
        kuri = 1
        dp[ni] = dp[i] + 10 - num
    else:
        nn = int(s[i + 1])
        if nn < 5:
            dp[ni] = dp[i] + num
        else:
            kuri = 1
            dp[ni] = dp[i] + 10 - num
print(dp[keta] + kuri)


### FIXED CODE ###

s = "0" + input()
keta = len(s)
dp = [0] * (keta + 1)
kuri = 0
for i in range(keta):
    ni = i + 1
    num = int(s[-i - 1])
    if kuri:
        num += 1
        kuri = 0
    if num == 10:
        kuri = 1
        dp[ni] = dp[i]
    elif num < 5:
        dp[ni] = dp[i] + num
    elif num > 5:
        num %= 10
        kuri = 1
        dp[ni] = dp[i] + 10 - num
    else:
        nn = int(s[-ni - 1])
        if nn < 5:
            dp[ni] = dp[i] + num
        else:
            kuri = 1
            dp[ni] = dp[i] + 10 - num
print(dp[keta] + kuri)
### BUGGY CODE ###

from sys import exit, stderr, stdin
input = stdin.readline
import heapq
from collections import defaultdict
# setrecursionlimit(10**7)

def debug(var, name="hoge"):
    print(name +":" + str(type(var)) + " = " + repr(var), file=stderr)
    return


def main():
    N,M = [int(n) for n in input().split()]
    # {期限:価値}
    jobs = defaultdict(list)
    v = 0
    for i in range(N):
        a,b = [int(n) for n in input().split()]
        if a <= M:
            jobs[a].append(-b)
    cand = []
    ans = 0
    for i in range(1,M+1):
        if i in jobs:
            cand += jobs[i]
            heapq.heapify(cand)
        if len(cand) != 0:
            ans -= cand[0]
            heapq.heappop(cand)
    print(ans)



if __name__ == "__main__":
    main()


### FIXED CODE ###

from sys import exit, stderr, stdin
input = stdin.readline
import heapq
# from collections import defaultdict
# setrecursionlimit(10**7)

def debug(var, name="hoge"):
    print(name +":" + str(type(var)) + " = " + repr(var), file=stderr)
    return


def main():
    N,M = [int(n) for n in input().split()]
    # {期限:価値}
    jobs = [[]]*N
    v = 0
    for i in range(N):
        jobs[i] = [int(n) for n in input().split()]
    # 価値降順→期間昇順
    jobs = sorted(jobs,key=lambda x:-x[1])
    jobs = sorted(jobs,key=lambda x:x[0])
    cur = 0
    ans = 0
    cand = []
    for i in range(1,M+1):
        while(cur < N and i >= jobs[cur][0]):
            heapq.heappush(cand,-jobs[cur][1])
            cur += 1
        if len(cand) != 0:
            ans -= cand[0]
            heapq.heappop(cand)
    print(ans)



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

# E
# This Message Will Self-Destruct in 5s
import numpy as np

N = int(input())
A_list = np.array([int(x) for x in input().split()])
Num_list = np.arange(1,N+1,1)

L_list = Num_list + A_list
R_list = Num_list - A_list
ans = 0
for i in range(N):
    ans += sum((R_list == L_list[i])[i+1:])

print(ans)

### FIXED CODE ###

from collections import Counter

n=int(input())
a=list(map(int,input().split()))
ans=0
l=[]
r=[]
for i,j in enumerate(a):
    l.append(i+j)
    r.append(i-j)

b=Counter(r)
for i in l:
    ans+=b.get(i,0)

print(ans)