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

S=input()

out=0
D=len(S)-4
for ii in range(D+1):
    for i in range(ii+3,len(S)):
        T=S[ii:i+1]
        if int(T)%2019==0:
            out+=1
print(out)

### FIXED CODE ###

S=input()

out=0
l=[0]*2019
x=0
now=1
for i in S[::-1]:
    x+=now*int(i)
    x%=2019
    l[x]+=1

    now*=10
    now%=2019

for i in l:
    out+=(i-1)*i//2
print(out+l[0])

# # 全探索は間に合わない
# D=len(S)-4
# for ii in range(D+1):
#     for i in range(ii+3,len(S)):
#         T=S[ii:i+1]
#         if int(T)%2019==0:
#             out+=1
# print(out)
### BUGGY CODE ###

import sys
input = sys.stdin.readline

N,T=map(int,input().split())
D=[tuple(map(int,input().split())) for i in range(N)]
D.sort()

DP=[0]*(T+1)
ANS=0

for i in range(N):
    a,b=D[i]

    for j in range(T,a-1,-1):
        DP[j]=max(DP[j-a]+b,DP[j])

    for j in range(i+1,N):
        ANS=max(ANS,DP[T-1]+D[j][1])

print(ANS)


### FIXED CODE ###

import sys
input = sys.stdin.readline

N,T=map(int,input().split())
D=[tuple(map(int,input().split())) for i in range(N)]

D.sort(key=lambda x:x[1],reverse=True)

DP=[[0,0] for i in range(T+1)]

for ind,(x,y) in enumerate(D):
    for time in range(T,x-1,-1):
        if DP[time][0]<DP[time-x][0]+y:

            if DP[time-x][1]==ind:
                DP[time]=[DP[time-x][0]+y,ind+1]
            else:
                DP[time]=[DP[time-x][0]+y,DP[time-x][1]]

        elif DP[time][0]==DP[time-x][0]+y:

            if DP[time-x][1]==ind:
                DP[time][1]=min(ind+1,DP[time][1])
            else:
                DP[time][1]=min(DP[time-x][1],DP[time][1])

    #print(DP)

D.append((0,0))
                
ANS=DP[-1][0]

for x,y in DP[:-1]:
    #if x==0:
    #    continue
    ANS=max(ANS,x+D[y][1])

print(ANS)
### BUGGY CODE ###

import heapq



def pay(N,A,B,C,D):
  q = []
  heapq.heapify(q)
  num = {}
  num[0] = 0
  num[-1] = -1
  heapq.heappush(q,( 0, 0 ))
  while q:
    c, n = heapq.heappop(q)
#    print(n,c)
    if n == N:
      break
    if num.setdefault(n*2,N*D+1) > c+A:
      heapq.heappush(q,( c+A, n*2 ))
      num[n*2] = c+A
    if num.setdefault(n*3,N*D+1) > c+B:
      heapq.heappush(q,( c+B, n*3 ))
      num[n*3] = c+B
    if num.setdefault(n*5,N*D+1) > c+C:
      heapq.heappush(q,( c+C, n*5 ))
      num[n*5] = c+C
    if num.setdefault(n+1,N*D+1) > c+D:
      heapq.heappush(q,( c+D, n+1 ))
      num[n+1] = c+D
    if num.setdefault(n-1,N*D+1) > c+D:
      heapq.heappush(q,( c+D, n-1 ))
      num[n-1] = c+D
  #
  print(num.setdefault(N,-1))
#

T = int(input())
for i in range(T):
  N,A,B,C,D = map(int, input().split())
  pay(N,A,B,C,D)


### FIXED CODE ###

import heapq

