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

import sys
def input(): return sys.stdin.readline().strip()
n=int(input())
ll=map(int,input().split())
from itertools import combinations
print(sum(1 for a,b,c in combinations(ll,3) if a<b+c and b<c+a and c<a+b))

### FIXED CODE ###

from bisect import bisect_left,bisect_right
import sys
def input(): return sys.stdin.readline().strip()
n=int(input())
ll=sorted(list(map(int,input().split())))
c=0
lll=len(ll)
for i in range(lll-2):
    for j in range(i+1, lll-1):
        uk = bisect_left(ll, ll[i] + ll[j], j+1)
        lk = bisect_right(ll, abs(ll[j] - ll[i]), j+1, uk)
        c+=uk-lk
print(c)
### BUGGY CODE ###

N = int(input())
A = list(map(int, input().split()))
A = sorted(A)
max_ans = 0
ans_op = []
if A[0] < 0 and A[-1] < 0:
    tmp = A[-1] - A[-2]
    ans_op.append([A[-1], A[-2]])
    A = A[:-2]
    A.append(tmp)
elif A[0] > 0 and A[-1] > 0:
    tmp = A[0] - A[1]
    ans_op.append([A[0], A[1]])
    A = A[2:]
    A.insert(tmp, 0)
while len(A) != 1:
    if A[-2] <= 0:
        tmp = A[-1] - A[-2]
        ans_op.append([A[-1], A[-2]])
        A = A[:-2]
        A.append(tmp)
    else:
        tmp = A[0] - A[-1]
        ans_op.append([A[0], A[-1]])
        A = A[1:-1]
        A.insert(0, tmp)

print(A[0])
for op in ans_op:
    print(op[0], op[1])


### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
A = sorted(A)
max_ans = 0
ans_op = []
if A[0] < 0 and A[-1] < 0:
    al = A.pop(-1)
    ar = A.pop(-1)
    tmp = al - ar
    ans_op.append([al, ar])
    A.append(tmp)
    N -= 1
elif A[0] > 0 and A[-1] > 0:
    al = A.pop(0)
    ar = A.pop(0)
    tmp = al - ar
    ans_op.append([al, ar])
    A.insert(0, tmp)
    N -= 1
tmp = A.pop(-1)
if N >= 2:
    tmpl = A.pop(0)
else:
    tmpl = 0
    
for i in range(N-2):
    if A[-1] <= 0:
        ar = A.pop(-1)
        ans_op.append([tmp, ar])
        tmp = tmp - ar
    else:
        ans_op.append([tmpl, tmp])
        tmpl = tmpl - tmp
        tmp = A.pop(-1)
        # A.insert(0, tmp)
ans_op.append([tmp, tmpl])
print(tmp-tmpl)
for op in ans_op:
    print(op[0], op[1])
### BUGGY CODE ###

# -*- coding: utf-8 -*-

import itertools


def mostProperComb(childs, x):
    tmp_sum = sum([c[1] for c in childs])
    if tmp_sum > x:
        print("IMPOSSIBLE")
        exit()

    total = tmp_sum + sum([c[0] for c in childs])

    max_a, min_b = 0, 0
    for code in itertools.product([True, False], repeat=len(childs)):
        a = 0
        for j, bool in enumerate(code):
            if bool:
                a += childs[j][1]
            else:
                a += childs[j][0]
            if a > x:
                break
        if a >= max_a and x >= a:
            max_a, min_b = a, total - a
            if max_a == x:
                break

    return (tuple(sorted([x, min_b], reverse=True)))


n = int(input())

p_list = [0] + list(map(int, input().split()))
x_list = list(map(int, input().split()))
c_list = [[] for i in range(n)]

if n == 1:
    print("POSSIBLE")
    exit()

for i in range(n):
    index = n - 1 - i

    if len(c_list[index]) == 0:
        c_list[index] = (x_list[index], 0)
        c_list[p_list[index] - 1].append(index)
    else:
        childs = [c_list[child_index] for child_index in c_list[index]]
        c_list[index] = mostProperComb(childs, x_list[index])
        if not p_list[index] == 0:
            c_list[p_list[index] - 1].append(index)