def pay2win():
  num = set()
  q = []
  heapq.heapify(q)
  heapq.heappush(q,( 0, N ))
  cost = N*D
  while q:
    c0, n0 = heapq.heappop(q)
    if n0 in num:
      continue
    num.add(n0)
    if n0 == 0:
      break
    if c0 >= cost:
      break
    cost = min(cost,c0+n0*D)
    #
    n2, m = divmod(n0, 2)
    if m == 0:
      heapq.heappush(q,( c0+A, n2 ))
    else:
      heapq.heappush(q,( c0+D+A, n2 ))
      heapq.heappush(q,( c0+D+A, n2+1 ))
    #
    n3, m = divmod(n0, 3)
    if m == 0:
      heapq.heappush(q,( c0+B, n3 ))
    elif m == 1:
      heapq.heappush(q,( c0+D+B, n3 ))
    else:
      heapq.heappush(q,( c0+D+B, n3+1 ))
    #
    n5, m = divmod(n0, 5)
    if m == 0:
      heapq.heappush(q,( c0+C, n5 ))
    elif m <= 2:
      heapq.heappush(q,( c0+D*m+C, n5 ))
    else:
      heapq.heappush(q,( c0+D*(5-m)+C, n5+1 ))
    #
  print(cost)
#

T = int(input())
for i in range(T):
  N,A,B,C,D = map(int, input().split())
  pay2win()
### BUGGY CODE ###

import math
def main():
  a,b,k = list(map(int,input().split()))
  for i in range(a,b+1):
    if (i < a+k) or(b-k+1 <= i):
      print(i)
  
main()


### FIXED CODE ###

def main():
  a,b,k = list(map(int,input().split()))
  minlist=[]
  maxlist=[]
  ans=[]
  for i in range(0,k):
    if b-i>=a:
      minlist.append(a+i)
    if b-i>=a+k:
      maxlist.insert(0,b-i)
  ans=minlist+maxlist
  set(ans)
  for i in range(0,len(ans)):
    print(ans[i])
main()
### BUGGY CODE ###

# 整数を一つ入力
N = int(input())

# 文字列を一つ入力
S = input()

res = 0

for i in range(N-2):
    for j in range(i+1,N-1):
        if S[i] == S[j]:
            continue
        for k in range(j+1,N):
            if j-i == k-j:
                continue
            if S[i] == S[k] or S[j] == S[k]:
                continue
            res += 1

print(res)


### FIXED CODE ###

# 整数を一つ入力
N = int(input())

# 文字列を一つ入力
S = input()

res = 0

R = []
G = []
B = []

for i in range(N):
    if S[i] == "R":
        R.append(i)
        continue
    if S[i] == "G":
        G.append(i)
        continue
    B.append(i)

BN = len(B)