print("POSSIBLE")


### FIXED CODE ###

# -*- coding: utf-8 -*-

import itertools


def mostProperComb(childs, x):
    tmp_sum = sum([c[1] for c in childs])
    if tmp_sum > x:
        print("IMPOSSIBLE")
        exit()

    total = tmp_sum + sum([c[0] for c in childs])

    sset = set([tmp_sum])
    for child in childs:
        rest = child[0] - child[1]
        tmp_set = set(sset)
        for s in sset:
            if s + rest <= x:
                tmp_set.add(s+rest)
        sset = tmp_set

    return (tuple(sorted([x, total-max(sset)], reverse=True)))


n = int(input())

p_list = [0] + list(map(int, input().split()))
x_list = list(map(int, input().split()))
c_list = [[] for i in range(n)]

if n == 1:
    print("POSSIBLE")
    exit()

for i in range(n):
    index = n-1-i

    if len(c_list[index]) == 0:
        c_list[index] = (x_list[index], 0)
        c_list[p_list[index]-1].append(index)
    else:
        childs = [c_list[child_index] for child_index in c_list[index]]
        c_list[index] = mostProperComb(childs, x_list[index])
        if not p_list[index] == 0:
            c_list[p_list[index]-1].append(index)

print("POSSIBLE")
### BUGGY CODE ###

def expe(x):
  l = [i/x for i in range(1, x, 1)] + [1.0]
  return sum(l)

n, k = map(int, input().split())
li = [expe(int(j)) for j in input().split()]
li2 = [sum(li[m:m+k]) for m in range(0, len(li) - k + 1, 1)]

print(max(li2))

### FIXED CODE ###

n, k = map(int, input().split())
li = [(int(j) + 1) / 2 for j in input().split()]

if k == 1:
  print(max(li))
else:
  a = 0
  for i in range(n-k+1):
    if i == 0:
      xe = sum(li[0:k])
    else:
      xe = xe - li[i-1] + li[i+k-1]
    a = max(a, xe)
  print(a)
### BUGGY CODE ###

import queue

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

ans = [0] * (N + 1)

def push(q, dist, index, dist_v):
    if dist[index] != -1:
        return
    q.put(index)
    dist[index] = dist_v

for i in range(N):
    q = queue.Queue()
    dist = [-1] * N
    push(q, dist, i, 0)
    while not q.empty():
        v = q.get()
        d = dist[v]
        if v - 1 >= 0: push(q, dist, v - 1, d + 1)
        if v + 1 < N: push(q, dist, v + 1, d + 1)
        if v == X: push(q, dist, Y, d + 1)
        if v == Y: push(q, dist, X, d + 1)
    for j in range(N):
        ans[dist[j]] += 1

for i in range(N):
    ans[i] //= 2

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


### FIXED CODE ###

from collections import deque

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

ans = [0] * (N + 1)

def push(q, dist, index, dist_v):
    if dist[index] != -1:
        return
    q.appendleft(index)
    dist[index] = dist_v

for i in range(N):
    q = deque()
    dist = [-1] * N
    push(q, dist, i, 0)
    while len(q) > 0:
        v = q.pop()
        d = dist[v]
        if v - 1 >= 0: push(q, dist, v - 1, d + 1)
        if v + 1 < N: push(q, dist, v + 1, d + 1)
        if v == X: push(q, dist, Y, d + 1)
        if v == Y: push(q, dist, X, d + 1)
    for j in range(N):
        ans[dist[j]] += 1

for i in range(N):
    ans[i] //= 2

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

R, G, B, N = map(int, input().split())
cnt = 0
for i in range(int(N/R)+1):
    r = i*R
    for j in range(int(N/G)+1):
        g = j*G
        if N-g-r >= 0 and(N-g-r) % B == 0:
            cnt += 1
print(cnt)

### FIXED CODE ###

R, G, B, N = map(int, input().split())
cnt = 0
for i in range(int(N/R)+1):
    r = i*R
    for j in range(int(N/G)+1):
        g = j*G
        b = N - g - r
        if b >= 0 and b % B == 0:
            cnt += 1
print(cnt)
### BUGGY CODE ###

from scipy.misc import comb

n = int(input())
a = list(map(int,input().split()))
for i in range(n):
    l = a[i]
    a[i] = 'X'
    ans = 0
    a_s = set(a)
    for j in a_s:
        ans += comb(a.count(j),2,exact=True)
    print(ans)
    a[i] = l


### FIXED CODE ###

from collections import Counter
n = int(input())
a = list(map(int,input().split()))

c = Counter(a)
key = c.keys()
comb = 0
for i in key:
    comb += (c[i]) * (c[i]-1) // 2

for i in a:
    ans = comb - (c[i]-1)
    print(ans)
### BUGGY CODE ###

#!/usr/bin/env python
# -*- coding: utf-8 -*-
#
# FileName: 	C
# CreatedDate:  2020-05-03 21:27:46 +0900
# LastModified: 2020-05-03 21:47:49 +0900
#


import os
import sys


def main():
    n,m = map(int,input().split())
    h = list(map(int,input().split()))
#    color=[0]*n
    matrix = list([0]*n for _ in range(n))
    for i in range(m):
        a,b = map(int,input().split())
        matrix[a-1][b-1]=1
        matrix[b-1][a-1]=1
    
    count=0
    flag=0
    for i in range(n):
        for j in range(n):
            if matrix[i][j]==1 and h[i]<=h[j] :
                flag=1
                break
        if flag==0:
#            color[i]=1
            count+=1
        flag=0
    print(count)

if __name__ == "__main__":
    main()


### FIXED CODE ###

#!/usr/bin/env python
# -*- coding: utf-8 -*-
#
# FileName: 	C_fix
# CreatedDate:  2020-06-27 13:14:18 +0900
# LastModified: 2020-06-27 13:50:05 +0900
#


def main():
    n, m = map(int, input().split())
    h = list(map(int, input().split()))
    ma = [0]*n
    for _ in range(m):
        a, b = map(int, input().split())
        ma[a-1] = max(ma[a-1], h[b-1])
        ma[b-1] = max(ma[b-1], h[a-1])
#        print(ma)
    cnt = 0
    for i in range(n):
        if ma[i] < h[i]:
            cnt += 1
    print(cnt)




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

import numpy as np
n,k,q = map(int,input().split())
a =np.array([k]*n)
for i in range(q):
    a-=1
    a[int(input())-1]+=1
for i in range(n):
    if a[i]>0:
        print("Yes")
    else:
        print("No")

### FIXED CODE ###

import numpy as np
n,k,q = map(int,input().split())
a =np.array([k]*n)
a-=q
for i in range(q):
    a[int(input())-1]+=1
for i in range(n):
    if a[i]>0:
        print("Yes")
    else:
        print("No")
### BUGGY CODE ###

# -*- coding: utf-8 -*-

"""
全探索
・ビットでやる
"""

N = int(input())
aN = list(map(int, input().split()))
Q = int(input())
mQ = list(map(int, input().split()))

for i in range(Q):
    # 全組み合わせ2^Nのループ
    for j in range(1 << N):
        sm = 0
        for k in range(N):
            # 各ビットについて、立っていればその位置の値を加算
            if j >> k & 1:
                sm += aN[k]
        if sm == mQ[i]:
            print('yes')
            break
    else:
        print('no')



### FIXED CODE ###

# -*- coding: utf-8 -*-

"""
全探索
・再帰で作る
・2^20でTLEするからメモ化した
"""

N = int(input())
aN = list(map(int, input().split()))
Q = int(input())
mQ = list(map(int, input().split()))

def dfs(cur, depth, ans):
    # 終了条件
    if cur == ans:
        return True
    # memo[現在位置]に数値curがあれば、そこから先はやっても同じだからやらない
    if cur in memo[depth]:
        return False
    memo[depth].add(cur)
    # 全探索
    for i in range(depth, N):
        if dfs(cur+aN[i], i+1, ans):
            return True
    # 見つからなかった
    return False

for i in range(Q):
    memo = [set() for j in range(N+1)]
    if dfs(0, 0, mQ[i]):
        print('yes')
    else:
        print('no')