for i in R:
    for j in G:
        res += BN
        ii,jj = i,j
        if ii > jj:
            ii,jj = jj,ii
        if ii - (jj-ii) >= 0:
            if S[ii-(jj-ii)] == "B":
                res -= 1
        if (abs(jj-ii)) % 2 == 0:
            if S[(jj+ii) // 2] == "B":
                res -= 1
        if jj + (jj-ii) <= N-1:
            if S[jj+(jj-ii)] == "B":
                res -= 1
print(res)
### BUGGY CODE ###

import bisect

n = int(input())
sl = []
for i in range(n):
    s = input()
    index = bisect.bisect_left(sl, s)  # 2 最も左(前)の挿入箇所が返ってきている
    sl.insert(index, s)

# print(sl)
c = 0
anss = []
for i, t in enumerate(sl):
    if i == 0:
        c += 1
        target = t
        continue

    if t == target:
        c += 1
    else:
        anss.append([target, c])
        target = t
        c = 1
anss.append([t, c])
anss.sort(key=lambda x: x[1], reverse=True)
target = anss[0][1]
for a in anss:
    if a[1] == target:
        print(a[0])


### FIXED CODE ###

import bisect

n = int(input())
sl = ['']*n
for i in range(n):
    sl[i] = input()
sl = sorted(sl, key=str.lower)
# print(sl)
c = 0
anss = []
max_n = 0
for i, t in enumerate(sl):
    if i == 0:
        c += 1
        target = t
        continue

    if t == target:
        c += 1
    else:
        if max_n < c:
            anss = []
            anss.append(target)
            max_n = c
        elif max_n == c:
            anss.append(target)
            max_n = c
        target = t
        c = 1

if max_n < c:
    anss = []
    anss.append(t)
elif max_n == c:
    anss.append(t)


print(*anss)
### BUGGY CODE ###

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

ans = [0 for i in range(N+1)]

for i in range(1,N):
    checking = i

    #まずスタート地点から幅優先探索を実装
    queue = [[i,0]]
    # checked = list(range(1,i+1)) #マス、距離
    checked = [i]

    while(True):
        now = queue[0]

        #ショートカット確認
        if now[0] == X:
            if Y not in checked:
                queue.append([Y,now[1]+1])
                checked.append(Y)
                if not(checking > Y):
                    ans[now[1]+1] += 1
                    # print(now[0],Y,now[1]+1)

        if now[0] == Y:
            if X not in checked:
                queue.append([X,now[1]+1])
                checked.append(X)
                if not(checking > X):
                    ans[now[1]+1] += 1
                    # print(now[0],X,now[1]+1)

        #左
        if now[0]-1 >= 1 and now[0]-1 not in checked:
            queue.append([now[0]-1,now[1]+1])
            checked.append(now[0]-1)
            if not(checking > now[0]-1):
                ans[now[1]+1] += 1
                # print(now[0],now[0]-1,now[1]+1)

        #右
        if now[0]+1 <= N and now[0]+1 not in checked:
            queue.append([now[0]+1,now[1]+1])
            checked.append(now[0]+1)
            if not(checking > now[0]+1):
                ans[now[1]+1] += 1
                # print(now[0],now[0]+1,now[1]+1)

        queue.pop(0)

        if len(checked) == N or len(queue) == 0:
            break

#回答を出力
for i in range(1,N):
    print(ans[i])


### FIXED CODE ###

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

ans = [0 for i in range(N+1)]

def calc_goal(start,goal):
    if goal <= X:
        return goal-start
    if goal <= Y:
        if X >= start:
            return min(goal-start,X-start+Y-goal+1)
        else:
            return min(start-X+Y-goal+1,goal-start)
    else:
        if X >= start:
            return X-start+goal-Y+1
        else:
            return min(start-X+goal-Y+1,goal-start)

for i in range(1,N):
    for j in range(i+1,N+1):
        ans[calc_goal(i,j)] += 1

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

from collections import Counter
n=int(input())
a=[Counter(list(input()))for _ in range(n)]
ans = 0

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

### FIXED CODE ###

from collections import Counter
n = int(input())
c = Counter([''.join(sorted(input())) for i in range(n)])
 
ans = 0
for k, cnt in c.items():
    ans+=cnt*(cnt-1)//2
print(ans)
### BUGGY CODE ###

N = int(input())

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

count = 0

for i in range(1,N+1):
    for k in range(0,len(a)):
        if(i == a[k]):
            count += 1
    print(count)
    count = 0

### FIXED CODE ###

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

import itertools
import math

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

#n=5
#a=[6,9,4,2,11]

b=list(itertools.combinations(a,2))
c=[]
for bi in b:
  bl=list(bi)
  bl.sort()
  c1=math.factorial(bl[1])
  c2=math.factorial(bl[0])
  c3=math.factorial(bl[1]-bl[0])
  c4=c1//c3//c2
  c.append([c4,bl[1],bl[0]])
c.sort()
print(c[len(c)-1][1],c[len(c)-1][2])
  

### FIXED CODE ###

import itertools
import math

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

#n=5
#a=[6,9,4,2,11]

a1=max(a)
a.remove(a1)
a2=a1/2
b=[]
for i in a:
  b.append(abs(i-a2))

print(a1,a[b.index(min(b))])
### BUGGY CODE ###

import sys
MAX_INT = int(10e10)
MIN_INT = -MAX_INT
mod = 1000000007
sys.setrecursionlimit(1000000)
def IL(): return list(map(int,input().split()))
def SL(): return input().split()
def I(): return int(sys.stdin.readline())
def S(): return input()

def tami(opened, res):
  global ans
  for i in range(1, N+1):
    if str(i) not in opened:
      for x in data[i]:
        tami(opened + " ".join(map(str, KeyID[x])), res + Value[x])
      break
  else:
    ans = min(ans, res)

N, M = IL()

KeyID = [[] for _ in range(M+1)]
data = [[] for _ in range(N+1)]
Value = [0 for _ in range(M+1)]
for i in range(1, M+1):
  a, b = IL()
  c = IL()

  KeyID[i].append(c)
  Value[i] = a
  for num in c:
    data[num].append(i)
#print(Value)
#print(KeyID)

ans = MAX_INT
tami("", 0)
if ans == MAX_INT:
  print(-1)
else:
  print(ans)

### FIXED CODE ###

MAX_INT = int(10e10)

N, M = list(map(int,input().split()))
Val = [0 for _ in range(M)]
Key = [0 for _ in range(M)]
for i in range(M):
  v, b = list(map(int,input().split()))
  k =  list(map(int,input().split()))
  Val[i] = v
  tmp = 0
  for num in k:
    tmp += 2**(num-1)
  Key[i] = tmp
#print(Val)
#print(Key)

dp = [MAX_INT for _ in range(1<<N)]
dp[0] = 0
for i in range(1<<N):
  for x in range(M):
    #print(i, i|Key[x])
    dp[i|Key[x]] = min(dp[i|Key[x]], dp[i] + Val[x])
#print(dp)
if dp[-1] == MAX_INT:
  print(-1)
else:
  print(dp[-1])
### BUGGY CODE ###

import math
import numpy as np

def main():
    h,w,k = tuple([int(t)for t in input().split()])

    s = [[int(i) for i in list(input())] for _ in range(h)]
    
    cusum = np.array([accumelist(s_) for s_ in s])

    candidates = []

    for i in range(1<<(h-1)):
        subcu = divide(cusum,i)
        subcusum = np.empty((0,w),int)

        for sub_ in subcu:
            subcusum = np.append(subcusum,np.sum(sub_,axis=0,keepdims=True),axis=0)

        cutnum = 0
        j=0
        temp = [0]*subcusum.shape[0]

        for j in range(w):
            for l in range(subcusum.shape[0]):
                if subcusum[l][j]-temp[l]>k:
                    temp = subcusum.T[j-1]
                    cutnum+=1
                    break
        
        candidates.append(cutnum+bin(i).count('1'))

    print(min(candidates))
            
def divide(s,i):
    subs = []
    counter = 0
    pos = 0
    while i!= 0:
        counter +=1
        if i%2==1:
            subs.append(s[pos:counter])
            pos = counter
        i >>=1
 
    subs.append(s[pos:])
    return subs

def accumelist(s):
    if s == []:
        return []
    res = [s[0]]
    for i in range(1,len(s)):
        res.append(res[i-1]+s[i])

    return res
    
if __name__ == "__main__":
    main()

### FIXED CODE ###

import math
import functools
from operator import add

def main():
    h,w,k = tuple([int(t)for t in input().split()])

    s = [[int(i) for i in list(input())] for _ in range(h)]
    
    cusum = [accumelist(s_) for s_ in s]

    candidates = []

    for i in range(1<<(h-1)):
        subcu = divide(cusum,i)
        subs = divide(s,i)

        subcusum = []

        rowsum = []

        for sub_ in subcu:
            subcusum.append(functools.reduce((lambda a,b:list(map(add,a,b))),sub_))

        for sub_ in subs:
            rowsum.append(functools.reduce((lambda a,b:list(map(add,a,b))),sub_))


        cutnum = 0

        temp = [0]*len(subcusum)

        for j in range(w):
            for l in range(len(subcusum)):
                if subcusum[l][j]-temp[l]>k:
                    if rowsum[l][j]>k:
                        cutnum+=10000
                    temp = [x[j-1] for x in subcusum]
                    cutnum+=1
                    break
        
        candidates.append(cutnum+bin(i).count('1'))

    print(min(candidates))
            
def divide(s,i):
    subs = []
    counter = 0
    pos = 0
    while i!= 0:
        counter +=1
        if i%2==1:
            subs.append(s[pos:counter])
            pos = counter
        i >>=1
 
    subs.append(s[pos:])
    return subs

def accumelist(s):
    if s == []:
        return []
    res = [s[0]]
    for i in range(1,len(s)):
        res.append(res[i-1]+s[i])

    return res

def _add_(a,b):
    return map(add,a,b)
    
if __name__ == "__main__":
    main()
### BUGGY CODE ###

import sys
import numpy as np
input = sys.stdin.buffer.readline
Q = int(input())


def is_prime(v):
    for i in range(2, v):
        if i * i > v:
            break
        if v % i == 0:
            return False
    return True


is_primes = np.ones(10**5 + 2, dtype='bool')
is_primes[:2] = False
for i in np.arange(2, is_primes.shape[0]):
    if not is_primes[i]:
        continue
    if is_prime(i):
        is_primes[i * 2::i] = False
# print('is_primes', is_primes[:14])

V = [0] * (10**5 + 2)
for i in range(1, len(V)):
    if i % 2 == 0:
        V[i] = V[i - 1]
        continue
    if is_primes[i] and is_primes[(i + 1) // 2]:
        V[i] = V[i - 1] + 1
    else:
        V[i] = V[i - 1]
# print('V', V)

for _ in range(Q):
    l, r = map(int, input().split())
    # print('l - 1, r, V[l- 1], V[r]', l - 1, r, V[l - 1], V[r])
    print(V[r] - V[l - 1])


### FIXED CODE ###

import numpy as np
Q = int(input())
lr = [list(map(int, input().split())) for _ in range(Q)]

is_prime = np.zeros(10**5 + 1, dtype='bool')
for i in range(2, 10**5 + 1):
    if not is_prime[i]:
        for j in range(2, int(np.sqrt(i) + 1)):
            if i % j == 0:
                break
        else:
            is_prime[i] = True
            # is_prime[::i] = True
# print(is_prime[:10])

like_2017 = np.zeros(10**5 + 1, dtype='bool')
for i in range(1, 10**5 + 1):
    if is_prime[i] and is_prime[(i + 1) // 2]:
        like_2017[i] = True
# print(like_2017)
# print(like_2017.cumsum())
cumsum = like_2017.cumsum()

for l, r in lr:
    print(cumsum[r] - cumsum[l - 1])
### BUGGY CODE ###

N = int(input())

testimonies_all = []
for i in range(N):
    A = int(input())
    testimonies = []
    for j in range(A):
        x, y = map(int, input().split())
        testimonies.append((x, y))
    testimonies_all.append(testimonies)

import itertools
assumptions = list(itertools.product((0, 1), repeat = N))

answers = []
for i in assumptions:
    assumptions2 = []
    for j in range(N):
        assumptions2.append((j + 1, i[j]))
        if i[j] == 1:
            for k in testimonies_all[j]:
                assumptions2.append(k)
    assumptions2.sort()
    count = 0
    for j in range(len(assumptions2) - 1):
        if assumptions2[j][0] == assumptions2[j + 1][0] and assumptions2[j][1] != assumptions2[j + 1][1]:
            count += 1
    if count == 0:
        answers.append(sum(i))

print(max(answers))


### FIXED CODE ###

N = int(input())

testimonies_all = []
for i in range(N):
    A = int(input())
    testimonies = []
    for j in range(A):
        x, y = map(int, input().split())
        testimonies.append((x, y))
    testimonies_all.append(testimonies)

import itertools
assumptions = list(itertools.product((0, 1), repeat = N))

answers = []
for i in assumptions:
    assumptions2 = []
    for j in range(N):
        assumptions2.append((j + 1, i[j]))
        if i[j] == 1:
            for k in testimonies_all[j]:
                assumptions2.append(k)
    assumptions2.sort()
    count = 0
    for j in range(len(assumptions2) - 1):
        if assumptions2[j][0] == assumptions2[j + 1][0] and assumptions2[j][1] != assumptions2[j + 1][1]:
            count += 1
            break
    if count == 0:
        answers.append(sum(i))

print(max(answers))
### BUGGY CODE ###

N=int(input())
A=list(range(N))
S=list(range(N-1))

for i in range(N):
    A[i]=int(input())

for i in range(N):
    r=0
    for j in range(N):
     if j!=i:
       if A[j]>r:
          r=A[j]

    print(r)

### FIXED CODE ###

N=int(input())
A=list(range(N))


r=0
count=0
for i in range(N):
    A[i]=int(input())
    if A[i]>r:
     r=A[i]
     count=i

for i in range(N):
    if i==count:
     del A[i]
     print(max(A))
    else:
     print(r)
### BUGGY CODE ###

N = int(input())
H = list(map(int, input().split()))
lowest = 10**10
for i in range(N - 2):
    if H[i] - H[i + 1] >= 2:
        print("No")
        exit()
    elif H[i] > H[i + 1]:
        H[i] -= 1
        lowest = min(H[i + 1:])
        if H[i] > lowest:
            print("No")
            exit()
print("Yes")

### FIXED CODE ###

N = int(input())
H = [int(x) for x in input().split()][::-1]
for i in range(1, N):
    d = H[i] - H[i - 1]
    if d >= 2:
        print("No")
        exit()
    elif d == 1:
        H[i] -= 1
print("Yes")
### BUGGY CODE ###

def main():
    k = int(input())
    a = 7
    c = 1
    b = 7
    if k == 2 or k == 5:
        print(-1)
        exit()
    while True:
        if a%k== 0:
            print(c)
            break
        else:
            b = (b*10)%k
            a = b+a
            a = a %k
            c += 1
            if c > k:
                print(-1)

main()

### FIXED CODE ###

def main():
    k = int(input())
    a = 7
    c = 1
    b = 7
    if k == 2 or k == 5:
        print(-1)
        exit()
    while True:
        if a%k== 0:
            print(c)
            break
        else:
            b = (b*10)%k
            a = b+a
            a = a %k
            c += 1
            if c > k:
                print(-1)
                exit()

main()
### BUGGY CODE ###

H,W = map(int,input().split())
INF = 10**10
trout = [[INF for i in range(W)]for i in range(H)]
q = []
for h in range(H):
  a = list(input())
  for w in range(W):
    if a[w]=='#':
      if 0<=h-1:
        q.append([h-1,w])
      if h+1<H:
        q.append([h+1,w])
      if 0<=w-1:
        q.append([h,w-1])
      if w+1<W:
        q.append([h,w+1])
      trout[h][w] = 0
while len(q)!=0:
  h,w = q[0][0],q[0][1]
  del q[0]
  if trout[h][w]==INF:
    s = []
    if 0<=h-1:
      q.append([h-1,w])
      s.append(trout[h-1][w])
    if h+1<H:
      q.append([h+1,w])
      s.append(trout[h+1][w])
    if 0<=w-1:
      q.append([h,w-1])
      s.append(trout[h][w-1])
    if w+1<W:
      q.append([h,w+1])
      s.append(trout[h][w+1])
    trout[h][w] = min(s)+1
res = 0
for h in range(H):
  res = max([res]+trout[h])
print(res)

### FIXED CODE ###

H,W = map(int,input().split())
A = [list(input()) for i in range(H)]
S = [[0]*W for i in range(H)]
for h in range(H):
    for w in range(W):
        if A[h][w]=="#":
            S[h][w] = H*W
for h in range(H):
    a = 0
    for w in range(W):
        S[h][w] = max(a,S[h][w])
        a = max(a,S[h][w])-1
    for w in range(W)[::-1]:
        S[h][w] = max(a,S[h][w])
        a = max(a,S[h][w])-1
for w in range(W):
    a = 0
    for h in range(H):
        S[h][w] = max(a,S[h][w])
        a = max(a,S[h][w])-1
    for h in range(H)[::-1]:
        S[h][w] = max(a,S[h][w])
        a = max(a,S[h][w])-1
ans = H*W
for h in range(H):
    for w in range(W):
        ans = min(ans,S[h][w])
print(H*W-ans)
### BUGGY CODE ###

import sys
from bisect import bisect, bisect_left
import heapq

def solve():
    input = sys.stdin.readline
    N, M = map(int, input().split())
    A = [int(a) for a in input().split()]
    A.sort()
    S = [0] * (N + 1)
    for i, a in enumerate(A): S[i + 1] = a + S[i]
 
    l, h = 1, A[N-1] * 2 + 1
    while h - l > 1: #最小値がｍ以上の要素をM個用意できるか
        m = (h + l) // 2
        count = 0
        for i, a in enumerate(A): count += N - bisect_left(A, m - a)
        if count >= M: l = m
        else: h = m

    total = 0
    count = 0
    Q = []
    heapq.heapify(Q)
    #print(A)
    for i, a in enumerate(A):
        j = bisect_left(A, l - a)
        double = bisect_left(A, h - a)
        total += a * (N - j) + (S[N] - S[j])
        count += N - j
        for k in range(j, min(N - 1, double + 1)):
            heapq.heappush(Q, a + A[k])
        #print(a, j)

    if count > M:
        for _ in range(count - M):
            minus = heapq.heappop(Q)
            total -= minus

    print(total)

    return 0

if __name__ == "__main__":
    solve()

### FIXED CODE ###

import sys
from bisect import bisect, bisect_left
import heapq

def solve():
    input = sys.stdin.readline
    N, M = map(int, input().split())
    A = [int(a) for a in input().split()]
    A.sort()
    S = [0] * (N + 1)
    for i, a in enumerate(A): S[i + 1] = a + S[i]
 
    l, h = 1, A[N-1] * 2 + 1
    while h - l > 1: #最小値がｍ以上の要素をM個用意できるか
        m = (h + l) // 2
        count = 0
        for i, a in enumerate(A): count += N - bisect_left(A, m - a)
        if count >= M: 
            l = m
        else: h = m

    total = 0
    count = 0
    Q = []
    heapq.heapify(Q)
    min_out = 10000000
    for i, a in enumerate(A):
        j = bisect_left(A, l - a)  
        total += a * (N - j) + (S[N] - S[j])
        count += N - j
        if 0 <= j < N: min_out = min(min_out, a + A[j])

    if count > M:
        total -= min_out * (count - M)

    print(total)

    return 0

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

N = int(input())
H = list(map(int,input().split()))
ans = 0
cnt = 0
start = 0
for i in range(N):
    if start > i:
        continue
    ans = max(ans,cnt)
    cnt = 0
    for j in range(N-i-1):
        if H[i+j] >= H[i+j+1]:
            cnt += 1
            if i+j+1 == N-1:
                print(max(ans,cnt))
                exit()
        else:
          start = j+1
          break    
print(ans)

### FIXED CODE ###

N = int(input())
H = list(map(int,input().split()))
ans = 0
cnt = 0
for i in range(N-1):
      if H[i] >= H[i+1]:
          cnt += 1
      else:
          ans = max(ans,cnt)
          cnt = 0
      if i+2 == N:
        print(max(ans,cnt))
        exit()
print(ans)
### BUGGY CODE ###

import heapq

n, m = map(int, input().split())
a = [int(i) for i in input().split()]
heapq.heapify(a)

for _ in range(m):
    b, c = map(int, input().split())
    for _ in range(b):
        p = heapq.heappop(a)
        if p < c:
            heapq.heappush(a, c)
        else:
            heapq.heappush(a, p)
            break

print(sum(a))

### FIXED CODE ###

import heapq

n, m = map(int, input().split())
a = sorted([int(i) for i in input().split()])
heapq.heapify(a)
l = []

for _ in range(m):
    b, c = map(int, input().split())
    l.append((b, c))

l = sorted(l, key=lambda x: x[1], reverse=True)

for b, c in l:
    if a[0] >= c:
        break
    for _ in range(b):
        if a[0] < c:
            heapq.heappushpop(a, c)
        else:
            break

print(sum(a))