### BUGGY CODE ###

n = int(input())
L = sorted(map(int,input().split()))
ans = 0

for i in range(n):
    for j in range(i+1,n):
        for k in range(j+1,n):
            a = L[i]
            b = L[j]
            c = L[k]
            
            if c < a + b:
                ans += 1
            else:
                break
            
print(ans)

### FIXED CODE ###

import bisect
#二分探索をするライブラリ

n = int(input())
L = sorted(map(int,input().split()))
ans = 0

# c <= b <= a とする

for i in range(n-2):
    for j in range(i+1,n-1):
        a = L[n-1-i]
        b = L[n-1-j]
        
        if a-b < b:
            ans += (n-1-j) - bisect.bisect_left(L,a-b+1)
        
print(ans)
### BUGGY CODE ###

S = input()

words = ['dreamer', 'eraser', 'dream', 'erase']

T = ''
T_next = ''

while len(T) < len(S):
    if len(T) + 5 > len(S):
        break
    for i in range(4):
        S_head = S[:len(T + words[i])]
        T_next = T + words[i]
        #print(S_head)
        #print(T_next)
        #print()
        if T_next == S:
            print('YES')
            exit()
        elif (words[i] in words[0:1]) and (len(T_next) < len(S) and S[len(T_next)] == 'a'):
            pass
        elif S_head == T_next:
            T = T_next
            break

print('NO')

### FIXED CODE ###

S = input()
S = S[::-1]

words = ['dreamer', 'eraser', 'dream', 'erase']
for i in range(4):
    K = words[i]
    words[i] = K[::-1]

T = ''
T_next = ''

while True:
    if len(T) + 5 > len(S):
        break
    for i in range(4):
        S_next = S[len(T):len(T + words[i])]
        T_next = words[i]
        flag = False
        #print(S_next)
        #print(T_next)
        #print()
        if S_next == T_next:
            flag = True
            T += T_next
            #print(T)
            #print()
            #input()
            if T == S:
                print('YES')
                exit()
            break
    if flag == False:
        break
    #input()

print('NO')
### BUGGY CODE ###

n,m=map(int,input().split())
A=sorted(list(map(int,input().split())))
for i in range(m):
  A[A.index(max(A))]//=2
print(sum(A))

### FIXED CODE ###

import heapq
n,m=map(int,input().split())
A=list(map(int,input().split()))
H=[]
for a in A:
    heapq.heappush(H,-a)
for i in range(m):
    heapq.heappush(H,-(-heapq.heappop(H)//2))
print(-sum(H))
### BUGGY CODE ###

import sys
from copy import deepcopy
from functools import lru_cache
sys.setrecursionlimit(10**6)

def main():
    # input and preparation
    F = 2*10**5
    mod = 10**9+7
    fact = [1]*F
    inv = [1]*F
    for i in range(2,F):
        fact[i]=(fact[i-1]*i)%mod
    inv[F-1]=pow(fact[F-1],mod-2,mod)
    for i in range(F-2,1,-1):
        inv[i] = (inv[i+1]*(i+1))%mod
    n=int(input())
    node=[[] for i in range(n)]
    for i in range(n-1):
        a,b=map(int,input().split())
        node[a-1].append(b-1)
        node[b-1].append(a-1)
    
    memo=[[0]*n for i in range(n)]

    # node i is list of [child,size,comb] connected i
    # return [size,comb]
    def deep(i,parent):
        if len(node[i])==1 and parent!=-1:
            return [1,1]
        mysize=0
        mycomb=1
        for j in node[i]:
            if j!=parent:
                size,comb=memo[j][i] if memo[j][i] != 0 else deep(j,i)
                mysize+=size
                mycomb=(mycomb*comb)%mod
                mycomb=(mycomb*inv[size])%mod
        mycomb=(mycomb*fact[mysize])%mod
        if parent!=-1:
            memo[i][parent]=(mysize+1,mycomb)
        return (mysize+1,mycomb)
    
    for i in range(n):
        print(deep(i,-1)[1])

main()


### FIXED CODE ###

n=int(input())
F = n+5
mod = 10**9+7
fact = [1]*F
inv = [1]*F
for i in range(2,F):
    fact[i]=(fact[i-1]*i)%mod
inv[F-1]=pow(fact[F-1],mod-2,mod)
for i in range(F-2,1,-1):
    inv[i] = (inv[i+1]*(i+1))%mod

#invnum[0] cant be used
invnum=[fact[i-1]*inv[i] for i in range(n)]

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

stack=[0]
order=[0]
parent=[-1]*n
comb=[0]*n
size=[1]*n

# BFS order
while stack:
    node = stack.pop()
    for neib in graph[node]:
        if neib!=parent[node]:
            stack.append(neib)
            order.append(neib)
            parent[neib]=node

#calc size including self
for node in order[n-1:0:-1]:
    size[parent[node]]+=size[node]

#calc root comb
comb[0]=fact[n-1]
for node in range(1,n):
    comb[0]*=invnum[size[node]]
    comb[0]%=mod

#calc all comb
for node in order[1:]:
    comb[node]=comb[parent[node]]*size[node]*invnum[n-size[node]]%mod

print(*comb,sep="\n")
### BUGGY CODE ###

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

sa=0
ans=1
ma=max(k)

for i in range(a-1):
    if k[i]==ma:
        ma=max(k[i+1:a])
    tmp=ma-k[i]
    if tmp>sa:
        sa=tmp
        ans=1
    elif tmp==sa:
        ans+=1

    

print(ans)

### FIXED CODE ###

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

sa=0
ans=1

n=k[a-1]

for i in range(a-2,-1,-1):
    if k[i]>n:
        n=k[i]
    tmp=n-k[i]
    if tmp>sa:
        sa=tmp
        ans=1
    elif tmp==sa:
        ans+=1

    

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

import sys
input=sys.stdin.readline
H,W,D = map(int,input().split())
A = []
for h in range(H):
  A = A + list(map(int,input().split()))
for i in range(H*W):
  A[i]=(A[i], i, i%W, i//W)
A.sort()

Q = int(input())
for q in range(Q):
  L,R = map(int,input().split())
  ret = 0
  x0,y0=A[L-1][2],A[L-1][3]
  for l in range((R-L)//D):
    x,y=A[L+D*(l+1)-1][2],A[L+D*(l+1)-1][3]
    ret += abs(x-x0)+abs(y-y0)
    x0,y0=x,y
  print(ret)

### FIXED CODE ###

import sys
input=sys.stdin.readline
H,W,D = map(int,input().split())
A = []
for h in range(H):
  A = A + list(map(int,input().split()))
for i in range(H*W):
  A[i]=(A[i], i%W, i//W)
A.sort()
Dist=[0]*(H*W)
for i in range(H*W):
  if i>=D:
    Dist[i] = Dist[i-D] + abs(A[i][1]-A[i-D][1]) + abs(A[i][2]-A[i-D][2])
Q = int(input())
for q in range(Q):
  L,R = map(int,input().split())
  ret = Dist[R-1]-Dist[L-1]
  print(ret)
### BUGGY CODE ###

z=10
m=z**9+7
k=13
t=input()[::-1]
dp=[0]*k
dp[0]=1
for d in range(len(t)):
  p=[0]*k
  f=(t[d]=='?')
  for i in range(k):
    for x in range(1+f*9):
      r=pow(z,d,k)
      r*=int(x if f else t[d])
      p[(i+r)%k]+=dp[i]
  dp=[j%m for j in p]
print(dp[5]%m)


### FIXED CODE ###

from heapq import heappush, heappop
from collections import deque
import itertools
from itertools import permutations
import sys
import bisect
sys.setrecursionlimit(10**6)
#input=sys.stdin.readline
def MI():
    return map(int,input().split())
def I():
    return int(input())
def LI():
    return [int(i) for i in input().split()]
YN=['Yes','No']
YNeos='YNeos'
mo=10**9+7
imp='IMPOSSIBLE'


s=input()
t=list(s)[::-1]
ans=0
dp=[0]*13
dp[0]=1
for d in range(len(t)):
    
    if t[d]=='?':
        tm=[0]*13
        for x in range(10):
            r=int(x)*pow(10,d,13)
            for i in range(13):
                tm[(i+r)%13]+=dp[i]
        dp=[j%mo for j in tm]
    else:
        tm=[0]*13
        r=int(t[d])*pow(10,d,13)
        for i in range(13):
            tm[(i+r)%13]=dp[i]
        dp=[j for j in tm]
    #print(dp)

print(dp[5]%mo)
### BUGGY CODE ###

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

res = []
pw = ""
for i in range(2 ** N):
    cnt = 0
    for j in range(N):
        if (i >> j) & 1 == 1:
            cnt += 1
            pw += S[j]
    if cnt == 3:
        res.append(pw)
        pw = ""
    else:
        pw = ""

print(len(set(res)))


### FIXED CODE ###

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

res = 0
for i in range(10):
    for j in range(10):
        for k in range(10):
            x = S.find(str(i))
            y = S.find(str(j), x + 1)
            z = S.find(str(k), y + 1)

            if -1 < x < y < z:
                res += 1

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

N=int(input())
A = list(map(int,input().split()))
mod=1000000007
ans=0
for i in range(N-1):
  for j in range(i+1,N):
    a=A[i]*A[j]%mod
    ans+=a
    ans%=mod
print(ans)


### FIXED CODE ###

N=int(input())
A = list(map(int,input().split()))
mod=1000000007
ans=0
sumA=sum(A)
for i in range(N-1):
  sumA-=A[i]
  a=A[i]*sumA
  a%=mod
  ans+=a
  ans%=mod
print(ans)
### BUGGY CODE ###

import sys
import numpy as np
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
N, K, *A = map(int, read().split())
B = [0]*N
for _ in range(K):
  for i in range(N):
    a = max(0,i-A[i])
    b = min(N-1,i+A[i])
    B[a] += 1
    if b+1 <= N-1:
      B[b+1] -= 1
 
  B = np.cumsum(B)
  if (A == B).all():
    break
  A=B
  B = [0]*N
print(*A)

### FIXED CODE ###

import sys
import numpy as np
from numba import jit
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
N, K, *A = map(int, read().split())
K = min(50,K)

@jit
def imos(A):
  B = np.zeros_like(A)
  for i,x in enumerate(A):
    a = max(0,i-x)
    b = min(N-1,i+x)
    B[a] += 1
    if b+1 <= N-1:
      B[b+1] -= 1
  B = np.cumsum(B)
  return B

for i in range(K):
  if i >= 50:
    break
  A = imos(A)
print(*A)
### BUGGY CODE ###

n = int(input())
a = [int(s) for s in input().split()]
b = a.copy()
max_index = a.index(max(a))
count = 0
last_index = len(a)
while(last_index > 0):
    b[max_index: last_index] = [a[max_index]] * (last_index - max_index)
    last_index = max_index
    
    if last_index == 0 or len(set(a[:last_index])) <= 1:
        break
    max_index = a.index(max(a[:last_index]))

for i in range(len(a)):
    count += b[i] - a[i]
print(count)

### FIXED CODE ###

n = int(input())
a = [int(s) for s in input().split()]
count = 0
max = a[0]
for i in range(1, len(a)):
    if max >  a[i]:
        if a[i - 1] > max:
            max = a[i - 1]
        count += max - a[i]
    else:
        max = a[i]
print(count)
### BUGGY CODE ###

import os

import sys

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(10 ** 9)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7
# MOD = 998244353

N, K = list(map(int, sys.stdin.buffer.readline().split()))
a = K
b = N - K
c = 0
d = min(a, b)
while not a == b == c:
    a, b, c = sorted([a, b, c])
    if b == c and (b - a) % d == 0:
        a = b
    elif a == b:
        a += d
    else:
        d = b - a
        a += d * 2
print(a + b + c)


### FIXED CODE ###

import os

import sys

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(10 ** 9)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7
# MOD = 998244353

N, K = list(map(int, sys.stdin.buffer.readline().split()))

a = K
b = N - K
c = 0
d = min(a, b)
while not a == b == c:
    a, b, c = sorted([a, b, c])
    if a != b:
        d = b - a
    cnt = (c - b) // d
    b += d * cnt
    a += d * cnt + d
print(a + b + c)
### BUGGY CODE ###

"""
int #整数
float #小数

#for
for name in fruits: #fruitの頭から操作
    print(name)
    
#リスト
list0 = [] #リスト生成
list0 = [1,2,3,4] #初期化
list0 = [0]*10 #[0,0,0,0,0,0,0,0,0,0]
list1= [i for i in range(10)] #>>> [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
list1 = list(map(int, input().split()))　# 複数の入力をリストに入れる
number=[int(input()) for i in range(int(input()))] #複数行の入力をリストに
list1 = list1 + [6, 7, 8] #リストの追加
list2.append(34) #リストの追加　最後に（）内が足される
list.insert(3,10) #リストの追加　任意の位置（追加したい位置,追加したい値）
len(list4) #リストの要素数
max(sa) #list saの最小値
list5.count(2) #リスト(文字列も可）内の2の数
list1.sort() #並び替え小さい順
list1.sort(reverse=True)  #並び替え大きい順
set(list1) #list1内の重複している要素を削除し、小さい順に並べる
sum([2,3,   ,3]) #リストの合計

abs(a) #aの絶対値
max(a,b) min(a,b) #最大値　最小値
text1 = text1.replace("34","test") #text1内の"34"を"test"に書き換える(文字列内の文字を入れ替える)

exit(0) #強制終了
"""
K, S = map(int, input().split())
count = 0
for i in range(K + 1):
    for j in range(K + 1):
        for k in range(K + 1):
            if i + j + k == S:
                count += 1
print(count)


### FIXED CODE ###

"""
int #整数
float #小数

#for
for name in fruits: #fruitの頭から操作
    print(name)
    
#リスト
list0 = [] #リスト生成
list0 = [1,2,3,4] #初期化
list0 = [0]*10 #[0,0,0,0,0,0,0,0,0,0]
list1= [i for i in range(10)] #>>> [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
list1 = list(map(int, input().split()))　# 複数の入力をリストに入れる
number=[int(input()) for i in range(int(input()))] #複数行の入力をリストに
list1 = list1 + [6, 7, 8] #リストの追加
list2.append(34) #リストの追加　最後に（）内が足される
list.insert(3,10) #リストの追加　任意の位置（追加したい位置,追加したい値）
len(list4) #リストの要素数
max(sa) #list saの最小値
list5.count(2) #リスト(文字列も可）内の2の数
list1.sort() #並び替え小さい順
list1.sort(reverse=True)  #並び替え大きい順
set(list1) #list1内の重複している要素を削除し、小さい順に並べる
sum([2,3,   ,3]) #リストの合計

abs(a) #aの絶対値
max(a,b) min(a,b) #最大値　最小値
text1 = text1.replace("34","test") #text1内の"34"を"test"に書き換える(文字列内の文字を入れ替える)

exit(0) #強制終了
"""
K, S = map(int, input().split())
count = 0
for i in range(K + 1):
    for j in range(K + 1):
        Z=S-i-j
        if 0<=Z<=K:
            count += 1

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

n,w=map(int,input().split())
a=[[int(i) for i in input().split()]for i in range(n)]
dp=[[0 for i in range(w+1)]for i in range(n+1)]
for i in range(n):
    for sum_w in range(1,w+1):
        if sum_w-a[i][0]>=0:
            dp[i+1][sum_w]=max(dp[i][sum_w],dp[i][sum_w-a[i][0]]+a[i][1])
        else:
            dp[i+1][sum_w]=dp[i][sum_w]
print(dp[n][w])

### FIXED CODE ###

n,w=map(int,input().split())
a=[[int(i) for i in input().split()]for i in range(n)]
dp=[[0 for i in range(w+1)]for i in range(n+1)]
for i in range(n):
    for sum_w in range(1,w+1):
        if sum_w-a[i][0]>=0:
            dp[i+1][sum_w]=max(dp[i][sum_w],dp[i][sum_w-a[i][0]]+a[i][1])
        else:
            dp[i+1][sum_w]=dp[i][sum_w]
print(dp[n][w])